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.
Figure 1: an example of an undirected graph
The following path shown in Figure 2 satisfies the condition.
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.
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.
Figure 4: another example of a path that does not satisfy the condition

-----Constraints-----
 - 2≦N≦8 
 - 0≦M≦N(N-1)/2 
 - 1≦a_i<b_i≦N 
 - The given graph contains neither self-loops nor double edges.

-----Input-----
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  

-----Output-----
Print the number of the different paths that start from vertex 1 and visit all the vertices exactly once.

-----Sample Input-----
3 3
1 2
1 3
2 3

-----Sample Output-----
2

The given graph is shown in the following figure:
The following two paths satisfy the condition:

Difficulty: introductory

Starter code:

Solutions:
from collections import defaultdict
N, M = list(map(int, input().split()))

d = defaultdict(list)
for _ in range(M):
    a, b = list(map(int, input().split()))
    d[a].append(b)
    d[b].append(a)


def dfs(n, path):
    count = 0
    path.append(n)
    if len(path) == N:
        count += 1
        return count
    for i in d[n]:
        if i not in path:
            count += dfs(i, path)
            path.pop()

    return count


print((dfs(1, [])))


import itertools
n,m=map(int,input().split())
edge=[[] for i in range(n+1)]
for i in range(m):
  a,b=map(int,input().split())
  edge[a].append(b)
  edge[b].append(a)
ans=0
for junretu in list(itertools.permutations(list(range(2,n+1)))):
  now=1
  flag=True
  for i in list(junretu):
    if not(i in edge[now]):
      flag=False
      break
    now=i
  if flag:
    ans+=1
print(ans)  

import itertools

n, m = list(map(int, input().split()))
lis = []
for i in range(m):
    a, b = list(map(int, input().split()))
    lis.append((a, b))

LIS = [i for i in range(2, n + 1)]
big_lis = list(itertools.permutations(LIS))
L = len(big_lis)

ans2 = 0
for j in range(L):
    i = 1
    ans1 = 1
    for k in big_lis[j]:
        if((i, k) not in lis) & ((k, i) not in lis):
            ans1 = 0
        i = k
    ans2 += ans1
print(ans2)


N, M = map(int, input().split())
Edge = [tuple(map(int, input().split())) for _ in range(M)]

Graph = [[] for _ in range(N)]
for a,b in Edge:
    Graph[a-1].append(b-1)
    Graph[b-1].append(a-1)


def dfs(v, seen):
    nonlocal Graph
    seen.add(v)
    if len(seen) == N:
        seen.remove(v)
        return 1
    Res = [dfs(nv, seen) for nv in Graph[v] if not nv in seen]
    seen.remove(v)
    return sum(Res)

print(dfs(0, set()))

from itertools import permutations
from math import factorial

n, m = map(int, input().split(' '))
edge = []
for i in range(m):
    ai, bi = map(int, input().split(' '))
    edge.append([ai, bi])

l = [i for i in range(1, n+1)]
ls = list(permutations(l))
ans = 0
for i in range(factorial(n-1)):
    y = 0
    for j in range(n-1):
        for k in edge:
            if (ls[i][j+1] in k) and (ls[i][j] in k):
                y += 1
    if y == n-1:
        ans += 1

print(ans)

import itertools

n,m=map(int,input().split())
rin=[[]for _ in range(n)]
for _ in range(m):
  a,b=map(int,input().split())
  rin[a-1].append(b-1)
  rin[b-1].append(a-1)
  
li=[ i for i in range(2,n+1)]

ans=0

for v in itertools.permutations(li):
  pas=0
  ch=0
  st=1
  for x in range(n-1):
    if v[x]-1 not in rin[st-1]:
      ch+=1
      break
    else:
      st=v[x]
  if ch==0:
    ans+=1
    
print(ans)

from itertools import permutations

N, M = map(int, input().split())
path = [[False] * N for _ in range(N)]

for i in range(M):
    a, b = map(int, input().split())
    a, b = a - 1, b - 1
    path[a][b] = path[b][a] = True

    ans = 0
    for i in permutations(range(N), N):
        if i[0] == 0:
            for j in range(N):
                if j == N - 1:
                    ans += 1
                    break
                if not path[i[j]][i[j + 1]]:
                    break

print(ans)

N, M = map(int, input().split())
leng = [set() for i in range(N+1)]
res = 0
for _ in range(M):
  a,b = map(int, input().split())
  leng[a].add(b)
  leng[b].add(a)
def check(arr):
  for i in range(N-1):
    if arr[i+1] not in leng[arr[i]]:
      return False
  return True

import itertools
for i in itertools.permutations([x for x in range(2,N+1)]):
  if check([1]+list(i)):
    res += 1
print(res)

import itertools

N, M = list(map(int, input().split()))

graph = [[False]*N for _ in range(N)]

for _ in range(M):
    a, b = [int(x)-1 for x in input().split()]
    graph[a][b] = True
    graph[b][a] = True

ans = 0

#頂点を並び替える順列を生成してループ
for path in itertools.permutations(list(range(N)), N):
    if path[0] == 0: #先頭が頂点1の時
        for i in range(N):
            if i==N-1:
                ans += 1
                break
            if not graph[path[i]][path[i+1]]:
                break
print(ans)


import itertools

n, m = map(int, input().split())
g = [[0]*n for _ in range(n)]
for _ in range(m):
    a, b = map(int, input().split())
    a, b = a-1, b-1
    g[a][b] = 1
    g[b][a] = 1

a = list(itertools.permutations(range(n)))
ans = 0
for i in a:
    if i[0] != 0:
        break
    for j in range(n-1):
        if g[i[j]][i[j+1]] == 0:
            break
    else:
        ans += 1
print(ans)

import itertools

n, m = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(m)]

# generate permunations from Node 2 to Node n
p = itertools.permutations(range(2, n + 1), n - 1)

cnt = 0
for v in p:
    if [1, v[0]] not in ab and [v[0], 1] not in ab:
        continue
    else:
        if all([n0, n1] in ab or [n1, n0] in ab for n0, n1 in zip(v, v[1:])):
            cnt += 1
print(cnt)

def dfs(place,number,checkedList,path):
  checkedList[place] = 1
  if sum(checked) == number:
    return 1
  pathNumber = 0
  for i in path[place]:
    if checkedList[i] == 1:
      continue
    pathNumber += dfs(i,number,checkedList,path)
    checkedList[i] = 0
  return pathNumber  

n, m = map(int, input().split())

checked = [0] * 8
path = [ [] for _ in range(8)]
for i in range(m):
  a, b = map(int, input().split())
  path[a-1].append(b-1)
  path[b-1].append(a-1)
  #print(path)
  
print(dfs(0,n,checked,path))

N, M = map(int,input().split())
adj = [set() for i in range(N+1)]
for i in range(M):
	u, v = map(int,input().split())
	adj[u].add(v)
	adj[v].add(u)

def good(p):
	for i in range(N-1):
		if p[i+1] not in adj[p[i]]:
			return False
	return True

ans = 0

from itertools import permutations
for p in permutations(range(2,N+1)):
	if good([1]+list(p)):
		ans += 1

print(ans)

import itertools

n,m=map(int,input().split())
emp=[[] for i in range(n)]
count=0

for i in range(m):
    a,b=map(int,input().split())
    emp[a-1].append(b-1)
    emp[b-1].append(a-1)

