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):
import itertools

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

side = [[] for k in range(n+1)] 

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

ans = 0  
for i in list(itertools.permutations(range(1, n+1), n)):
  if i[0] != 1:
    continue
  for j in range(n-1):
    if not i[j+1] in side[i[j]]:
      break
    if j == n-2:
      ans +=1
print(ans)

Solution (Python):



from collections import deque

def dfs(i, visited):
    stack = deque()
    total = 0
    stack.append((i, visited))
    while stack:
        idx, vis = stack.popleft()
        if all(vis):
            total += 1
        for j in graph[idx]:
            if not vis[j]:
                v = vis[:]
                v[j] = True
                stack.append((j, v))
    return total

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)

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

Solution (Python):



from collections import deque

def dfs(i, visited):
    stack = deque()
    total = 0
    stack.append((i, visited))
    while stack:
        idx, vis = stack.pop()
        if all(vis):
            total += 1
        for j in graph[idx]:
            if not vis[j]:
                v = vis[:]
                v[j] = True
                stack.append((j, v))
    return total

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)

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

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

dp = [[0]*n for _ in range(1<<n)]
dp[1][0] = 1
for num in range(1<<n):
    for v in range(n):
        if num & (1<<v) == 0:
            continue
        sub = num ^ (1<<v)

        for u in range(n):
            if sub & (1<<u) and list_MAP[v][u]:
                dp[num][v] += dp[sub][u]
ans = sum(dp[(1 << n) - 1])
print(ans)

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

dp = [[0]*n for _ in range(1<<n)]
dp[1][0] = 1
for num in range(1<<n):
    for v in range(n):
        if num & (1<<v) == 0:
            continue
        sub = num ^ (1<<v)

        for u in range(n):
            if sub & (1<<u) and list_MAP[v][u]:
                dp[num][v] += dp[sub][u]
ans = sum(dp[(1 << n) - 1][u] for u in range(1, n))
print(ans)

Solution (Python):
import itertools

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

for i in range(m):
    a, b = map(int, input().split())
    my_set.add(a * 10 + b)
    my_set.add(b * 10 + a)

ret = 0
for item in itertools.permutations(range(1, n + 1)):
    is_ok = True
    if item[0] != 1:
        is_ok = False
    for i in range(len(item)-1):
        a, b = item[i], item[i+1]
        if a * 10 + b in my_set:
            continue
        else:
            is_ok = False
    if is_ok:
        ret += 1

print(ret)

Solution (Python):
N,M=map(int,input().split())
import itertools
graph={i:{} for i in range(1,N+1)}
for _ in range(M):
    a,b=map(int,input().split())
    graph[a][b]=1
    graph[b][a]=1
    
seq=[i+1 for i in range(N)]
Q=list(itertools.permutations(seq))
ans=0
for que in Q:
    flag=True
    s=que[0]
    if s!=1:
        flag=False
    for i in range(1,N):
        node=que[i]
        if node in graph[s]:
            s=node
        else:
            flag=False
        if flag==False:
            break
    ans+=int(flag)
print(ans)

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

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


answer=0
for perm in itertools.permutations(range(2,N+1)):
  path=[1]+list(perm)
  
  
  for i in range(1,N):
    u=path[i-1]
    v=path[i]
    if not v in graph[u]:
      break
  else:
    answer+=1
    
print(answer)

Solution (Python):
A,B=list(map(int,input().split()))
n_l=[[] for i in range(A)]
from collections import deque
import itertools
for i in range(B):
   N,M= list(map( int,input().split()))
   n_l[N-1].append(M)
   n_l[M-1].append(N)
all_l=list(range(2,A+1))
first_list=[]
for i in n_l[0]:
   all_l_n=all_l.copy()
   for v in itertools.permutations(all_l_n):
      first_list.append(v)
