Problem:
 Score : 300 points    Problem 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.    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 1 3 3
1 2
1 3
2 3      Sample Output 1 2  The given graph is shown in the following figure:     The following two paths satisfy the condition:          Sample Input 2 7 7
1 3
2 7
3 4
4 5
4 6
5 6
6 7      Sample Output 2 1  This test case is the same as the one described in the problem statement.

Solution (Python):
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
mod2 = 998244353
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpln(n): return list(int(sys.stdin.readline()) for i in range(n))

n,m = inpl()
g = [[False for j in range(n)] for i in range(n)]
for i in range(m):
    a,b = inpl()
    a -= 1
    b -= 1
    g[a][b] = True
    g[b][a] = True

res = 0
for flag in itertools.permutations(range(1,n)):
    
    for i in range(n-1):
        if i == 0:
            if not g[0][flag[0]]:
                break
            continue
        if not g[flag[i]][flag[i-1]]:
            break
    else:
        res += 1
print(res)

Solution (Python):
n,m=map(int,input().split())
g=[[] for _ in range(n)]
cnt=[0]
for _ in range(m):
    a,b=map(int,input().split())
    g[a-1].append(b-1)
    g[b-1].append(a-1)
def dfs(z,s):
    if sum(z)==n:
        cnt[0]+=1
    else:
        for i in g[s]:    
            if z[i]==0:
                dfs(z[:i]+[1]+z[i+1:],i)

dfs([1]+[0]*(n-1),0)
print(*cnt)

Solution (Python):



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

graph = [[] * N for _ in range(N)]
for i in range(M):
    u, v = map(int, input().split())
    u -= 1
    v -= 1
    graph[u].append(v)
    graph[v].append(u)


num_lst = [_ for _ in range(0, N)]
search_list = itertools.permutations(num_lst)

ans = 0
for lst in search_list:
    flag = True
    if lst[0] != 0:    
        break
    for i in range(N-1):
        if lst[i+1] in graph[lst[i]]:   
            pass
        else:
            flag = False
            break
    if flag:
        ans += 1

print(ans)

Solution (Python):
import sys
import itertools
if sys.platform =='win32':
	sys.stdin=open('input.txt')
input = sys.stdin.readline
def MAP(): return [int(x) for x in input().split()]


N, M = MAP()
G = [[] for _ in range(N)]
for i in range(M):
	a,b = MAP()
	G[a-1].append(b-1)
	G[b-1].append(a-1)

permutations = (list(itertools.permutations(range(len(G)))))

paths = [p for p in permutations if p[0]==0]

count = 0
for path in paths:
	
	for idx,v in enumerate(path):
		if idx == len(path)-1:
			count+=1
			break
		if path[idx+1] in G[v]: continue
		else: break

print(count)

Solution (Python):
import collections
def main():

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

    

    cur = [[1, 1 << 1]]
    for _ in range(N-1):
        temp = []
        for a, h in cur:
            for b in graph[a]:
                if (h >> b) % 2 == 0:
                    temp.append([b, h | (1 << b)])
        cur = temp
        
    return len(cur)

if __name__ == '__main__':
    print(main())

Solution (Python):
N, M = map(int,input().split())
ab = [list(map(int,input().split())) for i in range(M)]
visited = [0]*N
ans = 0
def move(vert):
    global ans
    visited[vert-1] = 1
    if sum(visited) == N:
        ans += 1
        visited[vert-1] = 0
        return 0 
    for i in range(M):
        if ab[i][0] == vert and visited[ab[i][1]-1] == 0:
            move(ab[i][1])
        elif ab[i][1] == vert and visited[ab[i][0]-1] == 0:
            move(ab[i][0])
    visited[vert - 1] = 0
    return ans
print(move(1))

Solution (Python):
import itertools
N,M = map(int,input().split())
sides = []
for m in range(M):
    x,y = map(int,input().split())
    sides.append((x,y))
vertex = (i for i in range(2,N+1))
ans = 0
for v in itertools.permutations(vertex, N-1):
    T = 1
    if (1,v[0]) not in sides:
        T = 0
    for i in range(N-2):
        if (v[i],v[i+1]) not in sides and (v[i+1],v[i]) not in sides:
            T = 0
            break
    if T == 1:
        ans += 1