nlis=[i for i in range(n)]
perm=list(itertools.permutations(nlis))

for one_case in perm:
    if one_case[0]==0:
        cou=0
        for i in range(n-1):
            if one_case[i+1] in emp[one_case[i]]:
                cou+=1
            
            if cou==n-1:
                count+=1
print(count)

import itertools
N, M = map(int, input().split())
edges = [list(map(int, input().split())) for i in range(M)]#辺の集合
graph =[[] for i in range(N+1)]#隣接リスト
for edge in edges:
    graph[edge[0]].append(edge[1])
    graph[edge[1]].append(edge[0])

node = [i for i in range(1, N+1)]
per_list = list(itertools.permutations(node))#順列生成
count = 0
for l in per_list:#全ての順列について条件を満たすかどうか探索
    if l[0] != 1:#開始ノードが1じゃなかったらダメ
        continue
    flg = 0
    for i in range(len(l)-1):
        if not (l[i+1] in graph[l[i]]):#グラフの間に辺がなかったら
            flg = 1
            break
    if not flg:#フラグがたってなかったら
        count += 1

print(count)

N, M = list(map(int, input().split()))


def dfs(node):
    if sum([1 for v in visited if v]) == N:
        return 1
    ret = 0
    for n in graph[node]:
        if visited[n]:
            continue
        visited[n] = True
        ret += dfs(n)
        visited[n] = False
    return ret


graph = [[] for _ in range(N)]
for _ in range(M):
    a, b = list(map(int, input().split()))
    graph[a - 1].append(b - 1)
    graph[b - 1].append(a - 1)

visited = [False for _ in range(N)]
visited[0] = True
print((dfs(0)))


import itertools

n, m = list(map(int, input().split()))

#隣接行列
path=[[False]* n for _ in range(n)]
for i in range(m):
    a, b = list(map(int, input().split()))
    a -= 1
    b -= 1
    path[a][b] = True
    path[b][a] = True

ans = 0

for i in itertools.permutations(list(range(n))):
	#頂点１が始点
	if i[0]==0:
		# 生成した順列の中をさらにループ
		for j in range(n):
			# n - 1 まで続いたら条件を満たすパスが存在する
			if j == n-1:
				ans+=1
				break
			# i[j] から i[j + 1] に行くパスがなければ終了
			if not path[i[j]][i[j + 1]]:
				break
print(ans)


def dfs(g,v,depth):
    if seen[v]==True:return 0
    if depth==n:return 1
    seen[v] = True
    paths = 0
    for next_v in g[v]:
        paths += dfs(g,next_v,depth+1)
    seen[v] = False
    return paths
        
n,m = map(int,input().split())

g = [[]*(n+1) for _ in range(n+1)]

for _ in range(m):
    a,b = map(int,input().split())
    g[a].append(b)
    g[b].append(a)

seen = [False]*(n+1)
    
print(dfs(g,1,1))

import itertools

N,M=map(int,input().split())
s=[list(map(int,input().split())) for _ in range(M)]

lst=[x for x in range(2,N+1)]   
l=itertools.permutations(lst)

ans=0
for num in l:
	t=[1]+list(num)
	ok=True
	for j in range(N-1):
		p=sorted([t[j], t[j+1]])
		if not p in s:
			ok=False
			break
	if ok:
		ans+=1
				
print(ans)

def dfs(start,path):
    res = 0
    path.append(start)
    if len(path) == N:
        res += 1
        return res
    for i in graph[start]:
        if i not in path:
            res += dfs(i,path)
            path.pop()
    return res

N, M = map(int, input().split())
graph = [[] for _ in range(N)]
for i in range(M):
    a, b = map(int, input().split())
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)
print(dfs(0,[]))


N,M=map(int,input().split())
path_matrix=[]
for i in range(N):
    path_matrix.append([False]*N)

for i in range(M):
    a,b=map(int,input().split())
    path_matrix[a-1][b-1]=True
    path_matrix[b-1][a-1]=True
view=[False]*N

def path(x,depth):
    if view[x-1]:
        return False
    
    if depth==N-1:
        return True

    view[x-1]=True
    total_ans=0
    for i in range(N):
        if path_matrix[x-1][i]:
            total_ans+=int(path(i+1,depth+1))
    
    view[x-1]=False

    return total_ans

print(path(1,0))

#無向グラフ
from itertools import permutations
n,m=map(int,input().split())
data=[[False]*n for i in range(n)]
for i in range(m):
  a,b=map(int,input().split())
  a-=1
  b-=1
  data[a][b]=True
  data[b][a]=True
ans=0
for i in permutations(range(n),n):
  if i[0]==0:
    for j in range(n):
      if j==n-1:
        ans+=1
        break
      if not data[i[j]][i[j+1]]:
        break
print(ans)

from networkx import *
N,M = map(int,input().split())
A = [list(map(int,input().split())) for m in range(M)]
G = Graph(A)
ans = 0

for n in range(2,N+1):
  for p in all_simple_paths(G,1,n):
    if len(p)==N:
      ans+=1

print(ans)

N, M = map(int, input().split())
G = [[] for _ in range(N)]
seen = [False] * N
for i in range(M):
    a, b = map(lambda x: int(x) - 1 ,input().split())
    G[a].append(b)
    G[b].append(a)

def dfs(x, G, seen):
    seen[x] = True
    flag = True
    for i in seen:
        if i == False:
            flag = False
    if flag:
        return 1
    res = 0
    for i in G[x]:
        if seen[i]:
            continue
        res += dfs(i, G, seen)
        seen[i] = False
    return res

print(dfs(0, G, seen))

N,M=map(int, input().split())

checked = [0] * 8
path = [[] for _ in range(8)]

for i in range(M):
  a,b=map(int, input().split())
  path[a-1].append(b-1)
  path[b-1].append(a-1)

ans = 0

def dfs(place):
  checked[place] = 1
  if sum(checked) == N:
    return 1
  ret = 0
  for i in path[place]:
    if checked[i] == 1:
      continue
    ret += dfs(i)
    checked[i] = 0
  return ret

print(dfs(0))

import sys
import itertools
sys.setrecursionlimit(10**6)

N,M=list(map(int,input().split()))
tmp=[x for x in range(1,N)]
Cases=itertools.permutations(tmp)
G=[[] for _ in range(N)]
seen=[0]*N

for _ in range(M):
    a,b=list(map(int,input().split()))
    a-=1
    b-=1
    G[a].append(b)
    G[b].append(a)

def solve(v,case,cnt,N):
    if cnt==N-1: return True
    for nv in G[v]:
        if nv==case[cnt]:
            return solve(nv,case,cnt+1,N)
    return False

ans=0
for case in Cases:
    if solve(0,case,0,N): ans+=1
print(ans)


N,M = map(int,input().split())
AB = [tuple(map(int,input().split())) for i in range(M)]
es = [[0]*N for _ in range(N)]
for a,b in AB:
    a,b = a-1,b-1
    es[a][b] = es[b][a] = 1

ans = 0
import itertools
for ptn in itertools.permutations(range(1,N)):
    ptn = list(ptn)
    for a,b in zip([0]+ptn, ptn):
        if not es[a][b]: break
    else:
        ans += 1
print(ans)

N,M = list(map(int,input().split()))


#iから進める場所をリストにして保管
edges = {i:[] for i in range(1,N+1)}
for i in range(M):
  a,b = list(map(int,input().split()))
  edges[a].append(b)
  edges[b].append(a)


