output_description: Print the number of the different paths that start from vertex 1 and visit all
  the vertices exactly once.
  
  * * *
input_description: The input is given from Standard Input in the following format:
  
      
      
      N M  
      a_1 b_1  
      a_2 b_2
      :  
      a_M b_M
attempt: import itertools
  N, M = map(int, input().split())
  p = [list(map(int, input().split())) for i in range(M)]
  v = list(map(list, itertools.permutations(range(2,N+1), N-1)))
  cnt = 0
  for i in range(len(v)):
  	vit = True
      v_i = [1]+v[i]
      for j in range(N-1):
          if sorted(v_i[j:j+2]) not in p:
              vit = False
      if vit:
          cnt += 1
  print(cnt)
problem_description: Statement
  
  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 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).  
  How many different paths start from vertex 1 and visit all the vertices
  exactly once?  
  Here, the endpoints of a path are considered visited.
  
  For example, let us assume that the following undirected graph shown in Figure
  1 is given.
  
  ![](https://atcoder.jp/img/5013/888b2f55d46f66125a4ac25cd8cfc19a.png)
  
  Figure 1: an example of an undirected graph
  
  The following path shown in Figure 2 satisfies the condition.
  
  ![](https://atcoder.jp/img/5013/694eda4639f3f4608c9f0b38af1633d3.png)
  
  Figure 2: an example of a path that satisfies the condition
  
  However, the following path shown in Figure 3 does not satisfy the condition,
  because it does not visit all the vertices.
  
  ![](https://atcoder.jp/img/5013/4739baf6665ab2832ea424b1cc404ee1.png)
  
  Figure 3: an example of a path that does not satisfy the condition
  
  Neither the following path shown in Figure 4, because it does not start from
  vertex 1.
  
  ![](https://atcoder.jp/img/5013/7ad401c30e069a98a34c8cfec70ec278.png)
  
  Figure 4: another example of a path that does not satisfy the condition
samples: [{"input": "3 3\n    1 2\n    1 3\n    2 3", "output": "2\n    \n\nThe given graph is shown in the following figure:\n\n![43c0ac53de20d989d100bf60b3cd05fa.png](https://atcoder.jp/img/5013/43c0ac53de20d989d100bf60b3cd05fa.png)\n\nThe following two paths satisfy the condition:\n\n![c4a27b591d364fa479314e3261b85071.png](https://atcoder.jp/img/5013/c4a27b591d364fa479314e3261b85071.png)\n\n* * *"}, {"input": "7 7\n    1 3\n    2 7\n    3 4\n    4 5\n    4 6\n    5 6\n    6 7", "output": "1\n    \n\nThis test case is the same as the one described in the problem statement."}]