print(ans)

Solution (Python):
import itertools

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

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

Sum = 0

for i in range(len(p)):
    if p[i][0] != 0:
        break
    for j in range(N - 1):
        if graph[p[i][j]][p[i][j + 1]] != 1:
            break
        elif j == N - 2:
            Sum += 1

print(Sum)

Solution (Python):
import itertools

n,m = map(int, input().split())
ab = [list(map(int, input().split())) for i in range(m)]
graph = [list() for i in range(n)]
ans = 0
for a,b in ab:
  a -= 1
  b -= 1
  graph[a].append(b)
  graph[b].append(a)
for i in itertools.permutations(range(1,n)):
  now = 0
  for j in i:
    if not (j in graph[now]):
      break
    now = j
  else:
    ans += 1
print(ans)

Solution (Python):
from itertools import permutations
N,M=map(int,input().split())
ab=[list(map(int,input().split())) for i in range(M)]
g=[[False]*N for i in range(N)]
for a,b in ab:
  g[a-1][b-1]=True
  g[b-1][a-1]=True
nodes=[i for i in range(1,N)]
ans=0
for route in permutations(nodes):
  if g[0][route[0]]== False:
    continue
  for i in range(N-1):
    if i == N-2:
      ans+=1
      
      break
    elif g[route[i]][route[i+1]]:
      continue
    else:
      break
print(ans)

Solution (Python):
import itertools
n, m = map(int,input().split())
edges = {tuple(sorted(map(int,input().split()))) for i in range(m)}

ans = 0
a = 0
for i in itertools.permutations(range(2, n+1), n-1):
  l = [1] + list(i)
  
  ans += sum(1 for edge in zip(l,l[1:]) if tuple(sorted(edge)) in edges) == n-1
  
print(ans)

Solution (Python):
from collections import Counter,defaultdict,deque
import sys
import bisect
import math
import itertools
import string
import queue
import copy


from itertools import permutations, combinations
from heapq import heappop, heappush
input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7

def inp(): 
    return int(input())
def inpm(): 
    return map(int,input().split())
def inpl(): 
    return list(map(int, input().split()))
def inpls(): 
    return list(input().split())
def inplm(n): 
    return list(int(input()) for _ in range(n))
def inpll(n): 
    return [list(map(int, input().split())) for _ in range(n)]

def main():
    n,m=inpm()
    g=[[] for _ in range(n)]
    for _ in range(m):
        a,b=inpm()
        g[a-1].append(b-1)
        g[b-1].append(a-1)
    ans = 0
    for root in permutations(range(1,n)):
        if root[0] not in g[0]:
            continue
        key=0
        for i in range(n-2):
            if root[i] not in g[root[i+1]]:
                key=1
        if key==0:
            ans+=1
    print(ans)
        

if __name__ == "__main__":
    main()

Solution (Python):

def dfs(V, closed): 
 
    
    if not False in closed:
        return 1
    
    answer = 0
    for i in range(N):
        if not graph[V][i]:
            continue
        if closed[i]:
            continue
 
        
        closed[i] = True
        answer += dfs(i,closed)
 
        
        closed[i] = False
    
    return answer
 
N,M = map(int,input().split())
graph = [[False for i in range(N)] for j in range(N)]
 
for i in range(M):
    a,b = map(int,input().split())
    graph[a-1][b-1] = graph[b-1][a-1] = True
 
closed_list = [False]*N
closed_list[0] = True
 
print(dfs(0,closed_list))

Solution (Python):

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

path = [(i+1) for i in range(N)]
p_list = list(itertools.permutations(path,N))

ans = 0
for pl in p_list:
    if pl[0] == 1:
        flag = 0
        for i in range(N-1):
            ab1 = [pl[i],pl[i+1]]
            ab2 = [pl[i+1],pl[i]]
            if ab1 in AB or ab2 in AB:
                pass
            else:
                flag = 1
                break
        if flag == 0:
            ans+=1
            
print(ans)