#深さ優先探索
def dfs(list):
    #lst(通過点)の数がN(頂点数)と等しくなったら探索終了（成功）
  if len(list) == N:
    return 1
  else:
    a = list[-1]
    #lstの最後尾（現在地）が次に進める場所をnextとしてリスト化
    #nextに以前通った場所が入っていないか確認
    next = [n for n in edges[a] if n not in list]
    #次に進める場所がなくなったら探索終了（失敗）
    if len(next) == 0:
      return 0

    total = 0
    #再帰でさらに探索
    for n in next:
      total += dfs(list + [n])

    return total


ans = dfs([1])

print(ans)


import copy


def dfs(i, path, reached, n):
    if reached[i]:
        return n
    reached[i] = True

    if all(reached):
        n += 1
        return n

    for p in path[i]:
        org_reached = copy.deepcopy(reached)
        n = dfs(p, path, org_reached, n)

    return n


def main():
    N, M = list(map(int, input().split()))
    AB = [list(map(int, input().split())) for _ in range(M)]

    path = [[] for _ in range(N)]

    for a, b in AB:
        a -= 1
        b -= 1
        path[a].append(b)
        path[b].append(a)

    reached = [False for _ in range(N)]
    n = 0

    n = dfs(0, path, reached, n)
    print(n)


main()


from itertools import permutations, islice


def window(seq, n):
    it = iter(seq)
    result = tuple(islice(it, n))
    if len(result) == n:
        yield result
    for elem in it:
        result = result[1:] + (elem,)
        yield result


N, M, *ab = list(map(int, open(0).read().split()))
g = [[0] * N for _ in range(N)]
for a, b in zip(*[iter(ab)] * 2):
    g[a - 1][b - 1] = 1
    g[b - 1][a - 1] = 1

ans = 0
for path in permutations(list(range(1, N))):
    path = [0] + list(path)
    if all(g[v][nv] for v, nv in window(path, 2)):
        ans += 1
print(ans)


from itertools import permutations


N, M, *ab = list(map(int, open(0).read().split()))
g = [[] for _ in range(N)]
for a, b in zip(*[iter(ab)] * 2):
    a -= 1
    b -= 1
    g[a].append(b)
    g[b].append(a)

ans = 0
for path in permutations(list(range(1, N))):
    v = 0
    for nv in path:
        if nv not in g[v]:
            break
        v = nv
    else:
        ans += 1
print(ans)



n, m = list(map(int, input().split()))
edges = [tuple(map(int, input().split())) for _ in range(m)]

G = [list() for _ in range(n + 1)]
for a, b in edges:
    G[a].append(b)
    G[b].append(a)

checked = [False for _ in range(n)]

ans = 0

def dfs(v):
    nonlocal ans
    if all(checked):
        ans += 1
        return
    for u in G[v]:
        if not checked[u - 1]:
            checked[u - 1] = True
            dfs(u)
            checked[u - 1] = False
    return

checked[0] = True
dfs(1)
print(ans)


N,M = [int(a) for a in input().split()]


#iから進める場所をリストにして保管
edges = {i:[] for i in range(1,N+1)}
for i in range(M):
  a,b = [int(a) for a in input().split()]
  edges[a].append(b)
  edges[b].append(a)


#深さ優先探索
def search(lst):
    #lst(通過点)の数がN(頂点数)と等しくなったら探索終了（成功）
  if len(lst) == N:
    return 1
  else:
    a = lst[-1]
    #lstの最後尾（現在地）が次に進める場所をnextとしてリスト化
    #nextに以前通った場所が入っていないか確認
    next = [n for n in edges[a] if n not in lst]
    #次に進める場所がなくなったら探索終了（失敗）
    if len(next) == 0:
      return 0

    tot = 0
    #再帰でさらに探索
    for n in next:
      tot += search(lst + [n])

    return tot


ans = search([1])

print(ans)


import itertools
n,m=map(int,input().split())
tbl=[[0]*n for _ in range(n)]
for _ in range(m):
    a,b=map(int,input().split())
    tbl[a-1][b-1]=1
    tbl[b-1][a-1]=1
ans=0
l=[i+1 for i in range(n-1)]
for p in itertools.permutations(l,n-1):
    flag=True
    p=[0]+list(p)
    for i in range(n-1):
        if tbl[p[i]][p[i+1]]==0:
            flag=False
            break
    if flag:
      ans+=1
print(ans)

N,M = list(map(int,input().split()))
G = [[] for i in range(N)]
for i in range(M):
    a,b = list(map(int,input().split()))
    G[a-1].append(b-1)
    G[b-1].append(a-1)
cnt = [0]
def dfs(V,s):
    V[s] = 1
    if sum(V) == N:
        cnt[0] += 1
    else:
        for adj in G[s]:
            if V[adj] == 0:
                dfs(V[:adj] + [1] + V[adj + 1:], adj)
dfs([0] * N,0)
print((cnt[0]))


N,M=list(map(int,input().split()))
A=[[] for i in range(N)]

for i in range(M):
    x,y=list(map(int,input().split()))
    A[x-1].append(y)
    A[y-1].append(x)

color=["W" for i in range(N)]

clear=["B" for i in range(N)]

def path(x,d):
    if color[x-1]=="B":
        return False
        
    color[x-1]="B"

    if color==clear:
        color[x-1]="W"
        return True
    
    ans=0
    for i in range(len(A[x-1])):
        ans+=int(path(A[x-1][i],d+1))

    color[x-1]="W"
    return ans

print((path(1,0)))


N,M = [int(a) for a in input().split()]
edges = {i:[] for i in range(1,N+1)}
for i in range(M):
  a,b = [int(a) for a in input().split()]
  edges[a].append(b)
  edges[b].append(a)

def search(lst):
  if len(lst) == N:
    return 1
  else:
    a = lst[-1]
    next = [n for n in edges[a] if n not in lst]
    if len(next) == 0:
      return 0

    tot = 0
    for n in next:
      tot += search(lst + [n])
    
    return tot


ans = search([1])

print(ans)

      


from itertools import permutations
from math import factorial

n, m = list(map(int, input().split(' ')))
edge = []

for i in range(m):
    ai, bi = list(map(int, input().split(' ')))
    edge.append([ai,bi])


x = [i for i in range(1,n+1)]
ls = list(permutations(x))
ans = 0
for l in range(factorial(n-1)):
    cnt = 0
    for i in range(n-1):
        for j in range(m):
            if (ls[l][i] in edge[j]) and (ls[l][i+1] in edge[j]):
                cnt += 1
    if cnt == n-1:
        ans += 1


print(ans)


import itertools as it

n, m = list(map(int, input().split()))
a = list(list(map(int, input().split())) for _ in range(m))

#print(a)

#無向グラフのルート作成（リスト）
for i in range(len(a)):
    a.append([a[i][1],a[i][0]])
#print(a)


#１を始点とするルートを全探索で作成
lis  = list(it.permutations(list(range(2, n + 1))))
#print(lis)
for i in range(len(lis)):
    lis[i] = (1,) + lis[i]
#print(lis)

#リストに変換
lis2 = []
for i in range(len(lis)):
    lis[i] = list(lis[i])
    lis2.append(lis[i])
#print(lis2)