ans=0
first_list=list(set(first_list))
for x in first_list:
   if x[0] in n_l[0]:
      s=1
      for k in range(len(x)-1):
         if x[k+1] in n_l[x[k]-1]:
            pass
         else:
            s=0
            break
      if s == 1:
         ans+=1
print(ans)

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

from itertools import permutations
lis=[i for i in range(2,n+1)]
permu=list(permutations(lis))

ans=0
for pl in permu:
    c=1
    j=1
    for i in pl:
        if j in G[i]:
            j=i
        else:
            c=0
            break
    ans+=c
print(ans)

Solution (Python):
def main():
    お寿司, 食べたい = map(int, input().split())
    築地 = [[] for _ in range(お寿司)]
    for _ in range(食べたい):
        鮪, 蛸 = map(lambda x: int(x) - 1, input().split())
        築地[鮪].append(蛸)
        築地[蛸].append(鮪)

    やってるかい = [False] * お寿司
    寿司くいねぇ = おなかすいた(0, 築地, やってるかい, 0)

    print(寿司くいねぇ)


def おなかすいた(市場, 築地, やってるかい, お勘定):
    やってるかい[市場] = True
    if all(やってるかい):
        return お勘定 + 1

    for 豪遊 in 築地[市場]:
        if やってるかい[豪遊]:
            continue
        お勘定 = おなかすいた(豪遊, 築地, やってるかい, お勘定)
        やってるかい[豪遊] = False

    return お勘定


if __name__ == '__main__':
    main()

Solution (Python):
def main():
    n, m = map(int, input().split())
    g = [[] for _ in range(n)]
    for _ in range(m):
        u, v = map(lambda x: int(x) - 1, input().split())
        g[u].append(v)
        g[v].append(u)

    vis = [False] * n
    ans = dfs(0, g, vis, 0)

    print(ans)


def dfs(v, g, vis, count):
    vis[v] = True

    if all(vis):
        return count + 1

    for i in g[v]:
        if vis[i]:
            continue
        count = dfs(i, g, vis, count)
        vis[i] = False

    return count


if __name__ == '__main__':
    main()

Solution (Python):
import itertools 

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

ans = 0
for p in P:

  for i in range(n-1):

    if i==0:
      pnow = 0
      pnext = p[0]
    else:
      
      pnow = p[i-1]
      pnext = p[i]
    if pnext not in G[pnow]:
      break
  else:
    ans += 1
    continue
  
  
print(ans)

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

routes = [[] for _ in range(n)]
for i in range(m):
    routes[ab[i][0]-1].append(ab[i][1]-1)
    routes[ab[i][1]-1].append(ab[i][0]-1)

options = [i for i in range(n)]

combinations = ["0"]
for k in range(n-1):
    combinations = [i+str(j) for j in options for i in combinations if str(j) not in i]

allcount = 0
for i in range(len(combinations)):
    for j in range(n-1):
        if int(combinations[i][j+1]) not in routes[int(combinations[i][j])]:
            break
    else:
        allcount+=1

print(allcount)

Solution (Python):
def dfs(v,children,checked):
  if len(checked)==len(children):
    return 1
  ans = 0
  for child in children[v]:
    if child in checked:
      continue
    ncheck = set(checked)
    ncheck.add(child)
    ans += dfs(child,children,ncheck)
  return ans

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

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

ans = dfs(0,children,set([0]))

print(ans)

Solution (Python):
N, M = map(int,input().split())
G = [[] for k in range(N)]

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

def dfs(ima,visited):
    global ans
    visited[ima] = 1
    for tsugi in G[ima]:
        if visited[tsugi] == 0:
            visited[tsugi] = 1
            if sum(visited) == N:
                ans += 1
            dfs(tsugi,visited)
            visited[tsugi] = 0
ans = 0
dfs(0,[0]*N)
print(ans)

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

