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):
n,m = map(int,input().split())

list_l = []
list_r = []
seen = [0]*n
sta = []
count = 0
sta.append(1)

for i in range(m):
  temp = list(map(int,input().split()))
  list_l.append(temp[0])
  list_r.append(temp[1])
  
def dfs(count):
  a = sta.pop()
  seen[a-1] = 1
  
  if not (0 in seen):
    count = count + 1

  for i,x in enumerate(list_l):
    if x == a:
      next_num = list_r[i]
      if seen[next_num-1] == 0:
        sta.append(next_num)
        count = dfs(count)
        seen[next_num-1] = 0
    
  for i,x in enumerate(list_r):
    if x == a:
      next_num = list_l[i]
      if seen[next_num-1] == 0:
        sta.append(next_num)
        count = dfs(count)
        seen[next_num-1] = 0
      
  return count

ans = dfs(0)
print(ans)

Solution (Python):
from itertools import permutations
n, m = map(int, input().split())
e = [[0] * n for i in range(n)]
v = [i for i in range(1, n)]
for i in range(m):
    a, b = map(int, input().split())
    e[a -1][b - 1] = e[b - 1][a - 1] = 1


ans = 0
for i in permutations(v):
    s = (0,)
    t = s + i
    flag = 1
    for j in range(n - 1):
        if e[t[j]][t[j + 1]] == 0:
            flag = 0
            break
    if flag:
        ans += 1
print(ans)

Solution (Python):
from itertools import permutations

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

tu = [[] for j in range(n+1)]

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

na = [i for i in range(2,n+1)]
ans = 0

for nara in permutations(na):
    st = 1
    f = True
    for i in range(n-1):
        if not nara[i] in tu[st]:
            f = False
        st = nara[i]
    if f == True:
        ans += 1



print(ans)

Solution (Python):
import itertools

def resolve():
    n, m = map(int, input().split())
    S = [[0] * n for i in range(n)]

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

    ans = 0
    for p in itertools.permutations(range(n)):
        if p[0] != 0:
            break
        tmp = 1
        for i in range(n-1):
            tmp *= S[p[i]][p[i + 1]]
        ans += tmp

    print(ans)

if __name__ == '__main__':
    resolve()

Solution (Python):


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)

Solution (Python):

import sys
import itertools
n,m = map(lambda x: int(x),input().split())
tree = [[]*n for i in range(n)]
l = [int(i) for i in range(n)]
ans_count = 0
for _ in range(m) :
    a,b = map(lambda x: int(x),input().split())
    tree[a-1].append(b-1)
    tree[b-1].append(a-1)
for v in itertools.permutations(l) :
    if v[0] != 0 :
        continue
    flag = 1
    for w in range(n-1) :
        if not v[w] in tree[v[w+1]] :
            flag = 0
    if flag == 1 :
        ans_count += 1
print(ans_count)

Solution (Python):
from collections import deque
import sys
n,m = map(lambda x: int(x),input().split())
sys.setrecursionlimit(26000)

tree = [[]*n for j in range(n)]
seen = [0]*n
seen[0] = 1
ans_conut = 0
def DFS(x) :
    global ans_conut
    if seen.count(1) == n :
        ans_conut +=1
        return

    for i in tree[x] :
        if seen[i] == 0 :
            seen[i] += 1
            DFS(i)
            seen[i] = 0



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

DFS(0)
print(ans_conut)

Solution (Python):
n, m = map(int, input().split())
G = [[] for _ 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)

flag = (1<<n)-1

def dfs(v=0, visited=1):
    if visited == flag:
        return 1

    cnt = 0
    for to in G[v]:
        if visited & (1<<to):
            continue
        cnt += dfs(to, visited^(1<<to))
    return cnt

print(dfs())

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


path_matrix = []


for _ in range(N):
    path_matrix.append([False] * N)

for _ 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(N):
    if path_matrix[now][i]:
      total_paths += dfs(i, depth+1)
  
  visited[now] = False
  
  return total_paths
print(dfs(0,0))

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

ans = 0
def dfs(path):
  if len(path) == N:
    global ans
    ans += 1
  for next in adj[path[-1]]:
    if next not in path:
      dfs(path+[next])
dfs([0])
print(ans)

Solution (Python):
import itertools
n, m = map(int, input().split())
ab = []
for i in range(m):
    ab.append(list(map(int, input().split())))