#ルート探索
#lis3 = []
ans = 0
for i in range(len(lis2)):
    check = True
    for j in range(len(lis2[i]) - 1):
        if lis2[i][j : j + 2] not in a:
            check = False
    if check:
        ans += 1
print(ans)


N,M = list(map(int,input().split()))


#iから進める場所をリストにして保管
edges = {i:[] for i in range(1,N+1)}
for i in range(M):
  a,b = [int(a) for a in input().split()]
  edges[a].append(b)
  edges[b].append(a)


#深さ優先探索
def dfs(list):
    #lst(通過点)の数がN(頂点数)と等しくなったら探索終了（成功）
  if len(list) == N:
    return 1
  else:
    a = list[-1]
    #lstの最後尾（現在地）が次に進める場所をnextとしてリスト化
    #nextに以前通った場所が入っていないか確認
    next = [n for n in edges[a] if n not in list]
    #次に進める場所がなくなったら探索終了（失敗）
    if len(next) == 0:
      return 0

    total = 0
    #再帰でさらに探索
    for n in next:
      total += dfs(list + [n])

    return total


ans = dfs([1])

print(ans)


N, M = map(int, input().split())
Edge = [tuple(map(int, input().split())) for _ in range(M)]

Graph = [[] for _ in range(N)]
for a,b in Edge:
    Graph[a-1].append(b-1)
    Graph[b-1].append(a-1)

seen = set()
def dfs(v):
    seen.add(v)
    if len(seen) == N:
        seen.remove(v)
        return 1
    Res = [dfs(nv) for nv in Graph[v] if not nv in seen]
    seen.remove(v)
    return sum(Res)

print(dfs(0))

N, M = map(int, input().split())
D = {}
for i in range(M):
  a, b = map(int, input().split())
  if a not in D:
    D[a] = set()
  if b not in D:
    D[b] = set()
  D[a].add(b)
  D[b].add(a)
if 1 not in D or len(D) != N:
  print(0)
else:
  S = set(D.keys())
  ans = 0
  task = [(1, set())]
  while len(task) > 0:
    pos = 0
    log = set()
    pos, log = task.pop(0)
    log.add(pos)
    for i in D[pos]:
      if i not in log:
        task.append((i, log.copy()))
    else:
      if log == S:
        ans += 1
  print(ans)

from typing import List, Tuple


def main():
    n, m = list(map(int, input().split()))
    g = []
    for _ in range(m):
        a, b = list(map(int, input().split()))
        g.append((a, b))
    print((osp(n, g)))


def osp(n: int, g: List[Tuple[int, int]]) -> int:
    v = [False] * n

    return dfs(0, v, n, g)


def dfs(i, v, n, g):
    v[i] = True
    if all(v):
        v[i] = False
        return 1

    cnt = 0
    for j in range(n):
        if v[j]:
            continue
        if not ((i + 1, j + 1) in g or (j + 1, i + 1) in g):
            continue
        cnt += dfs(j, v, n, g)

    v[i] = False
    return cnt


def __starting_point():
    main()

__starting_point()

import itertools
n,m=list(map(int,input().split()))
num=[[] for _ in range(n)]
for i in range(m):
    a,b=list(map(int,input().split()))
    num[a-1].append(b)
    num[b-1].append(a)
cnt=list(itertools.permutations(list(range(2,n+1))))
ans=0
for i in range(len(cnt)):
    num1=1
    num2=cnt[i]
    yn=0
    for j in range(n-1):
        if num2[j] not in num[num1-1]:
            yn=1
            break
        num1=num2[j]
    if yn==0:
        ans+=1
print(ans)


from collections import defaultdict
N, M = list(map(int, input().split()))
d = defaultdict(list)
for _ in range(M):
    a, b = list(map(int, input().split()))
    d[a].append(b)
    d[b].append(a)


def dfs(n, path):
    count = 0
    path.append(n)
    if len(path) == N:
        count += 1
        return count

    for i in range(len(d[n])):
        if d[n][i] not in path:
            count += dfs(d[n][i], path)
            path.pop()

    return count


print((dfs(1, [])))


#Nはノード数、Mはエッジ数
N, M = map(int, input().split())

path_matrix = []

#無向行列の初期化
for n in range(N):
    path_matrix.append([False] * N)

#まず無向グラフを表す行列を作る
for m in range(M):
    line = map(int, input().split())
    paths = [x - 1 for x in line]
    path_matrix[paths[0]][paths[1]] = True
    path_matrix[paths[1]][paths[0]] = True

#最初はvisited、つまり訪問したことのあるノードはひとつもないので、Falseにする
visited = [False] * N


#再帰関数、ここが難しいかもしれない。
def dfs(now, depth):
    if visited[now]:
        return 0
    if depth == N - 1:
        return 1

    visited[now] = True
    total_paths = 0
    for i in range(0, N):
        if path_matrix[now][i]:
            total_paths += dfs(i, depth + 1)

    visited[now] = False

    return total_paths

print(dfs(0, 0))

def OneStrokePath():
    from collections import deque
    import copy
    n, m = list(map(int, input().split()))
    graph = [[] for _ in range(n)]
    ans = 0
    
    for _ in range(m):
        a, b = list(map(int, input().split()))
        graph[a-1].append(b-1)
        graph[b-1].append(a-1)
    q = deque()
    q.append([0, []])
        
    while q:
        x0, route0 = q.pop()
        if x0 in route0:
            continue
        route1 = copy.deepcopy(route0)
        route1.append(x0)
        if len(route1) == n:
            ans += 1
        for i in graph[x0]:
            if i in route1:
                continue
            q.append([i, route1])
    print(ans)  

def __starting_point():
    OneStrokePath()
    

__starting_point()

import queue 
n,m = map(int, input().split())

ma = [[] for i in range(n+1)]
for i in range(m):
  a,b = map(int, input().split())
  ma[a].append(b)
  ma[b].append(a)

ans = 0
def dfs(i):
  nonlocal ans
  if all(reach[1:]):
    ans += 1
  for j in ma[i]:
    if reach[j] == 1:
      continue
    reach[j] = 1
    dfs(j)
    reach[j] = 0

reach=[0]*(n+1)
reach[1] = 1
dfs(1)
print(ans)

import itertools
N,M = map(int,input().split())

g = [[] for _ in range(N)]
for _ in range(M):
  a,b = map(int,input().split())
  g[a-1].append(b-1)
  g[b-1].append(a-1)

p = list(itertools.permutations(range(0,N)))

ans = 0
for pair in p:
  if pair[0] != 0:
    continue
  ok = True
  for node1, node2 in zip(pair[0:],pair[1:]):
    if node1 not in g[node2]:
      ok = False
      break
  if ok:
    ans += 1

print(ans)

#グラフのパスを全探索する関数(再帰)
def dfs(now_node, depth):#deptt:今まで列挙した頂点数
    if seen[now_node]:#探索済みであった場合はreturn
        return 0
    if depth == N:#全ての頂点を通っていた場合、1を返す
        return 1
    seen[now_node] = True  #今から探索するノードを探索済みにする
    connect_nodes = graph[now_node]
    ans = 0
    for node in connect_nodes:#全ての遷移先をチェックする
        ans += dfs(node, depth+1)
    seen[now_node] = False  # 探索済みフラグを折る(ポイント)
    return ans

N, M = map(int, input().split())
edges = [list(map(int, input().split())) for i in range(M)]#辺の集合
graph =[[] for i in range(N+1)]#隣接リスト
for edge in edges:
    graph[edge[0]].append(edge[1])
    graph[edge[1]].append(edge[0])