P=list(range(2,N+1))
ans=0
for p in permutations(P):
    que=[1]+list(p)
    
    to=que.pop(0)
    route=G[to-1]
    count=1
    while len(que)>0:
        to=que.pop(0)
        if to-1 in route:
            count+=1
            route=G[to-1]
        else:
            
            break
    
    if count==N:
        ans+=1
print(ans)

Solution (Python):
from collections import deque
from heapq import heapify,heappop,heappush,heappushpop
from copy import copy,deepcopy
from itertools import product,permutations,combinations,combinations_with_replacement
from collections import defaultdict,Counter
from bisect import bisect_left,bisect_right


from functools import reduce
from pprint import pprint

INF = float("inf")

def myinput():
    return map(int,input().split())

def mylistinput(n):
    return [ list(myinput()) for _ in range(n) ]

def mycol(data,col):
    return [ row[col] for row in data ]

def mysort(data,col,reverse_flag):
    data.sort(key=lambda x:x[col],reverse=reverse_flag)
    return data

def mymax(data):
    M = -1*float("inf")
    for i in range(len(data)):
        m = max(data[i])
        M = max(M,m)
    return M

def mymin(data):
    m = float("inf")
    for i in range(len(data)):
        M = min(data[i])
        m = min(m,M)
    return m

def mycount(ls,x):
    
    l = bisect_left(ls,x)
    r = bisect_right(ls,x)
    return (r-l)

def myoutput(ls,space=True):
    if space:
        if len(ls)==0:
            print(" ")
        elif type(ls[0])==str:
            print(" ".join(ls))
        elif type(ls[0])==int:
            print(" ".join(map(str,ls)))
        else:
            print("Output Error")
    else:
        if len(ls)==0:
            print("")
        elif type(ls[0])==str:
            print("".join(ls))
        elif type(ls[0])==int:
            print("".join(map(str,ls)))
        else:
            print("Output Error")

def I():
    return int(input())

def MI():
    return map(int,input().split())

def RI():
    return list(map(int,input().split()))

def CI(n):
    return [ int(input()) for _ in range(n) ]

def LI(n):
    return [ list(map(int,input().split())) for _ in range(n) ]

def S():
    return input()

def MS():
    return input().split()

def RS():
    return list(input().split())

def CS(n):
    return [ input() for _ in range(n) ]

def LS(n):
    return [ list(input().split()) for _ in range(n) ]

n,m = RI()
ab = LI(m)

g = [ [] for _ in range(n) ]
for i in range(m):
    a = ab[i][0] - 1
    b = ab[i][1] - 1
    g[a].append(b)
    g[b].append(a)


l = list(range(1,n))
ls = list( permutations(l) )


ans = 0
for i in range(len(ls)):
    flag = True
    v = [0]*n
    p = [0] + list(ls[i])
    
    for j in range(len(p)-1):
        if v[p[j]]!=0:
            flag = False
        else:
            if p[j+1] in g[p[j]]:
                v[p[j]] = 1
            else:
                flag = False
    if flag:
        ans += 1
    else:
        pass

print(ans)

Solution (Python):
n, m = map(int,input().split())
G = [[] for _ in range(n)]
for i in range(m):
    a,b = map(lambda x: int(x)-1,input().split())
    G[a].append(b)
    G[b].append(a)
SAW = [False] * n

def dfs(v,SAW):
    global res
    end = True
    for i in range(n):
        if not SAW[i] and i != v:
            end = False
    if end:
        res += 1
        return
    SAW[v] = True
    for nv in G[v]:
        if SAW[nv]:
            continue
        dfs(nv,SAW)
    SAW[v] = False
res = 0
dfs(0,SAW)
print(res)

Solution (Python):
def main():
    import sys
    input = sys.stdin.buffer.readline
    from itertools import permutations
    N, M = (int(i) for i in input().split())
    edge = [[] for _ in range(N)]
    for i in range(M):
        a, b = (int(i) for i in input().split())
        edge[a-1].append(b-1)
        edge[b-1].append(a-1)

    ans = 0
    for p in permutations(range(1, N)):
        v = 0
        for nv in p:
            if nv in edge[v]:
                v = nv
            else:
                break
        else:
            ans += 1
    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
