{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"\u003ch2\u003eProblem K\n \n\u003c/h2\u003e\n\n\u003cp\u003e\n Given an undirected graph, count the number of simple cycles in the graph. Here, a simple cycle is a connected subgraph all of whose vertices have degree exactly two.\n\u003c/p\u003e\n\n\u003ch3\u003eInput\u003c/h3\u003e\n\u003cp\u003e\n The input consists of a single test case of the following format.\n\u003c/p\u003e\n\n\u003cpre\u003e$n$ $m$\n$u_1$ $v_1$\n...\n$u_m$ $v_m$\n\u003c/pre\u003e\n\n\u003cp\u003e\n A test case represents an undirected graph $G$.\n\u003c/p\u003e\n\n\u003cp\u003e\n The first line shows the number of vertices $n$ ($3 \\leq n \\leq 100 000$) and the number of edges $m$ ($n - 1 \\leq m \\leq n + 15$). The vertices of the graph are numbered from $1$ to $n$.\n\u003c/p\u003e\n\n\u003cp\u003e\nThe edges of the graph are specified in the following $m$ lines. Two integers $u_i$ and $v_i$ in the\n$i$-th line of these m lines mean that there is an edge between vertices $u_i$ and $v_i$. Here, you can assume that $u_i \u0026lt; v_i$ and thus there are no self loops.\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t \u003c/p\u003e\n\n\u003cp\u003e\n For all pairs of $i$ and $j$ ($i \\ne j$), either $u_i \\ne u_j$ or $v_i \\ne v_j$ holds. In other words, there are no parallel edges.\n\u003c/p\u003e\n\n\u003cp\u003e\n You can assume that $G$ is connected.\n\u003c/p\u003e\n\n\n\u003ch3\u003eOutput\u003c/h3\u003e\n\u003cp\u003e\n The output should be a line containing a single number that is the number of simple cycles in the graph.\n\u003c/p\u003e\n\n\n\u003ch3\u003eSample Input 1\u003c/h3\u003e\n\u003cpre\u003e4 5\n1 2\n1 3\n1 4\n2 3\n3 4\n\u003c/pre\u003e\n\n\u003ch3\u003eSample Output 1\u003c/h3\u003e\n\u003cpre\u003e3\n\u003c/pre\u003e\n\n\u003ch3\u003eSample Input 2\u003c/h3\u003e\n\u003cpre\u003e7 9\n1 2\n1 3\n2 4\n2 5\n3 6\n3 7\n2 3\n4 5\n6 7\n\u003c/pre\u003e\n\n\u003ch3\u003eSample Output 2\u003c/h3\u003e\n\u003cpre\u003e3\n\u003c/pre\u003e\n\n\u003ch3\u003eSample Input 3\u003c/h3\u003e\n\u003cpre\u003e4 6\n1 2\n1 3\n1 4\n2 3\n2 4\n3 4\n\u003c/pre\u003e\n\n\u003ch3\u003eSample Output 3\u003c/h3\u003e\n\u003cpre\u003e7\n\u003c/pre\u003e\n"}}]}