#訪問済みかどうかを表すリストを用意
seen = [False for i in range(N+1)]
seen[0] = True

print(dfs(1, 1))

from itertools import permutations
N, M = map(int, input().split())
AB = [tuple(map(int, input().split())) for _ in range(M)]
m = [set() for _ in range(27)]
for a, b in AB:
    m[a].add(b)
    m[b].add(a)

def main():
    ans = []
    def traverse(n, visits):
        visits = visits | set([n])
        if len(visits) == N:
            ans.append(1)
            return
        for c in m[n] - visits:
            traverse(c, visits)
    traverse(1, set())
    return len(ans)

print(main())

from typing import List, Tuple


def main():
    n, m = list(map(int, input().split()))
    g = []
    for _ in range(m):
        a, b = list(map(int, input().split()))
        g.append((a, b))
    print((osp(n, g)))


def osp(n: int, g: List[Tuple[int, int]]) -> int:
    v = [False] * n
    g = set(g)

    return dfs(0, v, n, g)


def dfs(i, v, n, g):
    v[i] = True
    if all(v):
        v[i] = False
        return 1

    cnt = 0
    for j in range(n):
        if v[j]:
            continue
        if not ((i + 1, j + 1) in g or (j + 1, i + 1) in g):
            continue
        cnt += dfs(j, v, n, g)

    v[i] = False
    return cnt


def __starting_point():
    main()

__starting_point()

def abc054c_one_stroke_path():
    import itertools
    n, m = map(int, input().split())
    e = [set() for _ in range(n + 1)]
    for _ in range(m):
        a, b = map(int, input().split())
        e[a].add(b)
        e[b].add(a)
    pattern = itertools.permutations(range(2, n + 1))
    cnt = 0
    for p in pattern:
        p_m = [1] + list(p)
        for i in range(n - 1):
            if p_m[i+1] not in e[p_m[i]]:
                break
        else:
            cnt += 1
    print(cnt)


abc054c_one_stroke_path()

import collections
import copy

def dfs(i,basho,memo):
    nonlocal ans
    #print(i,basho,memo)
    if memo[basho]==1:
        return
    memo[basho]=1
    if i == n:
        if sum(memo)==n:
            ans += 1
        return
    tmp = collections.Counter(graph[basho])
    #print(tmp)
    for next_basho in tmp.keys():
        copy_memo = copy.copy(memo)
        dfs(i+1,next_basho,copy_memo)

n,m = map(int,input().split())
graph = [[] for i in range(n+1)]
for i in range(m):
    a,b = map(int,input().split())
    graph[a].append(b)
    graph[b].append(a)

memo = [0 for i in range(n+1)]
ans = 0
dfs(1,1,memo)
print(ans)

from itertools import permutations

N,M = list(map(int, input().split()))
l = [list(map(int, input().split())) for _ in range(M)]

graph = [[False]*(N+1) for _ in range(N+1)]

for i,j in l:
    graph[i][j] = True
    graph[j][i] = True

pattern = permutations(list(range(1,N+1)))

cnt = 0
for i in pattern:
    flag = True
    if i[0] != 1:
        continue
    for j in range(N-1):
        if graph[i[j]][i[j+1]] == False:
            flag = False
            break
    
    if flag:
        cnt += 1

print(cnt)


n,m = map(int,input().split())
visit = [False]*n
r = [[] for _ in range(n)]
for i in range(m):
  a,b = map(lambda x:int(x)-1,input().split())
  r[a].append(b)
  r[b].append(a)
def dfs(x,v):
  if v[x]:
    return
  v = list(v)
  v[x] = True
  if all(v):
    nonlocal ans
    ans += 1
    return
  for y in r[x]:
    dfs(y,v)
ans = 0
dfs(0,[False]*n)
print(ans)

import itertools
from collections import deque

N,M = map(int,input().split())
table = [[0]*N for _ in range(N)]
ans = 0
for i in range(M):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    table[a][b] = 1
    table[b][a] = 1

p = [i for i in range(1,N)]
q = list(itertools.permutations(p))

s = deque()
for i in range(len(q)):
    x = 0
    flag = 0
    for y in q[i]:
        if table[x][y] == 0:
            flag = 1
            break
        x = y
    if flag == 0:
        ans += 1

print(ans)

import itertools
n,m = list(map(int,input().split()))
routes = list(itertools.permutations([i for i in range(2,n+1)]))
nodes = {}
ans = 0
for i in range(1,n+1):
    nodes[i] = []
for _ in range(m):
    a,b = list(map(int,input().split()))
    nodes[a].append(b)
    nodes[b].append(a)
for i in range(len(routes)):
    jud = 1
    if routes[i][0] not in nodes[1]:
        jud = 0
    for j in range(n-2):
        if routes[i][j+1] not in nodes[routes[i][j]]:
            jud = 0
    ans += jud
print(ans)


import sys


def dfs(A: list):
    if len(A) == n:
        for i in range(len(A)-1):
            if A[i+1] not in node[A[i]]:
                break
            if i == n-2:
                ans[0] += 1
        return
    for v in range(2, n+1):
        if v not in A:
            A.append(v)
            dfs(A)
            A.pop()


n, m = list(map(int, input().split()))
node = [set() for _ in range(n+1)]
for x in sys.stdin.readlines():
    a, b = list(map(int, x.split()))
    node[a].add(b)
    node[b].add(a)
ans = [0]
dfs([1])
print((ans[0]))


from itertools import permutations


N, M = map(int, input().split())
S = []
for i in range(M):
    a, b = map(int, input().split())
    S.append([a, b])
    
vertex = (i+1 for i in range(N))
all_path = list(permutations(vertex))

ans = 0
for p in all_path:
    flag = True
    if p[0] == 1:
        for i in range(N-1):
            if [p[i], p[i+1]] not in S and [p[i+1], p[i]] not in S:
                flag = False
                break
        if flag:
            ans += 1
                
print(ans)

#
# abc054 c
#

import sys
from io import StringIO
import unittest
import itertools


class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)

    def test_入力例_1(self):
        input = """3 3
1 2
1 3
2 3"""
        output = """2"""
        self.assertIO(input, output)

    def test_入力例_2(self):
        input = """7 7
1 3
2 7
3 4
4 5
4 6
5 6
6 7"""
        output = """1"""
        self.assertIO(input, output)


def resolve():
    N, M = list(map(int, input().split()))
    P = [list(map(int, input().split())) for _ in range(M)]

    R = itertools.permutations(list(range(1, N+1)))

    ans = 0
    for r in R:
        flag = True
        r = list(r)
        if r[0] != 1:
            break
        for i in range(1, N):
            for p in P:
                if (r[i-1] == p[0] and r[i] == p[1]) or (r[i-1] == p[1] and r[i] == p[0]):
                    break
            else:
                flag = False
        if flag == True:
            ans += 1

    print(ans)


def __starting_point():
    # unittest.main()
    resolve()

__starting_point()

import itertools as it
n,m=map(int,input().split())
e=[[0 for i in range(n)] for j in range(n)]
for i in range(m):
  a,b=map(lambda x:int(x)-1,input().split())
  e[a][b]=1
  e[b][a]=1

c=0
for t in it.permutations([j+1 for j in range(n-1)]):
  i=(0,)+t
  c+=1
  for j in range(n-1):
    if e[i[j]][i[j+1]]==0:
      c-=1
      break