from itertools import *

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

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

ans = 0

for p in permutations(range(N)):
    if p[0]!=0:
        continue
    
    flag = True
    
    for i in range(N-1):
        if p[i+1] not in G[p[i]]:
            flag = False
    
    if flag:
        ans += 1

print(ans)

Solution (Python):
from itertools import permutations

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

mat = [[0 for i in range(N)] for j in range(N)]

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

ans = 0
for i in permutations(range(N)):
    if i[0] != 0:
        continue
    else:

        flag = True
        for j in range(N-1):
            if not mat[i[j]][i[j+1]]:
                flag = False
                break
        if flag:
            ans += 1 

print(ans)

Solution (Python):
import sys
input = sys.stdin.readline

n, m = [int(x) for x in input().split()]
g = [[]*n for _ in range(n)]
for _ in range(m):
    a, b = [int(x) for x in input().split()]
    g[a - 1].append(b - 1)
    g[b - 1].append(a - 1)
v = [int(x) for x in range(n)]
from itertools import permutations
v_per = list(permutations(v, n))
ans = 0
for per in v_per:
    if per[0] != 0:
        continue
    flag = 1
    for i in range(len(per) - 1):
        if per[i + 1] not in g[per[i]]:
            flag = 0
            break
    if flag:
        ans += 1
print(ans)

Solution (Python):
from itertools import permutations

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

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

ans = 0

for p in permutations(range(1, n)):
    if p[0] not in g[0]: continue
    for i in range(n-2):
        if p[i+1] not in g[p[i]]: break
    else: ans += 1

print(ans)

Solution (Python):
from itertools import permutations
N, M = map(int, input().split())
G = [[False] * (N + 1) for _ in range(N + 1)]
for _ in range(M):
    a, b = map(int, input().split())
    G[a][b] = True
    G[b][a] = True

ans = 0
for p in permutations(range(2, N + 1)):
    bl = G[1][p[0]]
    for x, y in zip(p[:-1], p[1:]):
        bl &= G[x][y]
    ans += int(bl)

print(ans)

Solution (Python):
from itertools import permutations

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

toList = [set() for _ in range(N)]
for _ in range(M):
    fr, to = map(lambda a: int(a) - 1, input().split())
    toList[fr].add(to)
    toList[to].add(fr)

def countPath():
    ret = 0
    for P in permutations(range(N), r=N):
        if P[0] != 0:
            continue
        for fr, to in zip(P, P[1:]):
            if not to in toList[fr]:
                break
        else:
            ret += 1
    return ret

print(countPath())

Solution (Python):
import sys
from itertools import permutations

def solve():
    N, M = map(int, input().split())
    Edge = [[] for _ in range(N)]
    for _ in range(M):
        a, b = map(int, input().split())
        Edge[a-1].append(b-1)
        Edge[b-1].append(a-1)
    count = 0
    for order in permutations(range(N)):
        if order[0] != 0: continue
        for i in range(N-1):
            if order[i+1] not in Edge[order[i]]: break
        else: count += 1
    print(count)

    return 0

if __name__ == "__main__":
    solve()

Solution (Python):
from sys import setrecursionlimit
setrecursionlimit(4100000)
n, m = map(int, input().split())
P = [[] for i in range(n)]   
for i in range(m):
    a, b = map(int, input().split())
    a, b = a - 1, b - 1  
    P[a].append(b)
    P[b].append(a)


c = 0   
R = [0 for i in range(n)]  
tm = 1  

def all_search_dfs(c:int, tm:int, R:list):
    if R[c] == 0:
        R[c] = 1
        if  tm < n:
            return point_calculate(c, tm, R)
        elif tm == n:
            return 1
        else:
            return 0
    else:
        return 0

