{"problem":{"name":"One-stroke Path","description":{"content":"You are given an undirected unweighted graph with $N$ vertices and $M$ edges that contains neither self-loops nor double edges.   Here, a _self-loop_ is an edge where $a_i = b_i (1≤i≤M)$, and _double ","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"abc054_c"},"statements":[{"statement_type":"Markdown","content":"You are given an undirected unweighted graph with $N$ vertices and $M$ edges that contains neither self-loops nor double edges.  \nHere, a _self-loop_ is an edge where $a_i = b_i (1≤i≤M)$, and _double edges_ are two edges where $(a_i,b_i)=(a_j,b_j)$ or $(a_i,b_i)=(b_j,a_j) (1≤i<j≤M)$.  \nHow many different paths start from vertex $1$ and visit all the vertices exactly once?  \nHere, the endpoints of a path are considered visited.\nFor example, let us assume that the following undirected graph shown in Figure 1 is given.\n\n![image](https://atcoder.jp/img/5013/888b2f55d46f66125a4ac25cd8cfc19a.png)Figure 1: an example of an undirected graph\n\nThe following path shown in Figure 2 satisfies the condition.\n\n![image](https://atcoder.jp/img/5013/694eda4639f3f4608c9f0b38af1633d3.png)Figure 2: an example of a path that satisfies the condition\n\nHowever, the following path shown in Figure 3 does not satisfy the condition, because it does not visit all the vertices.\n\n![image](https://atcoder.jp/img/5013/4739baf6665ab2832ea424b1cc404ee1.png)Figure 3: an example of a path that does not satisfy the condition\n\nNeither the following path shown in Figure 4, because it does not start from vertex $1$.\n\n![image](https://atcoder.jp/img/5013/7ad401c30e069a98a34c8cfec70ec278.png)Figure 4: another example of a path that does not satisfy the condition\n\n## Constraints\n\n*   $2≦N≦8$\n*   $0≦M≦N(N-1)/2$\n*   $1≦a_i<b_i≦N$\n*   The given graph contains neither self-loops nor double edges.\n\n## Input\n\nThe input is given from Standard Input in the following format:\n\n$N$ $M$  \n$a_1$ $b_1$  \n$a_2$ $b_2$\n$:$  \n$a_M$ $b_M$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"abc054_c","tags":[],"sample_group":[["3 3\n1 2\n1 3\n2 3","2\n\nThe given graph is shown in the following figure:\n\n![image](https://atcoder.jp/img/5013/43c0ac53de20d989d100bf60b3cd05fa.png)\n\nThe following two paths satisfy the condition:\n\n![image](https://atcoder.jp/img/5013/c4a27b591d364fa479314e3261b85071.png)"],["7 7\n1 3\n2 7\n3 4\n4 5\n4 6\n5 6\n6 7","1\n\nThis test case is the same as the one described in the problem statement."]],"created_at":"2026-03-03 11:01:14"}}