print(c)

# coding: utf-8
# Your code here!

import itertools

N, M = list(map(int, input().split()))

graph= [[False]*N for i in range(N)]

for i in range(M):
    a, b = [int(x)-1 for x in input().split()]
    graph[a][b] = True
    graph[b][a] = True

lst = [i-1 for i in range(N)]
cnt = 0

for v in itertools.permutations(lst, N):
    if v[0] != 0:
        continue
    for i in range(N-1):
        if graph[v[i]][v[i+1]] == False:
            break
        if i == N-2:
            cnt += 1

print(cnt)









N, M = map(int, input().split())
to = [[] for i in range(N)]

for i in range(M):
    a, b = map(int, input().split())
    to[a-1].append(b-1)
    to[b-1].append(a-1)

ans = 0
v = [0] * N

def DFS(n):
    nonlocal ans
    v[n] = 1
    #print(v)
    if sum(v) == N:
        ans += 1
    for i in to[n]:
        if v[i] == 0:
            DFS(i)
    v[n] = 0

DFS(0)
print(ans)

from typing import List, Tuple


def main():
    n, m = list(map(int, input().split()))
    g = []
    for _ in range(m):
        a, b = list(map(int, input().split()))
        g.append((a, b))
    print((osp(n, g)))


def osp(n: int, g: List[Tuple[int, int]]) -> int:
    graph = [[False] * n for _ in range(n)]
    for a, b in g:
        graph[a - 1][b - 1] = True
        graph[b - 1][a - 1] = True
    v = [False] * n

    return dfs(0, v, n, graph)


def dfs(i, v, n, graph):
    v[i] = True
    if all(v):
        v[i] = False
        return 1

    cnt = 0
    for j in range(n):
        if v[j]:
            continue
        if not graph[i][j]:
            continue
        cnt += dfs(j, v, n, graph)

    v[i] = False
    return cnt


def __starting_point():
    main()

__starting_point()

import itertools

N,M = map(int,input().split())
adj_matrix = [[0] * N for _ in range(N)]

for i in range(M):
    a,b = map(int,input().split())
    adj_matrix[a-1][b-1] = 1
    adj_matrix[b-1][a-1] = 1
    
cnt = 0

for each in itertools.permutations(range(N)):
    if each[0] != 0:
        break
    factor = 1
    for i in range(N-1):
        factor *= adj_matrix[each[i]][each[i+1]]
    cnt += factor

print(cnt)

def dfs(x, l):
  if l.count(False) == 0:
    return 1
  cnt = 0
  for i in a[x]:
    if not l[i]:
      cnt += dfs(i, [[True] if j == i else l[j] for j in range(n)])
  return cnt

n, m = map(int, input().split())
a = [[] for i in range(n)]
for i in range(m):
  x = list(map(int, input().split()))
  a[x[0]-1].append(x[1]-1)
  a[x[1]-1].append(x[0]-1)
print(dfs(0, [True]+[False]*(n-1)))

N,M = [int(a) for a in input().split()]


#iから進める場所をリストにして保管
edges = {i:[] for i in range(1,N+1)}
for i in range(M):
  a,b = [int(a) for a in input().split()]
  edges[a].append(b)
  edges[b].append(a)


#深さ優先探索
def dfs(list):
    #lst(通過点)の数がN(頂点数)と等しくなったら探索終了（成功）
  if len(list) == N:
    return 1
  else:
    a = list[-1]
    #lstの最後尾（現在地）が次に進める場所をnextとしてリスト化
    #nextに以前通った場所が入っていないか確認
    next = [n for n in edges[a] if n not in list]
    #次に進める場所がなくなったら探索終了（失敗）
    if len(next) == 0:
      return 0

    total = 0
    #再帰でさらに探索
    for n in next:
      total += dfs(list + [n])

    return total


ans = dfs([1])

print(ans)


from itertools import permutations


N, M, *ab = list(map(int, open(0).read().split()))
g = [[0] * N for _ in range(N)]
for a, b in zip(*[iter(ab)] * 2):
    g[a - 1][b - 1] = 1
    g[b - 1][a - 1] = 1

ans = 0
for path in permutations(list(range(1, N))):
    path = [0] + list(path)
    if all(g[v][nv] for v, nv in zip(path, path[1:])):
        ans += 1
print(ans)


import sys
readline = sys.stdin.readline

N,M = map(int,readline().split())
G = [[] for i in range(N)]

for i in range(M):
  a,b = map(int,readline().split())
  G[a - 1].append(b - 1)
  G[b - 1].append(a - 1)

stack = []
stack.append([0, set()])
ans = 0
while stack:
  v, visited = stack.pop()
  visited.add(v)
  if len(visited) == N:
    ans += 1
    continue
  for child in G[v]:
    if child in visited:
      continue
    visited_c = visited.copy()
    stack.append([child, visited_c])
  
print(ans)

def dfs(v):
    if sum(visited) == N:
        return 1
    res = 0
    for nv in g[v]:
        if visited[nv]:
            continue
        visited[nv] = 1
        res += dfs(nv)
        visited[nv] = 0
    return res


N, M, *ab = list(map(int, open(0).read().split()))
g = [[] for _ in range(N)]
for a, b in zip(*[iter(ab)] * 2):
    a -= 1
    b -= 1
    g[a].append(b)
    g[b].append(a)

visited = [0] * N
visited[0] = 1
print((dfs(0)))



import itertools as itt

n, m = map(int, input().split())
l = set()
for i in range(m):
    a, b = map(int, input().split())
    l.add((a, b))
    l.add((b, a))

lis = [i for i in range(1, n+1)]
p_lis = list(itt.permutations(lis))

cnt = 0

for i in range(len(p_lis)):
    if p_lis[i][0] != 1:
        continue
    flg = [0]*(n-1)
    for j in range(n-1):
        x = (p_lis[i][j], p_lis[i][j+1])
        if x in l:
            flg[j] = 1
    if all(flg):
        cnt += 1

print(cnt)

n,m=list(map(int,input().split()))
#隣接リスト表現
es=[[0 for i in range(n)] for i in range(n)]
for i in range(m):
  a,b=list(map(int,input().split()))
  es[a-1][b-1]=1
  es[b-1][a-1]=1

# 再帰の深さが1000を超えそうなときはこれをやっておく
import sys
sys.setrecursionlimit(10**7)


#深さ優先探索
#n個の頂点が未探索であるとしておく
visited=[0 for i in range(n)]
check=[1 for i in range(n)]

def dfs(v,visited):
  #ansは頂点vから始まるパスの数
  ans=0
  #自分がいることろを探索済にしておく
  visited[v-1]=1

  if visited==check:
    visited[v-1]=0
    return 1
  #そこから行けるところに対して深さ優先探索
  for i in range(n):
    #つながっていて未探索
    if es[v-1][i]==1 and visited[i]==0:
        ans+=dfs(i+1,visited)
  #全部探索し終わったら今自分がいるところは未探索に戻しておく
  visited[v-1]=0
  return ans

print((dfs(1,visited)))


import itertools

n, m = map(int, input().split())

#繋がっている頂点リスト
a_list = []
for j in range(m) :
    a = list(map(int, input().split()))
    a_list.append(a)
a_list.sort()

