{"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Дается неориентированный граф из вершин **n** и **m** ребер. Необходимо покрасить минимальное количество вершин в черный цвет так, чтобы при удалении любой вершины, каждая из компонент связности имела хотя бы одну черную вершину.\nНайдите минимальное количество черных вершин и количество способов покрасить столько вершин.\nThe junctions and tunnels are strong but if there is any kind of natural disasters like earthquakes or tornadoes, there is a chance that a junction may collapse. That\u0027s why they want to built some escape shafts in junctions (at most one shaft in one junction) that lead them to the surface. Now they want to build minimum number of shafts such that if any of the junctions (only one) collapses, ants that survive the collapse, still have a path to the surface. Now your task is to find the minimum number of shafts, and the number of ways the minimum shafts can be built."}},{"title":"Input","value":{"format":"MD","content":"Первая строка - **T (\u0026le; 30)** - количество тестов.\n\nКаждый тест начинается с пустой строки. Затем следует два числа: **n (2 \u0026le; n \u0026le; 10000)** and **m (0 \u0026le; m \u0026le; 20000)**. Каждая из следующих **m** строк содержить по 2 числа **u v (0 \u0026le; u, v \u0026lt; n, u \u0026ne; v)** двустороннее ребро между вершинами **u** и **v**. Гарантируется, что граф связный, нет петель и кратных ребер. "}},{"title":"Output","value":{"format":"MD","content":"Для каждого теста, выведите минимальное количество черных вершин и количество способов покрасить столько вершин по модулю **2\u003csup\u003e64\u003c/sup\u003e**."}},{"title":"Sample Input","value":{"format":"MD","content":"\u003cpre\u003e2\n\n6 6\n0 3\n0 1\n1 4\n4 2\n2 5\n5 0\n\n5 4\n2 1\n1 3\n0 4\n4 1\n\u003c/pre\u003e"}},{"title":"Sample Output","value":{"format":"MD","content":"\u003cpre\u003eCase 1: 2 4\nCase 2: 3 1\n\u003c/pre\u003e"}},{"title":"Note","value":{"format":"MD","content":"Dataset is huge, use faster I/O methods."}}]}