def point_calculate(c:int, tm:int, R:list):
    
    p = 0
    
    for i in range(len(P[c])):
        R2 = R[:]
        
        tmp = all_search_dfs(P[c][i], tm + 1, R2)
        
        
        p += tmp
        
    return p

print(all_search_dfs(c, tm, R))

Solution (Python):
from itertools import permutations
import copy
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] = 1
    g[b-1][a-1] = 1
stock = list(permutations([i for i in range(1,n)]))

ans = 0
for i in stock:
    h = copy.deepcopy(g)
    cnt = 1
    p = 0
    for k in i:
        if h[p][k] == 0:
            break
        else:
            cnt += 1
            p = k
    if cnt == n:
        ans += 1
    
print(ans)

Solution (Python):
import itertools

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

path_matrix = []


for n in range(N):
    path_matrix.append([0] * N)

for m in range(M):
    paths = [int(i) - 1 for i in input().split()]
    path_matrix[paths[0]][paths[1]] = 1
    path_matrix[paths[1]][paths[0]] = 1

list_per = list(itertools.permutations(range(N)))
ans = 0

for i in list_per:
    if i[0] != 0:
        break
    cnt = 1
    for index in range(N - 1):
        cnt *= path_matrix[i[index]][i[index + 1]]
    ans += cnt
    
print(ans)

Solution (Python):
ans = 0
to = []

def main():
    global to
    n, m = map(int, input().split())
    to = [[] for i in range(n)]
    for i in range(m):
        a, b = map(int, input().split())
        a, b = a - 1, b - 1
        to[a].append(b)
        to[b].append(a)
    
    solve(n, m)
    print(ans)

def dfs(pos, arrived):

    global ans

    
    

    arrived[pos] = True

    
    if all(arrived):
        
        ans += 1
        return

    for nt in to[pos]:
        if arrived[nt] == False:
            dfs(nt, [i for i in arrived])

def solve(n, m):
    arrived = [False for i in range(n)]
    dfs(0, arrived)
    return


if __name__ == '__main__':
    main()

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

Solution (Python):
import itertools
import sys

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

if M < N-1:
  print(0)
  sys.exit()

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


pattern = list(itertools.permutations(p))


ans = 0
for i in range(len(pattern)):
  if pattern[i][0] != 0:
    break
  Flag = True
  for j in range(N-1):
    if (pattern[i][j], pattern[i][j+1]) in root:
      continue
    elif (pattern[i][j+1], pattern[i][j]) in root:
      continue
    else:
      Flag = False
      break
  if Flag:
    ans += 1
print(ans)

Solution (Python):
from itertools import permutations
n, m = map(int, input().split())
list_AB = [ list(map(int,input().split(" "))) for i in range(m)]
list_MAP = [[0]*n for _ in range(n)]
list_N = [i for i in range(2, n+1)]

for a, b in list_AB:
    list_MAP[a-1][b-1] = 1
    list_MAP[b-1][a-1] = 1

ans = 0

for l in permutations(list_N, n-1):
    cnt = 0
    p = 1
    q = 0
    for num in l:
        q = num
        cnt += list_MAP[p-1][q-1]
        p = num

    if cnt == n-1:
        ans += 1

print(ans)

Solution (Python):
import itertools
a,b=map(int,input().split())
A=[]
for _ in range(a-1):
  A.append(_+2)
List=[list(map(int,input().split())) for i in range(b)]
count=0
for i in itertools.permutations(A):
  ju=True
  if [1,i[0]] in List or [i[0],1] in List:
    ju=True
  else:
    ju=False
  for j in range(a-2):
    if not([i[j],i[j+1]] in List) and not([i[j+1],i[j]] in List):
      ju=False
  if ju:
    count+=1
print(count)