#道順リスト(最初が1に限る)
b_list = [k for k in itertools.permutations([l for l in range(1, n + 1)]) if k[0] == 1]

#道順リストの中で頂点リストが含まれているもの
cnt = 0
for x in b_list :
    tf_list = []
    for y in range(n - 1) :
        tf_list.append([x[y], x[y + 1]] in a_list or [x[y + 1], x[y]] in a_list)
    
    if all(tf_list) == True :
        cnt += 1

print(cnt)

import sys, itertools

load = []
for i,row in enumerate(sys.stdin.readlines()):
    if i == 0:
        n,m = [int(x) for x in row.split()]
    else:
        load.append({int(x) for x in row.split()})

sum = 0
for one_load in itertools.permutations([i for i in range(1,n+1)]):
    #print("one_load:",one_load)
    if one_load[0] != 1:
        continue
    else:
        for i,dot in enumerate(one_load):
            if i == 0:
                old_dot = dot
            else:
              #  print("old_dot,dot:",old_dot,dot)
                if {old_dot,dot} in load:
                    old_dot = dot
                else:
                    break
        else:
            sum += 1
print(sum)

N,M = [int(a) for a in input().split()]
edges = {i:[] for i in range(1,N+1)}
for i in range(M):
  a,b = [int(a) for a in input().split()]
  edges[a].append(b)
  if a not in edges[b]:
    edges[b].append(a)

def search(lst):
  if len(lst) == N:
    return 1
  else:
    a = lst[-1]
    next = [n for n in edges[a] if n not in lst]
    if len(next) == 0:
      return 0

    tot = 0
    for n in next:
      tot += search(lst + [n])
    
    return tot


ans = search([1])

print(ans)



import copy
from collections import deque

n, m = map(int,input().split())

e = [[] for i in range(n)]
for i in range(m):
    a, b = map(int,input().split())
    a -= 1
    b -= 1
    e[a].append(b)
    e[b].append(a)
visited = [False]*n
visited[0] = True
d = deque([[0, visited]])

cnt = 0
while d:
    f, visited = d.pop()
    for t in e[f]:
        v = copy.deepcopy(visited)
        if not v[t]:
            v[t] = True
            if False in v:
                d.append([t, v])
            else:
                cnt += 1
print(cnt)

from collections import deque

n,m = list(map(int, input().split()))
g = [[] for _ in range(n)]
prev = [0] * n

for i in range(m):
    a,b = list(map(int, input().split()))
    g[a-1].append(b)
    g[b-1].append(a)

count = 0
prev[0] = 1

def keiro(pre,q,now):
    nonlocal count
    if len(q) == 0:
            return

    now = q.popleft()
    
    for no in g[now-1]:
        if pre[no-1] == 0:

            pre_1 = pre.copy()
            pre_1[no-1] = 1
            if sum(pre_1) == n:
                count+=1
                return
            q.append(no)
            keiro(pre_1,q,no)
        else:

            keiro(pre,q,no)


keiro(prev,deque([1]),1)
print(count)



import itertools 

n,m=map(int,input().split())
li=[]
for _ in range(m):
  a,b=map(int,input().split())
  li.append([a,b])
count=0
for comb in itertools.permutations(range(n),n):
  if comb[0]!=0:
    continue
  judge=True
  for i in range(n-1):
    if judge==False:
      break
    a=comb[i]+1
    b=comb[i+1]+1
    if ([a,b] in li) or ([b,a] in li):
      continue
    else:
      judge=False
      break
  if judge==True:
    count+=1
print(count)

N,M = map(int, input().split())
li = []
for i in range(N):
 li.append([-1 for i in range(N)])

for i in range(M):
    a,b = map(int, input().split())
    li[a-1][b-1] = 1
    li[b-1][a-1] = 1
import itertools
an = 0
for i in itertools.permutations(range(1,N)):
  jun = [0]
  jun+= list(i)
  st = jun[0]
  for t in range(1,N):
      if li[jun[t]][st] == -1:
          break
      st = jun[t]
      if t == N-1:
          an += 1
print(an)

from itertools import permutations

N,M = map(int,input().split())
AB = [0 for i in range(M)]

for i in range(M):
  ab = list(map(int,input().split()))
  AB[i] = ab

count = 0
nums = [i for i in range(1,N+1)]
pers =permutations(nums,N)
for i in pers:
  if i[0] == 1:
    flag1 = 0
    for j in range(N-1):
      flag2 = False
      for k in range(M):
        if (i[j] == AB[k][0] and i[j+1] == AB[k][1]) or (i[j] == AB[k][1] and i[j+1] == AB[k][0]):
          flag2 = True
          #print(i,i[j],i[j+1],AB[k])
      if flag2:
        flag1 += 1
    if flag1 == N-1:
      #print(i)
      count += 1
print(count)

import itertools as it

n, m = list(map(int, input().split()))
a = list(list(map(int, input().split())) for _ in range(m))

#無向グラフのルート作成（リスト）
for i in range(len(a)):
    a.append([a[i][1],a[i][0]])

lis  = list(it.permutations(list(range(2, n + 1))))
for i in range(len(lis)):
    lis[i] = (1,) + lis[i]

lis2 = []
for i in range(len(lis)):
    lis[i] = list(lis[i])
    lis2.append(lis[i])

#ルート探索
ans = 0
for i in range(len(lis2)):
    check = True;
    for j in range(len(lis2[i]) - 1):
        if lis2[i][j : j + 2] not in a:
            check = False;
    if(check):
        ans += 1
print(ans)


import itertools

n, m = map(int, input().split())
path = [[False] * n for _ in range(n)]
for i in range(m):
    a, b = map(int, input().split())
    path[a-1][b-1] = True
    path[b-1][a-1] = True

ans = 0

for i in itertools.permutations(range(n), n):  #iterools.permutations(list, size)
    # 頂点は0か？
    if i[0] == 0:  # 頂点は１ではないことに注意
        for j in range(n):
            if j == n-1:
                ans += 1
                break
            if not path[i[j]][i[j+1]]:
                break

print(ans)

import itertools
 
N,M=map(int,input().split())
s=[list(map(int,input().split())) for _ in range(M)]
 
lst=[x for x in range(1,N+1)]   
l=itertools.permutations(lst)
 
ans=0
cnt=0
for num in l:
	if num[0]==1:
		for j in range(N-1):
			if [num[j], num[j+1]] in s or [num[j+1], num[j]] in s:
				cnt+=1
	if cnt==N-1:
		ans+=1
		cnt=0
	else:
		cnt=0
 
print(ans)

from itertools import groupby, accumulate, product, permutations, combinations
import numpy as np
N, M = map(int, input().split())
adj = np.zeros((N,N),np.int64)
for i in range(M):
  a,b = map(lambda x:int(x)-1, input().split())
  adj[a,b] = 1
  adj[b,a] = 1
ans = 0
for per in permutations(range(1,N),N-1):
  if adj[0,per[0]]==0:
    continue
  for i in range(N-2):
    if adj[per[i],per[i+1]]==0:
      break
  else:
    ans += 1
print(ans)

N, M = list(map(int, input().split()))
to = [[] for _ in range(N)]

for _ in range(M):
    a, b = list(map(int, input().split()))
    a, b = a - 1, b - 1
    to[a].append(b)
    to[b].append(a)


def dfs(v, seen):
    if seen == [1] * N:
        return 1
    
    res = 0
    for nv in to[v]:
        if not seen[nv]:
            seen[nv] = 1
            res += dfs(nv, seen)
            seen[nv] = 0
    return res


