{"trustable":false,"sections":[{"title":"","value":{"format":"MD","content":"\u003cscript type\u003d\"text/x-mathjax-config\"\u003e\nMathJax.Hub.Config({\n tex2jax: {inlineMath: [[\u0027$$$\u0027,\u0027$$$\u0027], [\u0027$\u0027,\u0027$\u0027]], displayMath: [[\u0027$$$$$$\u0027,\u0027$$$$$$\u0027], [\u0027$$\u0027,\u0027$$\u0027]]}\n});\n\u003c/script\u003e\n\u003cscript type\u003d\"text/javascript\" async\n src\u003d\"https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.1/MathJax.js?config\u003dTeX-AMS-MML_HTMLorMML\"\u003e\n\u003c/script\u003e\n\nВ городе М\u0026City есть n домов и m двусторонних дорог между ними. Так как жители дружны, от любого дома до другого можно добраться с помощью дорог. Мнсята хотят быть еще дружнее, для этого им хочется защитится от поломки дорог. То есть, им хочется построить новые дороги так, чтобы в случае поломки одной из дорог все еще можно было добраться из любого дома до другого. Так как они умны, мнсятам хочется построить как можно меньше дорог. Помогите им это сделать."}},{"title":"Input","value":{"format":"MD","content":"В первой строке находится число тестов **T (\u0026le; 30)**.\nКаждый тест начинается с пустой строки. В следующей строке следуют два числа : **n (3 \u0026le; n \u0026le; 10000)** и **m (\u0026le; 20000)**. Каждая из следующих **m** строк содержит два числа **u v (0 \u0026le; u, v \u0026lt; n, u \u0026ne; v)** означающих двустороннюю дорогу между домами **u** и **v**. Входные данные гарантируют условия."}},{"title":"Output","value":{"format":"MD","content":"Для каждого теста выведите необходимое минимальное количество дорог для постройки, такое чтобы при поломке произвольной дороги все еще можно было добраться от любого дома до любого другого."}},{"title":"Sample Input","value":{"format":"MD","content":"\u003cpre\u003e2\n\n4 3\n1 2\n2 3\n2 0\n\n3 3\n1 2\n2 0\n0 1\n\u003c/pre\u003e"}},{"title":"Sample Output","value":{"format":"MD","content":"\u003cpre\u003eCase 1: 2\nCase 2: 0\n\u003c/pre\u003e"}},{"title":"Note","value":{"format":"MD","content":"1. используйте быстрые I/O методы.\n2. Для случая 1, одно из решений построить дороги (0, 1) и (1, 3)."}}]}