per = list(itertools.permutations([i+1 for i in range(n)]))
ans = 0
for i in range(len(per)//n):
    
    flug = True
    for j in range(n-1):
        way = list(per[i][j:j+2])
        
        if not((way in ab) or (way[::-1] in ab)):
            flug = False
            break
    if flug:
        ans += 1
print(ans)

Solution (Python):
import itertools

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

edge = [[0]*n for i in range(n)]


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




res = 0
for each in itertools.permutations(range(n)):
    if each[0] != 0:
        break

    x = 1
    for i in range(n-1):
        x *= edge[each[i]][each[i+1]]
    
    res += x

print(res)

Solution (Python):
def dfs(v, N, visited):
    all_visited = True

    for i in range(N):
        if visited[i] == False:
            all_visited = False

    if all_visited:
        return 1

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

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

    return ret


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

graph = [[False for _ in range(8)] for _ in range(8)]


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

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

print(dfs(0, N, visited))

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

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

ans = 0
for path in itertools.permutations(list(range(1, N+1))):
    if path[0] != 1:
        continue
    exist = True
    for i in range(N-1):
        if not path[i+1] in path_map[path[i]]:
            exist = False
            break
    if exist:
        ans += 1
print(ans)

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

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
import itertools

def main():
    mod=10**9+7
    N,M=MI()
    adj=[[] for _ in range(N)]
    for _ in range(M):
        a,b=MI()
        a-=1
        b-=1
        adj[a].append(b)
        adj[b].append(a)
        
        
    ans=0
    for ite in itertools.permutations(range(1,N), N-1):
        v=0
        f=1
        for nv in ite:
            if nv in adj[v]:
                v=nv
            else:
                f=0
                break
        ans+=f
        
    print(ans)
        
            
    

main()

Solution (Python):
N, M = map(int, input().split())
graph = [[False for i in range(N)] for j in range(N)]
visit = [False for i in range(N)]
for i in range(M):
  a, b = map(lambda x: int(x) - 1, input().split())
  graph[a][b] = graph[b][a] = True
visit[0] = True

def dfs(c, n, vis):
  for i in range(n):
    if not vis[i]:
      break
  else:
    return 1
  ret = 0
  for i in range(n):
    if not graph[c][i]:
      continue
    if vis[i]:
      continue
    vis[i] = True
    ret += dfs(i, n, vis)
    vis[i] = False
  return ret

print(dfs(0, N, visit))

Solution (Python):
from sys import stdin
import itertools 
N,M = [int(x) for x in stdin.readline().rstrip().split()]

edges = []
for m in range(M):
    a,b = [int(x) for x in stdin.readline().rstrip().split()]
    edges.append((a,b))
    edges.append((b,a))
    
node = list(range(1,N+1))

ans = 0
for i in itertools.permutations(node):
    f = True
    for j in range(len(i)-1):
        if (not (i[j],i[j+1]) in edges):
            f = False
    if f and i[0] == 1:
        ans += 1
print(ans)

Solution (Python):
from collections import deque

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

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

for i in range(M):
    n,m=map(int,input().split())
    G[n].append(m)
    G[m].append(n)

visited=[0]*(N+1)
ans=0
def dfs(now, num_visited=0):
    global ans
    visited[now] = 1
    num_visited+=1
    
    if num_visited==N:
        ans+=1
    
    for i in G[now]:
        next=i
        if visited[next]!=1:dfs(next,num_visited)

    visited[now] = 0

dfs(1)
print(ans)

Solution (Python):
N,M=map(int,input().split())
original_paths={}
paths={}
for n in range(1,N+1):
    original_paths[n]=[]
    paths[n]=[]
for m in range(1,M+1):
    s,e=map(int,input().split())
    original_paths[s].append(e)
    original_paths[e].append(s)
    paths[s].append(e)
    paths[e].append(s)
    
visited=[1]
current_point=1
answer=0

while len(paths[1])!=0:
    
    if len(paths[current_point])!=0:
        next_point=paths[current_point][0]
    
        if next_point in visited:

            if len(paths[current_point])!=1:
                paths[current_point].remove(next_point)

            else:
                if len(visited)==N:
                    answer+=1
                prior_point=visited[-2]
                paths[current_point]=original_paths[current_point].copy()
                paths[prior_point].remove(current_point)
                visited.remove(current_point)
                current_point=prior_point

        else:
            visited.append(next_point)
            current_point=next_point

    else:
        prior_point=visited[-2]
        paths[current_point]=original_paths[current_point].copy()
        paths[prior_point].remove(current_point)
        visited.remove(current_point)
        current_point=prior_point
        
print(answer)

Solution (Python):
N,M=map(int,input().split())
original_paths={}
for n in range(1,N+1):
    original_paths[n]=[]
for m in range(1,M+1):
    s,e=map(int,input().split())
    original_paths[s].append(e)
    original_paths[e].append(s)
    
visited=[1]
current_point=1
answer=0
import copy
paths=copy.deepcopy(original_paths)

while len(paths[1])!=0:
    
    if len(paths[current_point])!=0:
        next_point=paths[current_point][0]
    
        if next_point in visited:

            if len(paths[current_point])!=1:
                paths[current_point].remove(next_point)

            else:
                if len(visited)==N:
                    answer+=1
                prior_point=visited[-2]
                paths[current_point]=original_paths[current_point].copy()
                paths[prior_point].remove(current_point)
                visited.remove(current_point)
                current_point=prior_point

        else:
            visited.append(next_point)
            current_point=next_point

    else:
        prior_point=visited[-2]
        paths[current_point]=original_paths[current_point].copy()
        paths[prior_point].remove(current_point)
        visited.remove(current_point)
        current_point=prior_point
        
print(answer)

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

check = [0] * n
check[0] = 1


def dfs(x):
    ans = 0
    if min(check) == 1:  
        return 1  
    for i in range(n):  
        if vertex[x][i] == 1 and check[i] == 0:  
            check[i] = 1  
            ans += dfs(i)  
            check[i] = 0  
    return ans  


print(dfs(0))

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

from collections import deque
def dws(st):
  ret = 0
  q = deque([])   
  q.append(st)
  while len(q) > 0:
    p = q.popleft()
    if len(p)==N:
      ret += 1
    else:
      for a in e[p[-1]]:
        if not a in p:
          q.append(p+[a])    
  return ret
print(dws([1]))

Solution (Python):
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 -= 1
    b -= 1
    path[a][b] = True
    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
            elif not path[i[j]][i[j + 1]]:
                break
print(ans)

Solution (Python):
N,M=map(int,input().split())
import copy
a=[0]*M
b=[0]*M
for i in range(M):
    a[i],b[i]=map(int,input().split())
D=[[1]]
def route(D):
    E=[]
    D1=copy.deepcopy(D)
    for j in range(len(D)):
        x=D[j][-1]
        for i in range(M):

            if a[i]==x:
                if not b[i] in D1[j]:
                    D[j]=copy.deepcopy(D1[j])
                    D[j].append(b[i])
                    E.append(D[j])
            elif b[i]==x:
                if not a[i] in D1[j]:
                    D[j]=copy.deepcopy(D1[j])
                    D[j].append(a[i])
                    E.append(D[j])
    return E
for i in range(N-1):
    D=copy.deepcopy(route(D))
print(len(D))

Solution (Python):
import itertools

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

edges = []
for i in range(m):
    edges.append(tuple(map(int, input().split())))

reverse_edges = [e[::-1] for e in edges]



edges += reverse_edges

count = 0
start = 1
end = 1
for series in itertools.permutations(range(2, n + 1)):
    
    start, end = 1, 1
    conflict = False
    for i in series:
        edge = (start, i)
        
        if edge not in edges:
            conflict = True
            
            break
        start = i
    if not conflict:
        count +=1

print(count)

Solution (Python):
import sys
sys.setrecursionlimit(10 ** 9)

def solve(cur, visited):
    if len(visited) == n:
        ans.append(1)
        return
    for i in graph[cur]:
        if not i in visited:
            solve(i, visited + [i])


n, m = map(int, input().split())
graph = [[] for i in range(n)]
ans = []

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

solve(0, [0])
print(len(ans))

Solution (Python):
import itertools

n,m = map(int,input().split())
A = [list(map(int,input().split())) for _ in range(m)]
pair = [[] for _ in range(n+1)]
for i in range(m):
    a = A[i][0]
    b = A[i][1]
    pair[a].append(b)
    pair[b].append(a)

ans = 0
li = [i for i in range(2,n+1)]
orders = list(itertools.permutations(li))

for order in orders:
    flag = True
    pre = 1
    for i in range(n-1):
        if not order[i] in pair[pre]:
            flag = False
        pre = order[i]
    if flag:
        ans += 1
print(ans)

Solution (Python):
import itertools

def main():
    n, m = map(int, input().split())
    g = set([tuple(map(int, input().split())) for _ in range(m)])

    ans = 0
    for path in itertools.permutations(list(range(1, n+1)), n):
        if path[0] != 1:
            continue
        flag = True
        for i in range(n-1):
            if ((path[i], path[i+1]) not in g) and ((path[i+1], path[i]) not in g):
                flag = False
        if flag is True:
            ans += 1
    print(ans)


if __name__ == '__main__':
    main()

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

visited = [0]*N
visited[0] = 1

def dfs(n) :
    ans = 0
    if min(visited) == 1 :
        return 1
    for i in range(N) :
        if G[n][i] == 1 and visited[i] == 0 :
            visited[i] = 1
            ans += dfs(i)
            visited[i] = 0
    return ans

print(dfs(0))

Solution (Python):
n, m = map(int, input().split())
graph = {i: [] for i in range(1, n + 1)}
for _ in range(m):
    u, v = map(int, input().split())
    graph[u].append(v)
    graph[v].append(u)

def dfs(i):
    ret = 0
    if all(han):
        return 1
    for j in range(1, n + 1):
        if han[j] == False and j in graph[i]:
            han[j] = True
            ret += dfs(j)
            han[j] = False
    return ret

han = [False] * (n + 1)
han[0] = True
han[1] = True
ans = dfs(1)
    
print(ans)

Solution (Python):
import itertools

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

total = 0
for x in itertools.permutations(range(2,n+1)):
    
    route = [1,]+list(x)
    
    for x in range(len(route)-1):
        flg = False
        
        for y in data:
            if {route[x],route[x+1]} == set(y):
                flg = True
                break
                
        if flg == False:
            break
            
    else:
        total += 1
        
print(total)

Solution (Python):
import itertools
n,m = map(int,input().split())
mat = [[0]*n for i in range(n)]
for i in range(m):
    u,v = map(int,input().split())
    mat[u-1][v-1] = 1
    mat[v-1][u-1] = 1

cnt = 0
arr = [i for i in range(1,n)]
for road in itertools.permutations(arr):
    start = 0
    for r in road:
        if mat[start][r] ==0:
            break
        else:
            start = r
    else:cnt+=1
print(cnt)

Solution (Python):
import copy

def func(graph, array, n):
  ans = 0
  for v in graph[n]:
    if not array[v]:
      cp_array = copy.deepcopy(array)
      cp_array[v] = True
      
      if [True]*len(array) == cp_array:
        ans += 1
      else:
        ans += func(graph, cp_array, v)

  return ans

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

for i in range(m):
  a,b = map(int, input().split())
  a -= 1
  b -= 1
  graph[a].append(b)
  graph[b].append(a)
  
array = [False] * n
array[0] = True
print(func(graph, array, 0))

Solution (Python):
import itertools
n,m = map(int,input().split())
M = [[0] * n for i in range(n)]

for i in range(m):
  a,b = map(int,input().split())
  M[a-1][b-1] = 1
couse = list(itertools.permutations(range(n)))
result = 0

for c in couse:
  con = 0
  if(c[0] == 0):
    for i in range(len(c)-1):
      if(M[c[i]][c[i+1]] == 1 or M[c[i+1]][c[i]] == 1):
        con += 1
        
    if (len(c)-1 == con):
      result += 1
print(result)

Solution (Python):
import itertools

n,m = [int(x) for x in input().split()]
li = []
for _ in range(m):
    li.append({int(x) for x in input().split()})

a = itertools.permutations(range(2,n+1))
count = 0
for i in a:
    x = [1] + list(i)
    for i in range(n-1):
        if not {x[i],x[i+1]} in li:
            break
    else:
        count += 1
print(count)

Solution (Python):
from itertools import permutations

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

ed = list(range(1, N+1))
temp = permutations(ed)

ans = 0

for i in temp:
    flg = True
    if i[0] != 1:
        continue
    else:
        for j in range(1, N):
            a, b = i[j-1], i[j]
            if a > b:
                ab = a
                a = b
                b = ab
            if [a, b] in edge:
                continue
            else:
                flg = False
                break
    if flg:
        ans += 1

print(ans)

Solution (Python):
n,m=map(int,input().split())
a=[[] for i in range(n)]
for i in range(m):
    x,y=map(int,input().split())
    a[x-1].append(y-1)
    a[y-1].append(x-1)

import itertools
p=itertools.permutations(range(1,n))
p=list(p)

def check(x,y):
    if y in a[x]:
        return True
    else:
        return False
ans=0
for route in p:
    flag=True
    for i in range(n-1):
        if i==0:
            if check(0,route[i])==True:
                pass
            else:
                flag=False
        else:
            if check(route[i-1],route[i])==True:
                pass
            else:
                flag=False
    if flag==True:
        ans+=1
print(ans)

Solution (Python):
import itertools as it
n,m = map(int, input().split())
keiro = []
for i in range(m):
    a,b = map(int, input().split())
    keiro.append([a,b])
per = it.permutations(range(2,n+1),n-1)
ans = 0
for pe in per:
    Flag = True
    pe = list(pe)
    pe.insert(0,1)
    for i in range(len(pe)-1):
        if [pe[i],pe[i+1]] not in keiro and [pe[i+1],pe[i]] not in keiro:
            Flag = False
            break
    if Flag == True:
        ans +=1
print(ans)

Solution (Python):
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
 
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
 
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, M = MAP()
L = [LIST() for i in range(M)]

graph = defaultdict(list)

rinsetsu = [[0] * N for i in range(N)]

for a, b in L:
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)
    rinsetsu[a-1][b-1] = 1
    rinsetsu[b-1][a-1] = 1