Solution (Python):
from collections import defaultdict
import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.buffer.readline
N,M = map(int,input().split())
g = defaultdict(list)

for i in [0]*M:
    a,b = (map(int,input().split()))
    g[a].append(b)
    g[b].append(a)

f = [False]*N

ans = 0
def rec(s,f_):
    global ans
    f_[s-1] = True
    if sum(f_) == N:
        ans += 1
        return
    for t in g[s]:
        if not f_[t-1]:
            rec(t,f_[:])
    return 
rec(1,f[:])
print(ans)

Solution (Python):
n,m=map(int,input().split())
G=[[0]*n for i in range(n)]
for i in range(m):
    a,b=map(int,input().split())
    G[a-1][b-1]=G[b-1][a-1]=1
V=[0]*n
c=0
def dfs(v):
    global c
    if sum(V)==n:
        c+=1
        return
    for v2 in range(n):
        if G[v][v2]==1 and V[v2]==0:
            V[v2]=1
            dfs(v2)
            V[v2]=0
    return
V[0]=1
dfs(0)
print(c)

Solution (Python):
n,m=map(int,input().split())
nexts=[None for i in range(n)]
for i in range(m):
  a,b=map(int,input().split())
  a,b=a-1,b-1
  if nexts[a]==None:
    nexts[a]=[b]
  elif b not in nexts[a]:
    nexts[a].append(b)
  if nexts[b]==None:
    nexts[b]=[a]
  elif a not in nexts[b]:
    nexts[b].append(a)

ans=0
stack=[]
stack.append([0,[]])
while stack:
  node=stack.pop()
  v=node[0]
  seen=node[1][:]
  seen.append(v)
  if len(seen)==n:
    ans+=1
    continue
  childs=nexts[v]
  if childs:
    for child in (set(childs)-set(seen)):
      stack.append([child,seen])
  
print(ans)

Solution (Python):
from itertools import permutations
import numpy as np
N, M = map(int, input().split(" "))
edges = []
for _ in range(M):
    edges += [list(map(int, input().split(" ")))]

count = 0
for line in permutations(np.arange(N - 1) + 2):
    vtxs = [1] + list(line)
    for i in range(N - 1):
        edge = sorted([vtxs[i], vtxs[i + 1]])
        if edge not in edges:
            break
    else:
        count += 1
print(count)

Solution (Python):
from itertools import permutations
n,m=map(int,input().split())
G=[[0]*n for i in range(n)]
for i in range(m):
	a,b=map(int,input().split())
	G[a-1][b-1]=G[b-1][a-1]=1
l=[i+1 for i in range(n-1)]
c=0
for v in permutations(l,n-1):
	L=[0]+[i for i in v]
	if all([G[L[i]][L[i+1]]==1 for i in range(n-1)]):
		c+=1
print(c)

Solution (Python):



def dfs(v,seen):
    if all(seen):
        return 1
    res = 0
    
    for nv in G[v]:
        if seen[nv]:
            continue
        seen[nv]=True
        res += dfs(nv,seen)
        
        
        
        seen[nv]=False
    return res

n,m = map(int, input().split())
G = [[] for _ in range(n)]
seen = [False]*n
res = 0

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


seen[0]=True
print(dfs(0,seen))

Solution (Python):
import itertools as it

N,M=map(int,input().split())
e=[[False for j in range(N+1)] for i in range(N+1)]
for i in range(M):
    a,b=map(int,input().split())
    e[a][b]=e[b][a]=True


ans=0
l=list(range(2,N+1))
for p in it.permutations(l,N-1):
    q=(1,)+p    
    
    f=True
    for i in range(N-1):
        
        if not e[q[i]][q[i+1]]:
            f=False
            break
    if f:
        ans+=1

print(ans)

Solution (Python):
from itertools import permutations

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

g = [[0] * n for _ in range(n)]
for a, b in ab:
    a -= 1
    b -= 1
    g[a][b] = 1
    g[b][a] = 1

ans = 0
for pat in permutations(range(1, n), n - 1):
    is_path = True
    u = 0
    for v in pat:
        if g[u][v] == 0:
            is_path = False
        u = v

    if is_path:
        ans += 1