def main():
    seen = [0] * N
    seen[0] = 1
    print((dfs(0, seen)))    


def __starting_point():
    main()

__starting_point()

import sys
sys.setrecursionlimit(10 ** 6)

N, M = list(map(int, input().split()))
graph = [[] for _ in range(N)]
for i in range(M):
    a, b = [int(x) - 1 for x in input().split()]
    graph[a].append(b)
    graph[b].append(a)
def dfs(cur, visited):
    if visited == (1 << N) - 1:
        return 1
    res = 0
    for to in graph[cur]:
        if not (visited >> to) & 1:
            res += dfs(to, visited | (1 << to))
    return res
print((dfs(0, 1)))


def dfs(v, used):
  if not False in used: return 1
  ans = 0
  for i in range(n):
    if not matrix[v][i]: continue
    if used[i]: continue
    used[i] = True
    ans += dfs(i, used)
    used[i] = False
  return ans

n, m = map(int, input().split())
matrix = [[0]*n for _ in range(n)]
for i in range(m):
  a, b = map(int, input().split())
  matrix[a-1][b-1] = 1
  matrix[b-1][a-1] = 1

used = [False]*n
used[0] = True

print(dfs(0, used))

n,m=list(map(int,input().split()))
root=[[] for _ in range(n+1)]
for i in range(m):
    a,b=list(map(int,input().split()))
    root[a].append(b)
    root[b].append(a)
s=[0]*(n+1)
s[0]=1
s[1]=1
ans=0
def f(a,x):
    nonlocal ans
    for i in root[a]:
        if x[i]==0:
            x[i]=1
            f(i,x)
            x[i]=0
    if x.count(1)==n+1:
        ans+=1
f(1,s)
print(ans)



N, M = map(int, input().split())
Edge = [tuple(map(int, input().split())) for _ in range(M)]

Graph = [[] for _ in range(N)]
for a,b in Edge:
    Graph[a-1].append(b-1)
    Graph[b-1].append(a-1)

seen = set()
def dfs(v):
    nonlocal Graph, seen
    seen.add(v)
    if len(seen) == N:
        seen.remove(v)
        return 1
    Res = [dfs(nv) for nv in Graph[v] if not nv in seen]
    seen.remove(v)
    return sum(Res)

print(dfs(0))

"""
1 ----- 2 ----- ai ----- bi -----
                    辺:i
"""
import itertools

def one_stroke_path():
    """
    N : 頂点
    M : 辺数
    ai, bi : 辺iの両端の頂点
    """
    # 入力
    N, M = list(map(int, input().split()))
    a = list()
    b = list()
    for _ in range(M):
        A, B = list(map(int, input().split()))
        a.append(A)
        b.append(B)
    
    # 処理
    permutations_list = itertools.permutations([x for x in range(1,N+1)])
    count = 0
    for one_case in permutations_list:
        is_ok = False
        if one_case[0] == 1:
            for i in range(len(one_case)-1):
                for j in range(M):
                    if (one_case[i] == a[j] and one_case[i+1] == b[j]) or (one_case[i] == b[j] and one_case[i+1] == a[j] ):
                        is_ok = True
                        break
                    else:
                        is_ok = False
                if is_ok == False:
                    break
        else:
            is_ok = False
        if is_ok:
            count += 1
    return count

result = one_stroke_path()
print(result)



from itertools import permutations

N, M = map(int, input().split())
edges = set(tuple(map(int, input().split())) for _ in range(M))

ans = 0
for t in permutations(range(2, N + 1)):
    p = [1] + list(t)
    ok = True
    for i in range(N - 1):
        e = tuple(sorted((p[i], p[i + 1])))
        if not (e in edges):
            ok = False
            break
    if ok:
        ans += 1

print(ans)

import itertools
n, m = map(int, input().split())
path = [[False] * n for i in range(n)]
for i in range(m):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    path[a][b] = True
    path[b][a] = True
ans = 0
# 頂点を並び替える順列を生成してループ
for i in itertools.permutations(range(n), n):
    # 頂点1が始点
    if i[0] == 0:
        # 生成した順列の中をさらにループ
        for j in range(n):
            # n - 1 まで続いたら条件を満たすパスが存在する
            if j == n - 1:
                ans += 1
                break
            # i[j] から i[j + 1] に行くパスがなければ終了
            if not path[i[j]][i[j + 1]]:
                break
print(ans)

import itertools as it
n,m=map(int,input().split())
e=[[0 for i in range(n)] for j in range(n)]
for i in range(m):
  a,b=map(lambda x:int(x)-1,input().split())
  e[a][b]=1
  e[b][a]=1
 
c=0
for t in it.permutations([j+1 for j in range(n-1)]):
  i=(0,)+t
  c+=1
  for j in range(n-1):
    if e[i[j]][i[j+1]]==0:
      c-=1
      break
print(c)

import itertools

n,m = map(int,input().split())

path = [[False]*n for i in range(n)]
for i in range(m):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    path[a][b] = True
    path[b][a] = True

ans = 0

for i in itertools.permutations(range(n),n):
    #頂点が0のものだけ抽出
    if i[0] == 0:
        #確かめる
        for j in range(n):
            if j == n - 1:
                ans += 1
                break

            if not path[i[j]][i[j+1]]:
                break

print(ans)

from itertools import permutations

N,M = map(int,input().split())
Alist = [list(map(int,input().split())) for i in range(M)]

graph = [[False]*(N+1) for i in range(N+1)]

for i ,j in Alist:
  graph[i][j] = True
  graph[j][i] = True

route = permutations(range(1,N+1))

count = 0
for i in route:
  flag = True
  if i[0] !=1:
    continue
  for j in range(N-1):
    if graph[i[j]][i[j+1]] == False:
      flag = False
      break
  
  if flag == True:
    count += 1

print(count)

from itertools import permutations

n,m = map(int,input().split())
v = [set() for _ in range(n)]
for i in range(m):
    ai,bi = map(int,input().split())
    v[ai-1].add(bi-1)
    v[bi-1].add(ai-1)

ans = 0
for ci in permutations(range(n)):
    if not ci[0]:
        for i in range(n-1):
            if not (ci[i+1] in v[ci[i]]):
                break
        else:
            ans += 1
print(ans)

N,M = map(int,input().split())

path = [[0]*(N+1) for _ in range(N+1)]

for i in range(M):
    a,b = map(int,input().split())
    path[a][b] = 1
    path[b][a] = 1

visited = [0]*(N+1)

def dfs(now,depth):
    if visited[now]:
        return 0
    if depth == N:
        return 1 # 最後まで探索したらはじめて+1
    
    visited[now] = 1
    
    total_paths = 0
    
    for i in range(1,N+1):
        if path[now][i]:
            total_paths += dfs(i, depth + 1)
            
    visited[now] = 0
    
    return total_paths

print(dfs(1,1))

from itertools import permutations

N, M = map(int, input().split())
G = [[] for _ in range(N)]
for _ in range(M):
    a, b = map(int, input().split())
    a, b = a - 1, b - 1
    G[a].append(b)
    G[b].append(a)

res = 0
for P in permutations(range(N), N):
    if P[0] != 0:
        continue
    for i in range(N - 1):
        if P[i + 1] not in G[P[i]]:
            break
    else:
        res += 1

print(res)