per = list(permutations([n for n in range(1, N)]))

permu = []
for p_list in per:
    p_list = [0] + list(p_list)
    permu.append(p_list)

ans = 0

for p in permu:
    for i in range(N-1):
        
        if rinsetsu[p[i]][p[i+1]] != 1:
            break
    else:
        ans += 1
print(ans)

Solution (Python):
from collections import deque
from collections import Counter
from itertools import product, permutations,combinations
import sys
input = sys.stdin.readline

sys.setrecursionlimit(2147483647)

def main():
  n, m = map(int, input().split())
  
  path = [[False for i in range(n)] for j 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 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)

if __name__ == '__main__':
  main()

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

flag = [False]*N
flag[0] = True
res = 0

def f(n):
    global res
    for fl in flag:
        if not fl:
            break
    else:
        res += 1
        return
    for i in x[n]:
        if flag[i]:
            continue
        flag[i] = True
        f(i)
        flag[i] = False
    return

f(0)
print(res)

Solution (Python):
import itertools

n, m = map(int, input().split())
l = [list(map(int, input().split())) for i in range(m)]
r = [[] for i in range(n + 1)]
ans = 0
for i in range(m):
    r[l[i][0]].append(l[i][1])
    r[l[i][1]].append(l[i][0])
p = "2345678"[:n-1]
p = list(itertools.permutations(p))
for i in range(len(p)):
    check = True
    t = "1" + "".join(p[i])
    for j in range(len(t)-1):
        if not int(t[j + 1]) in r[int(t[j])]:
            check = False
    if check:
        ans += 1