print(ans)

Solution (Python):
import itertools
n, m = map(int, input().split(" "))
d = {}
for i in range(1, n+1):
  d[i] = []

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

cnt = 0
for iter in itertools.permutations(range(2, n+1)):
  bp = 0
  for i, num in enumerate(iter):
    if i == 0:
      if num in d[1]:
        pass
      else:
        bp = 1
        break
    else:
      if num in d[iter[i-1]]:
        pass
      else:
        bp = 1
        break
  if bp == 0:
    cnt += 1

print(cnt)

Solution (Python):
import itertools
N, M = map(int, input().split())
X = [[int(a) - 1 for a in input().split()] for _ in range(M)]
Y = [[0] * N for _ in range(N)]
for a, b in X:
    Y[a][b] = 1
    Y[b][a] = 1
ans = 0
for A in itertools.permutations(range(1, N)):
    A = [0] + [a for a in A]
    if all([Y[A[i]][A[i+1]] for i in range(N-1)]):
        ans += 1
print(ans)

Solution (Python):
n, m = map(int, input().split())
road = [[] for _ in range(n)]
result = [0] * n
def search(loc):
    result[loc] = 1
    if sum(result) == n:
        result[loc] = 0
        return 1
    
    cnt = 0
    for r in road[loc]:
        if result[r] == 0:
            cnt += search(r)
    result[loc] = 0
    return cnt
    

for _ in range(m):
    a, b = map(int,input().split())
    road[a-1].append(b-1)
    road[b-1].append(a-1)
print(search(0))

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


S = []
Xold =[[1]]
while Xold:
    Xnew = []
    for x in Xold:
        for y in M[x[-1]]:
            if y not in x:
                z = x + [y]
                Xnew.append(z)
                if len(z)== n:
                    S.append(z)
    
    Xold = Xnew.copy()
    
print(len(S))

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

ans = 0

def dfs(n, visited):
    global ans
    visited.append(n)
    if len(visited) == N:
        ans += 1
    else:
        for i in l[n-1]:
            if i not in visited:
                dfs(i, visited)
    visited.remove(n)

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

dfs(1, [])
print(ans)

Solution (Python):
import itertools
N, M = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(M)]

N_list = [i for i in range(1, N + 1)]

Np_list = list(itertools.permutations(N_list))
ans = 0
for p in Np_list:
    
    flag = True
    if p[0] != 1:
        continue
    for j in range(len(p) - 1):
        if p[j] < p[j+1] and [p[j], p[j + 1]] not in ab:
            flag = False
        elif p[j] > p[j + 1] and ([p[j + 1], p[j]] not in ab):
            flag = False
    if flag:
        ans += 1
print(ans)

Solution (Python):
nmax = 8
graph = [[0]*nmax for i in range(nmax)]
visited = [0] * nmax


def dfs(v, N, visited):
    all_visited = True
    for i in range(N):
        if visited[i] == 0:
            all_visited = False
    if all_visited:
        return 1
  
    ret = 0
    for i in range(N):
        if graph[v][i] == 0:
            continue
        if visited[i] == 1:
            continue
        visited[i] = 1
        ret += dfs(i, N, visited)
        visited[i] = 0
    return ret
      

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


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

Solution (Python):
import itertools
L=["2","3","4","5","6","7","8"]

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

L=L[:N-1]
A=list(itertools.permutations(L,N-1))
C=[]
for i in A:
    B=["1"]+list(i)
    C.append(B)

D={}
for i in range(M):
    a,b=input().split()
    D[(a,b)]=1
    D[(b,a)]=1
    


ans=0
for i in C:
    f=1
    for j in range(N-1):
        if (i[j],i[j+1]) not in D:
            f=0
            break
    if f==1:
        ans+=1
print(ans)

Solution (Python):
N,M = map(int,input().split())
G = [[] for i in range(N+1)]
for i in range(M):
    a,b = map(int,input().split())
    G[a].append(b)
    G[b].append(a)