Solution (Python):
class Graph():
    def __init__(self):
        """ ノードのつながりを辞書型で表現する """
        self.adjacency_dict = {}
    
    def add_vertex(self, v):
        """ ノードを追加する """
        self.adjacency_dict[v] = []
    def add_edge(self, v1, v2):
        """ ノード同士をつなぐ。"""
        
        self.adjacency_dict[v1].append(v2)
        self.adjacency_dict[v2].append(v1)
    def remove_edge(self, v1, v2):
        """ ノード同士のつながりを削除する。"""
        self.adjacency_dict[v1].remove(v2)
        self.adjacency_dict[v2].remove(v1)
    def remove_vertex(self,v):
        """ ノードを削除する。"""
        while self.adjacency_dict[v] != []:
            adjacent_vertex = self.adjacency_dict[v][-1]
            self.remove_edge(v, adjacent_vertex)
        del self.adjacency_dict[v]
    
    def print_graph(self):
        print(self.adjacency_dict)

    def _init_internal_graph(self, graph_dict):
        self.adjacency_dict = graph_dict
    
    def get_edge(self, v):
        """ 指定されたノードに関するエッジを返す。"""
        return self.adjacency_dict[v]

def dprint(*args):
  if debug:
    if len(args)==1:
      print(args[0])
    else:
      print(args)

debug = False
if debug:
  g = Graph()
  
  
  
  N,M = [3, 3]
  g._init_internal_graph({0: [1, 2], 1: [0, 2], 2: [0, 1]})
else:
  N, M = map(int, input().split())
  g = Graph()
  dprint(N,M)

  for n in range(N):
    g.add_vertex(n)

  
  for m in range(M):
      v1,v2 = list(map(int, input().split()))
      g.add_edge(v1-1,v2-1)                     



seen = [False] * N
count = 0

def dfs(node, depth):
    dprint(node,depth)        
    if seen[node]:
        return 0
    if depth == N - 1:
        dprint('count-up',seen)
        return 1

    seen[node] = True
    dprint(seen)
    
    total_paths = 0
    for next_node in g.get_edge(node):
      total_paths += dfs(next_node, depth + 1)

    
    seen[node] = False

    return total_paths

count = dfs(0, 0)
print(count)

Solution (Python):

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] * 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))

Solution (Python):
import sys
import itertools
n,m=map(int,input().split())
ab=[]
for _ in range(m):
    ab.append(list(map(int,input().split())))

lis=list(range(1,n+1))
per_lis =[i for i in list(itertools.permutations(lis)) if i[0]==1]

ans=0

for one_case in per_lis:
    tmp=0
    for j in range(n-1):
        for num in ab:
            if one_case[j]==num[0] and one_case[j+1]==num[1]:
                tmp+=1
            elif one_case[j]==num[1] and one_case[j+1]==num[0]:
                tmp+=1
                    

        if tmp==n-1:
            ans+=1

print(ans)

Solution (Python):
import sys
import itertools
n,m=map(int,input().split())
ab=[]
for _ in range(m):
    ab.append(list(map(int,input().split())))

lis=list(range(1,n+1))
per_lis = itertools.permutations(lis) 

ans=0

for one_case in per_lis:
    if one_case[0]==1:
        tmp=0
        for j in range(n-1):
            for num in ab:
                if one_case[j]==num[0] and one_case[j+1]==num[1]:
                    tmp+=1
                elif one_case[j]==num[1] and one_case[j+1]==num[0]:
                    tmp+=1
                    

        if tmp==n-1:
            ans+=1

print(ans)

Solution (Python):
from itertools import permutations
n, m = map(int, input().split())
v = [set(map(int, input().split())) for _ in range(m)]

ans = 0
x = [i for i in range(2, n+1)]
cand = permutations(x)
for i in cand:
    crnt = 1
    for nxt in i:
        if set([crnt, nxt]) in v:
            crnt = nxt
        else:
            break
    else:
        ans += 1
print(ans)

Solution (Python):
import itertools
n , m = map(int,input().split())
hen = [list(map(int,input().split())) for _ in range(m)]