print(ans)

Solution (Python):
import itertools
n,m=map(int,input().split())
link=[[]for j in range(n)]
for i in range(m):
  a,b=map(int,input().split())
  link[a-1].append(b-1)
  link[b-1].append(a-1)
s=list(range(1,n))
res=0
for perm in list(itertools.permutations(s)):
  last=0
  ok=True
  for i in range(n-1):
    if perm[i] not in link[last]:
      ok=False
      break
    else:
      last=perm[i]
  if ok==True:
    res=res+1
print(res)

Solution (Python):
import itertools
n, m = map(int, input().split())
l = [list(map(int, input().split())) for i in range(m)]
r = [[] for i in range(n + 1)]
ans = 0
for i in range(m):
    r[l[i][0]].append(l[i][1])
    r[l[i][1]].append(l[i][0])
p = []
for i in range(n):
    p.append(i + 1)
p = list(itertools.permutations(p))
for i in range(len(p)):
    check = True
    t = list(p[i])
    if t[0] != 1:
        check = False
    for j in range(len(t)-1):
        if not t[j + 1] in r[t[j]]:
            check = False
    if check:
        ans += 1
print(ans)

Solution (Python):
import itertools
N,M=map(int,input().split())
path=[tuple(map(int,input().split())) for _ in range(M)]
cnt=0
for li in itertools.permutations([k for k in range(2,N+1)],N-1):
    flag=True
    li=list(li)
    li.insert(0,1)
    for i in range(N-1):
        if (li[i],li[i+1]) not in path and (li[i+1],li[i]) not in path:
            flag=False
    if flag:
        cnt+=1