l = [i for i in range(2,N+1)]
import itertools
ans = 0
for v in itertools.permutations(l):
    v = list(v)
    flag = 1
    s = 1
    t = 1
    while v:
        s = t
        t = v.pop(0)
        if t not in G[s]:
            flag = 0
            break
    ans += flag
print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(1000000)

n, m = map(int, input().split())
adlist = [[] for _ in range(n)]
for _ in range(m):
  a, b = map(lambda x:int(x)-1, input().split())
  adlist[a] += [b]
  adlist[b] += [a]

ans = 0
used = [0] * n 
used[0] = 1
def dfs(u):
  global ans
  if sum(used) == n:
    ans += 1
    return 
  for v in adlist[u]:
    if used[v] == 0:
      used[v] = 1
      dfs(v)
      used[v] = 0

  return 

dfs(0)
print(ans)

Solution (Python):
n,m=map(int,input().split())
l=[[] for i in range(n+1)]
for i in range(m):
  a,b=map(int,input().split())
  l[a].append(b)
  l[b].append(a)
lans=[]
def dfs(i,l1):
  if len(l1)==n:
    lans.append(l1)
    return
  for j in l[i]:
    if j in l1:
      pass
    else:
      l2=l1+[j]
      dfs(j,l2)
  return
dfs(1,[1])
print(len(lans))

Solution (Python):
import itertools

n,m=map(int,input().split())
l=[i for i in range(1,n)]
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)

res = 0
for sp in itertools.permutations(l):
    flag = 1
    s = 0
    for i in range(n-1):
        if not (sp[i] in g[s]):
            flag = 0
            break
        else:
            s = sp[i]
    if flag == 1:
        res += 1

print(res)

Solution (Python):
import itertools
N,M = (int(i) for i in input().split())
K = []
for i in range(M):
    J = [int(i) for i in input().split()]
    J.sort()
    K.append(J)


vertex = []
for i in range(N-1):
    vertex.append(i+2)

X = list(itertools.permutations(vertex))


ans = 0
for i in X:
    start = 1
    localcount = 0
    for j in i:
        tmp = [start,j]
        tmp.sort()
        if tmp in K:            
            localcount += 1   
        start = j
            
    if localcount == N-1:
        ans += 1

print(ans)

Solution (Python):
import itertools

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

a=[]
for i in range(N):
    a.append(i+1)

L=list(itertools.permutations(a))


cnt=0

for l in L:
    tmp=1
    if l[0]!=1:
        break
    for j in range(N-1):
        if ([l[j],l[j+1]] in S) or ([l[j+1],l[j]] in S):
            tmp=1
        else:
            tmp=0
            break
    if tmp==1:
        cnt+=1

print(cnt)

Solution (Python):
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

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


used = [False] * N

used[0] = True

print(dfs(0, used))

Solution (Python):
N, M = map(int, input().split())
g = [[] for _ in range(N + 1)]
for _ in range(M):
    a, b = map(int, input().split())
    g[a].append(b)
    g[b].append(a)
 
ans = 0
def walk(cur, visited):
    global ans
    tmp = visited + [cur]
    if len(tmp) == N:
        ans += 1
        return
    for nex in g[cur]:
        if nex not in tmp:
            walk(nex, tmp)
walk(1, [])
print(ans)

Solution (Python):


import sys

graph = {}

def solve(start, visited = set()):
    global graph

    visited = visited | set([start])
    if len(visited) == len(graph):
        return 1

    ans = 0
    for next_ in graph[start]:
        if not next_ in visited:
            ans += solve(next_, visited)
    return ans

def read_int_list():
    return [int(s) for s in sys.stdin.readline().rstrip().split(" ")]

def dprint(*args, **kwargs):
    return
    print(*args, **kwargs)

def connect(f, t):
    global graph
    if not f in graph:
        graph[f] = set()
    graph[f].add(t)

def main():
    global graph
    
    _, m = read_int_list()
    for _ in range(0, m):
        a, b = read_int_list()
        connect(a, b)
        connect(b, a)

    dprint(repr(graph))
    print(solve(1))

main()

Solution (Python):
import itertools
n,m=map(int,input().split())
data=[[] for i in range(n+1)]
for i in range(m):
    a,b=map(int,input().split())
    data[a].append(b)
    data[b].append(a)