ans = 0
x = [i for i in range(2,n+1)]
candi = itertools.permutations(x)
for i in candi: 
  now = 1
  for next in i: 
    if [now,next] in hen or [next,now] in hen:
      now = next
    else:
      ck = 0
      break
  else:
    ans += 1

print(ans)

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

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


def dfs(node, visited):
  if all(visited):
    return 1

  res = 0
  for nei in adj_list[node]:
    if not visited[nei]:
      visited[nei] = True
      res += dfs(nei, visited)
      visited[nei] = False

  return res

cnt = 0
for node in adj_list[1]:
  visited = [False]*(N+1)
  visited[0],visited[1],visited[node] = True,True,True
  cnt += dfs(node, visited)

print(cnt)

Solution (Python):
def DFS(num):
    global ans,color
    color[num]="black"
    if "white" not in color:
        ans +=1
    for i in M[num]:
        if color[i]=="white":
            DFS(i)
    color[num]="white"


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

M=[[] for _ in range(n)]
color=["white" for _ in range(n)]
for a,b in AB:
    M[a-1].append(b-1)
    M[b-1].append(a-1)

ans=0
DFS(0)
print(ans)

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

l = [0]
def dfs(p,s):
  for i in G[p]:
    if s[i] == "0":
      a = s[:i] + "1" + s[i+1:]
      dfs(i,a)
  if s == "0" + N*"1":
    l[0] += 1

s = "01"+(N-1)*"0"
    
dfs(1,s)
print(l[0])

Solution (Python):
import itertools
n, m = map(int, input().split())

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

ans = 0
for value in itertools.permutations([int(x) for x in range(1, n)]):
  if not node[0][value[0]]:
    continue
  flag = True
  for i in range(n-2):
    if not node[value[i]][value[i+1]]:
      flag = False
  if flag:
    ans += 1

print(ans)

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

G = {k: [] for k 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)


def dfs(p, arrived):
    if arrived == 2**N-1:
        return 1

    ret = 0
    for n in G[p]:
        if (arrived >> n) & 1 == 0:
            ret += dfs(n, arrived+2**n)
    return ret


arrived = 1
print(dfs(0, arrived))

Solution (Python):
n, m = map(int, input().split())

conn = []
for _ in range(n):
    conn.append([False]*n)

visited = [False]*n 


v = []
for i in range(m):
    tmp = list(map(int, input().split()))
    v.append([x-1 for x in tmp])


for start, end in v:
    conn[start][end] = conn[end][start] = True

def dfs(now, depth):
    if visited[now]:
        return 0
    if depth == n-1: 
        return 1

    visited[now] = True
    ret = 0

    for i in range(n):
        if conn[now][i]:
            ret += dfs(i, depth+1)

    visited[now] = False

    return ret

print(dfs(0, 0))

Solution (Python):
import itertools
def judge(a,b,edge): 
    if edge[a][b] == 1:
        return True
    else:
        return False
n,m = map(int,input().split())
edge=[[0 for _ in range(n+1)] for _ in range(n+1)]
for _ in range(m):
    a,b = map(int,input().split())
    edge[a][b] = 1
    edge[b][a] = 1
lis_permutations = itertools.permutations(range(2,n+1))
count = 0
for one_case in lis_permutations:
    one_case_1 = [1]
    for j in one_case:
        one_case_1.append(j)
    true = 1
    for i in range(len(one_case_1)-1):
        start = one_case_1[i]
        goal = one_case_1[i+1]
        if not judge(start,goal,edge):
            true = 0
            break
    if true ==1:
        count += 1
print(count)

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

c = 0
P = [0]*N
P[0] = 1
def bfs(start,used):
    global c
    for i in K[start]:
        M = used[:]
        k = 0
        if M[i] == 0:
            M[i] = 1
            for j in M:
                if j != 1:
                    k = 1
                    break
            if k == 0:
                c += 1
            else:
                bfs(i,M)

bfs(0,P)
print(c)