print(cnt)

Solution (Python):
def dfs(visted, graph, cur, count):
    n = len(visited)

    allNodeVisited = True
    for i in range(1, n):
        if visited[i] is False:
            allNodeVisited = False
            break

    if allNodeVisited:
        count += 1
        return count

    for i in range(1, n):
        if cur != i and visited[i] is False and graph[cur][i] == 1:
            visited[i] = True
            count = dfs(visited, graph, i, count)
            visited[i] = False

    return count


n, m = map(int, input().split())
visited = [False] * (n + 1)

graph = [[0 for _ in range(n + 1)] for _ in range(n + 1)]
for i in range(m):
    frm, to = map(int, input().split())
    graph[frm][to] = graph[to][frm] = 1


count = 0
visited[1] = True
count = dfs(visited, graph, 1, count)

print(count)

Solution (Python):
N, M = map(int, input().split())
G = [[] for _ in range(N)]
visited = [False]*N
visited_all = [True]*N
for i in range(M):
  a, b = map(int, input().split())
  a -= 1
  b -= 1
  G[a].append(b)
  G[b].append(a)
ans = [0]
  
def dfs(node):
  visited[node] = True
  if visited == visited_all:
    ans[0] += 1
  else:
    for i in range(len(G[node])):
      next_node = G[node][i]
      if visited[next_node] == True:
        continue
      dfs(next_node)
      visited[next_node] = False