z=[i+2 for i in range(n-1)]
ans=0
for u in itertools.permutations(z):
    if u[0] in data[1]:
        for i in range(1,n-1):
            if u[i] in data[u[i-1]]:
                continue
            else:
                break
        else:
            ans+=1
print(ans)

Solution (Python):
import itertools
N, M = map(int, input().split())
d = [[] for i in range(N)]
for i in range(M):
  a, b = map(int, input().split())
  d[a-1].append(b-1)
  d[b-1].append(a-1)

r = 0
for path in itertools.permutations(range(1, N)):
  path = tuple([0]) + path
  for i in range(1, N):
    if(path[i] not in d[path[i-1]]):
      break
  else:
    r += 1
print(r)

Solution (Python):
n, m = map(int, input().split())
G = [ set() for _ in range(n+1) ]
for  _ in range(m):
  a, b = map(int, input().split())
  G[a].add(b)
  G[b].add(a)
seen = [False]*(n+1)

def dfs(v, c):
  if c == n:
    return 1
  seen[v] = True
  temp = 0
  for nv in G[v]:
    if not seen[nv]:
      temp += dfs(nv, c+1)
  seen[v] = False
  return temp

print(dfs(1, 1))

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

ans = 0
def walk(cur, visited):
    global ans
    tmp = visited + [cur]
    if len(tmp) == N:
        ans += 1
    for nex in g[cur]:
        if nex not in tmp:
            walk(nex, tmp)
walk(1, [])
print(ans)

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

ret = 0
def walk(node, visited):
    global ret
    tmp = visited + [node]
    if len(tmp) == n:
        ret += 1 
    for nd in g[node]:
        if nd not in tmp:
            walk(nd, tmp)
walk(1, [])
print(ret)

Solution (Python):
nmax = 8
graph = [[False] * nmax for _ in range(nmax)]


def dfs(v, N, visited):
    all_visited = True
    for i in range(N):
        if not visited[i]:
            all_visited = False
    if all_visited:
        return 1

    ret = 0
    for i in range(N):
        if not graph[v][i]:
            continue
        if visited[i]:
            continue

        visited[i] = True
        ret += dfs(i, N, visited)
        visited[i] = False
    return ret


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

visited = [False] * nmax
visited[0] = True
print(dfs(0, N, visited))

Solution (Python):
def f(i, links, visited, nodes):
    t = 1 << i
    if t & visited != 0:
        return 0
    visited |= t
    if visited == (1 << nodes) - 1:
        return 1
    result = 0
    for j in links[i]:
        result += f(j, links, visited, nodes)
    return result


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

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

result = 0
for i in links[0]:
    result += f(i, links, 1, N)
print(result)

Solution (Python):
from itertools import permutations as per
n,m = map(int,input().split())
g = [[] for i in range(n)]
for i in range(m):
  a,b = map(int,input().split())
  a-=1;b-=1
  g[a].append(b)
  g[b].append(a)
c = 0
for i in per(range(2,n+1)):
  cur = 1
  f = 1
  for j in range(n-1):
    pre,cur = cur,i[j]
    if cur-1 not in g[pre-1]:
      f = 0
      break
  c += f
print(c)

Solution (Python):
def examC():
    def search_graph(graph_releation, result_list, current_idx=0, path=[0]):
        for i in range(len(graph_releation[current_idx])):
            next_idx = graph_releation[current_idx][i]
            
            tmp_path = copy.deepcopy(path)
            
            if next_idx in tmp_path:
                
                continue
            tmp_path.append(next_idx)
            if len(tmp_path) == len(graph_releation):
                
                result_list.append(tmp_path)  
                continue
            else:
                search_graph(graph_releation, result_list, next_idx, tmp_path)
                

    N, M = LI()
    v = [[] for _ in range(N)]
    for i in range(M):
        a, b = LI()
        v[a-1].append(b-1)
        v[b-1].append(a-1)
    cur = []
    search_graph(v, cur)
    print(len(cur))


import sys
import copy
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
mod = 10**9 + 7
inf = float('inf')