dfs(0)
print(ans[0])

Solution (Python):
import itertools
N,M = map(int,input().split())
ab = [list(map(int,input().split())) for i in range(M)]
r = list(range(1,N+1))
ok = 1
cnt = 0
for v in itertools.permutations(r):
    if(v[0] == 1):
        ok = 1
        for i in range(N-1):
            if(list(v[i:i+2]) not in ab and list(reversed(v[i:i+2])) not in ab):
                ok = 0
                break
        if(ok == 1):
            cnt += 1
print(cnt)

Solution (Python):
import copy

def solve():
    N,M = map(int, input().split())
    graph = {i:[] for i in range(1,N+1)}
    for _ in range(M):
        a,b = map(int, input().split())
        graph[a].append(b)
        graph[b].append(a)
        
    stack = [1]
    ret = 0
    searched = [False]*(N+1)
    searched[1] = True
    
    def dfs(dom, searched, prev=-1):
        searched[dom] = True
        ret = 0
        
        if all(searched[1:]): 
            
            return ret+1
        
        for cod in graph[dom]:
            
            if not searched[cod]:
                ret += dfs(cod, copy.copy(searched),dom)
        
        return ret
            
    ret = dfs(1, searched)
    print(ret)
    
solve()

Solution (Python):
import sys
sys.setrecursionlimit(10**7) 
N, M = map(int, input().split())
A = [[0]* N for _ in range(N)]
for i in range(M):
    a, b = map(int, input().split())
    A[a-1][b-1] = 1
    A[b-1][a-1] = 1
visited=[1]+[0]*(N-1)
def DFS(now, visited):
    ans = 0
    if not 0 in visited:
        return 1
    for i in range(N):
        if A[now][i] == 0:
            continue
        if visited[i] == 1:
            continue
        visited[i] = 1
        ans += DFS(i, visited)
        visited[i] = 0
    return ans
print(DFS(0, visited))

Solution (Python):



import sys
read = sys.stdin.readline


from itertools import permutations


def read_ints():
    return list(map(int, read().split()))


def main():
    N, M = read_ints()

    from collections import defaultdict
    graph = defaultdict(lambda: [])
    for m in range(M):
        a, b = read_ints()
        graph[a].append(b)
        graph[b].append(a)

    def is_ok(p):  
        for now, nx in zip(p, p[1:]):
            if nx not in graph[now]:
                return 0
        return 1

    ans = 0
    for perm in permutations(range(2, N + 1)):
        perm = [1] + list(perm)
        ans += is_ok(perm)

    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):



import sys
read = sys.stdin.readline


from itertools import permutations


def read_ints():
    return list(map(int, read().split()))


N, M = read_ints()
from collections import defaultdict
graph = defaultdict(lambda: [])
for m in range(M):
    a, b = read_ints()
    graph[a].append(b)
    graph[b].append(a)


def is_ok(p):  
    for now, nx in zip(p, p[1:]):
        if nx not in graph[now]:
            return 0
    return 1


def main():
    ans = 0
    for perm in permutations(range(2, N + 1)):
        perm = [1] + list(perm)
        ans += is_ok(perm)

    print(ans)


if __name__ == "__main__":
    main()