examC()

Solution (Python):
import itertools

N,M = map(int, input().split())
E = [[0]*N for _ in range(N)]
for _ in range(M):
    y, x = map(int, input().split())
    E[y-1][x-1] = 1
    E[x-1][y-1] = 1

ans = 0
L = [int(i) for i in range(1, N)]
for P in itertools.permutations(L):
    f = 0
    for i in range(N-1):
        if i == 0:
            if E[0][P[i]] == 0:
                f = 1
                break
        elif E[P[i-1]][P[i]] == 0:
            f = 1
            break
    if f == 0:
        ans += 1
        
print(ans)

Solution (Python):
from itertools import permutations
n,m=map(int,input().split())
g=[]
for i in range(m):
    a,b=map(int,input().split())
    g.append([a,b])
    g.append([b,a])
ans=0
for i in permutations(range(2,n+1),n-1):
    f=0
    if not [1,i[0]] in g:
        continue
    for j in range(n-2):
        if not [i[j],i[j+1]] in g:
            f=1
            break
    if f==0:
        ans+=1
print(ans)

Solution (Python):
import copy

def perm(i, ls):
    if not ls:
        return 1
    else:
        count = 0
        for j in ls:
            if cost[i-1][j-1]:
                ls2 = copy.copy(ls)
                ls2.remove(j)
                count += perm(j, ls2)
        return count

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

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


count = perm(1, list(range(2, n+1)))

print(count)

Solution (Python):
import copy

def perm(i, ls):
    if not ls:
        global count
        count += 1
    else:
        for j in ls:
            if cost[i-1][j-1]:
                ls2 = copy.copy(ls)
                ls2.remove(j)
                perm(j, ls2)

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

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

count = 0
perm(1, list(range(2, n+1)))

print(count)

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

def dfs(n,seen):
  global ans
  seen.append(n)
  if len(seen)==N:
    ans+=1
  else:
    for i in AB[n-1]:
      if i not in seen:
        dfs(i,seen)
  seen.remove(n)

ans=0
dfs(1,[])
print(ans)

Solution (Python):
import copy

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


result_list = []

def search_graph(graph_releation,result_list,current_idx=0,path=[0]):
    for i in range(len(graph_releation[current_idx])):
        next_idx = graph_releation[current_idx][i]
        tmp_path = copy.deepcopy(path)
        if next_idx in tmp_path:
            continue
        tmp_path.append(next_idx)
        if len(tmp_path) == len(graph_releation):
            result_list.append(tmp_path) 
            continue
        else:
            search_graph(graph_releation,result_list,next_idx,tmp_path)

search_graph(graph_releation,result_list)
print(len(result_list))

Solution (Python):
def one_stroke_path(path, graph, i):
    if len(path) == N:
        return 1
    if not graph[i]:
        return 0
    if graph[i] in path:
        return 0
    res = 0
    for node in graph[i]:
        if not node in path:
            res += one_stroke_path(path + [node], graph, node)
    return res

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

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

ans = 0
path = [0]
i = 0

print(one_stroke_path(path, graph, i))

Solution (Python):
from copy import deepcopy as dp
N, M = map(int, input().split())
path = [list(map(int, input().split())) for i in range(M)]
count = 0

def ser(plase, path, ans):
    global count
    for i in range(len(path)):
        if path[i][0] == plase and not path[i][1] in ans:
            next_path = dp(path)
            next_path.pop(i)
            next_ans = dp(ans)
            next_ans.append(path[i][1])
            ser(path[i][1], next_path, next_ans)
        if path[i][1] == plase and not path[i][0] in ans:
            next_path = dp(path)
            next_path.pop(i)
            next_ans = dp(ans)
            next_ans.append(path[i][0])
            ser(path[i][0], next_path, next_ans)
    if N == len(ans):
        count += 1
ser(1, path, [1])
print(count)

Solution (Python):
def main():
    N, M = map(int, input().split())
    matrix = [[0] * N for _ in range(N)]

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

    def dfs(v, used):
        if False not 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

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

    print(dfs(0, used))


if __name__ == '__main__':
    main()