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 sys
input = sys.stdin.readline

import math

import bisect
from collections import defaultdict
from collections import deque
from functools import lru_cache






MOD = 10**9+7
INF = float('inf')






def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]


def P(arg): print(arg); return
def Y(): print("Yes"); return
def N(): print("No"); return
def E(): exit()
def PE(arg): print(arg); exit()
def YE(): print("Yes"); exit()
def NE(): print("No"); exit()


def DD(arg): return defaultdict(arg)



def inv(n): return pow(n, MOD-2, MOD)


kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n):
    return kaijo_memo[n]
  if(len(kaijo_memo) == 0):
    kaijo_memo.append(1)
  while(len(kaijo_memo) <= n):
    kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n):
    return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0):
    gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n):
    gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if(n == r):
    return 1
  if(n < r or r < 0):
    return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret


def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1:
    arr.append([temp, 1])
  if arr==[]:
    arr.append([n, 1])
  return arr


def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors


def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum


def gcd(a, b):
    while b:
        a, b = b, a % b
    return a


def lcm(a, b):
    return a * b // gcd (a, b)


def count_bit(n):
  count = 0
  while n:
    n &= n -1
    count += 1
  return count


def base_10_to_n(X, n):
  if X//n:
    return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))


def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count





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

import itertools
nums = [i+1 for i in range(N-1)]
count = 0
for route in itertools.permutations(nums):
  co = route[:]
  route = list(route)
  prev = 0
  while route:
    now = route.pop()
    if now not in graph[prev]:
      route = "NG"
      break
    prev = now
  if not route:
    count += 1
print(count)

Solution (Python):



import itertools

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


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

result = 0

for v in itertools.permutations(node):
    index = 0
    adj_mat2 = adjacency_matrix[:]
    past = 0
    for i in v:
        
        
        a = min(past, i)
        b = max(past, i)


        if adj_mat2[a][b] != 1:
            break

        past = i
        index += 1
    if index == n-1:
        result += 1

print(result)

Solution (Python):
import sys
import math
import itertools
def input():
    return sys.stdin.readline()[:-1]

n,m=map(int,input().split())
g = [[]for i in range(n)]
lis = [i for i in range(2,n+1)]

for i in range(m):
    a,b=map(int,input().split())
    g[a-1].append(b-1)
    g[b-1].append(a-1)
ans=0
for i in itertools.permutations(lis):
    now = 0
    jud = True
    for j in list(i):
        if j-1 not in g[now]:
            jud = False
            continue
        else:
            now = j-1

    if jud==True:
        ans+=1

print(ans)

Solution (Python):
def DFS(now, visited):
    ans = 0
    if all(visited):
        return 1
    for i in range(N):
        if path[now][i] and visited[i] == False:
            visited[i] = True
            ans += DFS(i, visited)
            visited[i] = False
    return ans
    


N, M = map(int, input().split())
path = [[0]*N for i in range(N)]
for i in range(M):
    a, b = map(int, input().split())
    path[a-1][b-1] = 1
    path[b-1][a-1] = 1
visited = [False]*N
visited[0] = True
print(DFS(0, visited))

Solution (Python):
import sys
from collections import Counter
from collections import deque
import heapq
import math
import fractions
import bisect
import itertools
def input(): return sys.stdin.readline().strip()
def mp(): return map(int,input().split())
def lmp(): return list(map(int,input().split()))

n,m=mp()
tree=[[False]*(n+1) for i in range(n+1)]
for i in range(m):
    a,b=mp()
    tree[a][b]=True
    tree[b][a]=True
ans=0
for path in itertools.permutations(range(2,n+1), n-1):
    if tree[1][path[0]]:
        for i in range(n-1):
            if i==n-2:
                ans+=1
                break
            if not tree[path[i]][path[i+1]]:
                break

print(ans)

Solution (Python):
import itertools

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)

path = list(itertools.permutations(range(1, N), N-1))
ans = 0
for p in path:
  now = 0
  res = True
  for child in p:
    if child not in graph[now]:
      res = False
      break
    now = child
  ans += res

print(ans)

Solution (Python):
from itertools import permutations

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
lsts = list(permutations(range(n)))

for lst in lsts:
    if lst[0] != 0:
        continue
    now = 0
    for l in lst[1:]:
        if not l in graph[now]:
            break
        now = l
    else:
        ans += 1
        
print(ans)

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

for i in range(m):
    a,b=map(int,input().split())
    a-=1
    b-=1
    adj[a].append(b)
    adj[b].append(a)
    
sum=0
for i in permutations(list(range(1,n))):
    i = [0]+list(i)
    c=1
    for j in range(n-1):
        if not(i[j+1] in adj[i[j]]):
            c*=0
    sum+=c
            
print(sum)

Solution (Python):


import itertools

n, m = map(int, input().rstrip().split())
mylist = [[0 for j in range(n)] for i in range(n)]

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

vist = [i for i in range(1, n)]

result = 0
for v in itertools.permutations(vist):
    index = 0
    mylist2 = mylist[:]
    past = 0
    for i in v:
        a = min(past, i)
        b = max(past, i)
        if mylist2[a][b] != 1:               
            break
        past = i
        index += 1
    if index == n-1:
        result += 1
        
print(result)

Solution (Python):


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


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


visited = [False] * n



v = []
for _ in [0]*m:
    line = map(int, input().split())
    v.append([x-1 for x in line])


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(0, n):
        if conn[now][i]: ret += dfs(i, depth+1)
    
    visited[now] = False

    return ret

print(dfs(0, 0))

Solution (Python):
from collections import deque

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

def DFS(now, visited):
    global ans
    if len(visited) == N:
        ans += 1 
    else:
        for u in adj[now]:
            if u not in visited: 
                DFS(u, visited+[u])
                
                
        return



ans = 0
visited = [0] 
DFS(0, visited)
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())))
ct = 0
N_lis = [(i + 2) for i in range(n - 1)]
Pat = itertools.permutations(N_lis)
for one_case in Pat:
    tmp = 1
    all_flag = True
    for j in one_case:
        flag = False
        for k in range(m):
            if AB[k][0] == tmp:
                if AB[k][1] == j:
                    tmp = j
                    flag = True
                    break
            elif AB[k][1] == tmp:
                if AB[k][0] == j:
                    tmp = j
                    flag = True
                    break
        if not flag:
            all_flag = False
            break
    if all_flag:
        ct += 1
print(ct)

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

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


dp = [[0] * n for _ in range(1 << n)]


dp[1][0] = 1

for S in range(1 << n):
    for v in range(n):
        
        if S & (1 << v) == 0:
            continue
        
        
        sub = S ^ (1 << v)
        
        for u in range(n):
            
            if sub & (1 << u) and P[u][v]:
                dp[S][v] += dp[sub][u]

ans = sum(dp[(1 << n) - 1][u] for u in range(1, n))
print(ans)

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

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


dp = [[0] * n for _ in range(1 << n)]


dp[1][0] = 1

for S in range(1 << n):
    for v in range(n):
        
        if S & (1 << v) == 0:
            continue
        
        
        sub = S ^ (1 << v)
        
        for u in range(n):
            
            if sub & (1 << u) and P[u][v]:
                dp[S][v] += dp[sub][u]

ans = sum(dp[(1 << n) - 1][u] for u in range(1, n))
print(ans)

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

from collections import defaultdict

memo = defaultdict(list)

for ele in ab:
    memo[ele[0]-1].append(ele[1]-1)
    memo[ele[1]-1].append(ele[0]-1)

que = []
visited = defaultdict(int)
ans = [0]

def dfs(visited,node,pre_node,tmp_sum):
    if tmp_sum == N:
        ans[0] += 1
        return

    for nn in memo[node]:
        if nn == pre_node: continue
        if visited[nn]==1: continue
        visited[nn] = 1
        dfs(visited,nn,node,tmp_sum+1)
        visited[nn] = 0

    return
        
flag = [False]
visited[0]=1
dfs(visited,0,-1,1)

print(ans[0])

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


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

ans = 0
for l in permutations(range(1,n)):
    l = [0] + list(l)
    cnt = 1
    for i in range(n-1):
        
        if edges[l[i]][l[i+1]] == 0:
            cnt = 0
            break
    ans += cnt
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
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 deque

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

def DFS(now, visited):
    if len(visited) == N:
        return 1
    else:
        count = 0
        for u in adj[now]:
            if u not in visited:
                count += DFS(u, visited+[u])
        return count


def main():
    queue = deque([0])
    visited = [0]
    ans = DFS(0, visited)
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):

from collections import deque

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

ans = 0

def DFS(now,visited):
    global ans
    if len(visited) == N:
        ans += 1
    else:
        for u in adj[now]:
            if u not in visited:
                DFS(u,visited+[u])

def main():
    queue = deque([0])
    visited = [0]
    DFS(0,visited)
    print(ans)

if __name__ == "__main__":
    main()

Solution (Python):
N,M=map(int,input().split())
R=list(list(map(int,input().split())) for _ in range(M))
S=[i for i in range(2,N+1)]

import itertools
count=0
for p in itertools.permutations(S):
  damage=0
  p=list(p)
  q=[1]
  for j in range(N-1):
    q.append(p[j])
  for i in range(N-1):
    if not([q[i],q[i+1]] in R) and not([q[i+1],q[i]] in R):
      damage=1
  if not(damage):
    count+=1


print(count)

Solution (Python):


from collections import deque
import itertools

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

all_lis = itertools.permutations(range(1, n))  


ans = 0
for i in all_lis:
    start = 0
    ok = 1
    for j in range(n - 1):
        if i[j] not in path[start]:
            ok = 0
            break
        else:
            start = i[j]
    if ok:
        ans += 1
print(ans)

Solution (Python):
import sys
from itertools import permutations
input = sys.stdin.readline
N, M = map(int,input().rstrip().split())
node = []
for _ in range(M):
  a,b = map(int,input().rstrip().split())
  node.append((a,b))
  node.append((b,a))
ans = 0
for p in permutations(range(1,N+1)):
  flag = True
  if p[0] != 1:
    continue
  for i in range(N-1):
    if (p[i],p[i+1]) not in node:
      flag = False
  if flag:
    ans += 1
print(ans)

Solution (Python):
num_ver, num_edge = map(int,input().split())

graph_mat = [[0]*num_ver for _ in range(num_ver)]

for i in range(num_edge):
    start, goal = map(int,input().split())
    start -= 1
    goal -= 1
    graph_mat[start][goal] = 1
    graph_mat[goal][start] = 1

visited = [0] * num_ver

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

    for ver in range(num_ver):
        if graph_mat[now][ver]:
            num_path += dfs(ver, depth + 1)
    
    
    visited[now] = 0

    return num_path
print(dfs(0,0))

Solution (Python):
num_ver, num_edge = map(int,input().split())

graph_mat = [[0]*num_ver for _ in range(num_ver)]

for i in range(num_edge):
    start, goal = map(int,input().split())
    start -= 1
    goal -= 1
    graph_mat[start][goal] = 1
    graph_mat[goal][start] = 1

visited = [0] * num_ver



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

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

    visited[now] = 0

    return total_paths

print(dfs(0, 0))

Solution (Python):




import math
import sys
import bisect
import heapq  
from collections import deque
inf = 10 ** 15
mod = 10 ** 9 + 7

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


def dfs(visited, now):
    tmp = [visited[i] for i in range(n)]
    tmp[now] = True
    if all(tmp):
        return 1
    else:
        ret = 0
        for b in ab[now]:
            if not tmp[b]:
                ret+=dfs(tmp, b)
        return ret

print(dfs([False for i in range(n)], 0))

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

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

for i in range(M):
  a,b = map(int,readline().split())
  G[a-1].append(b-1)
  G[b-1].append(a-1)
  
ans = 0
stack = []
stack.append([0,set()])
while stack:
  v,visited = stack.pop()
  if v in visited:
    continue
  visited2 = visited.copy()
  visited2.add(v)
  if len(visited2) == N:
    ans += 1
    continue
  for child in G[v]:
    stack.append([child,visited2])

print(ans)

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

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

ans = []

def dfs(x):
  visited[x-1] = 1
  if visited == [1] * N:
    ans.append(1)
  for i in range(len(adj[x-1])):
    if visited[adj[x-1][i] - 1] == 0:
      dfs(adj[x-1][i])
  visited[x-1] = 0
      
dfs(1)
print(sum(ans))

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

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

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

ans = []

def dfs(x):
  visited[x-1] = 1
  if visited == [1] * N:
    ans.append(1)
  for i in range(len(adj[x-1])):
    if visited[adj[x-1][i] - 1] == 0:
      dfs(adj[x-1][i])
  visited[x-1] = 0
      
dfs(1)
if ans == []:
  print(0)
else:
  print(sum(ans))

Solution (Python):
from itertools import permutations

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
lst = [i for i in range(n)]
lsts = list(permutations(lst, n))

for lst in lsts:
    if lst[0] != 0:
        continue
    now = 0
    for l in lst[1:]:
        if not l in graph[now]:
            break
        now = l
    else:
        ans += 1
print(ans)

Solution (Python):

import sys
input = sys.stdin.readline









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

A = [[False for _ in range(N)] for _ in range(N)]
for a,b in AB:
    A[a-1][b-1] = True
    A[b-1][a-1] = True


from itertools import permutations
Ps = permutations([i for i in range(1,N)])

ans = 0
for P in Ps:
    flg = True
    x,y = 0,0
    for p in P:
        y = p
        
        if not A[x][y]:
            flg = False
            break
        x = p
    if flg:
        ans += 1

print(ans)

Solution (Python):


from itertools import permutations

N, M = map(int, input().split())
G = [[0]*N for _ 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

perms = permutations(range(1, N))
ans = 0

for perm in perms:
  now = 0
  for v in perm:
    if G[now][v] == 0:
      break
    now = v
  else:
    ans += 1
    
print(ans)

Solution (Python):

from collections import deque

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)
  
stack = deque([(0, 0)])
visited = [0] * N
depth = 0
ans = 0
while stack:
  now, depth = stack.pop()
  if depth == N-1:
    ans += 1
    continue
  visited[depth] = now
  for nxt in G[now]:
    if nxt not in visited[:depth+1]:
      stack.append((nxt, depth+1))
    
print(ans)

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

visit = [0] * (n + 1)
ans = 0


def dfs(now, depth):
    global ans
    if visit[now]:
        pass
    if depth == n:
        ans += 1

    visit[now] = 1
    if graph[now]:
        for i in graph[now]:
            if visit[i] == 0:
                dfs(i, depth + 1)
    visit[now] = 0


dfs(1, 1)
print(ans)

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

visit = [0] * (n + 1)


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

    count = 0
    visit[now] = 1
    if graph[now]:
        for i in graph[now]:
            count += dfs(i, depth + 1)
    visit[now] = 0

    return count


ans = dfs(1, 1)
print(ans)

Solution (Python):
from sys import stdin
from itertools import permutations
from collections import Counter


def main():
    _in = [_.rstrip() for _ in stdin.readlines()]
    N, M = list(map(int,_in[0].split(' ')))  
    graph = []
    for i in range(M):
        _ = list(map(int,_in[i+1].split(' ')))  
        graph.append(_)
    
    con = [[] for i in range(N)]
    for a,b in graph:
        a -= 1
        b -= 1
        con[a].append(b)
        con[b].append(a)
    for i, _ in enumerate(con):
        con[i] = Counter(con[i])

    cnt = 0
    for cand in permutations(range(1,N)):
        _cand = (0,)+cand
        mult = 1
        for v,nv in zip(_cand[:-1],_cand[1:]):
            try:
                mult *= con[v][nv]
            except:
                mult = 0
                break
        cnt += mult
    
    print(cnt)

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

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

def mkmap(N, M):
    mapdic = {}
    for i in range(1, N+1):
        mapdic[str(i)] = [] 
    for j in range(M):
        pathA, pathB = map(str, input().split())
        mapdic[pathA] = mapdic[pathA] + [pathB]
        mapdic[pathB] = mapdic[pathB] + [pathA]
    return mapdic

mapdic = mkmap(N, M)
import copy

roots = [[]]*N
roots[0] = ["1"]
for i in range(N-1):
    root = copy.deepcopy(roots[i])
    for nowroot in root:
        for nextroot in mapdic[nowroot[-1]]:
            if  i >= 1:
                if not nextroot in nowroot:                    
                    roots[i+1] = roots[i+1] + [nowroot + nextroot]
                else:
                    pass
            else:
                roots[i+1] = roots[i+1] + [nowroot + nextroot]


List = [str(n+1) for n in range(N)]
check = "".join(List)
ans = 0
for i in roots[-1]:
    TF = "".join(sorted(list(i))) == check
    if TF:
        ans = 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(int, input().split())
    a, b = a - 1, b - 1
    g[a].append(b)
    g[b].append(a)

lis = list(c for c in permutations(range(n), n) if c[0] == 0)

res = 0
for li in lis:
    flg = True
    for i in range(1, n):
        if li[i-1] in g[li[i]]:
            continue
        else:
            flg = False
            break
    if flg:
        res += 1
print(res)

Solution (Python):
from itertools import permutations

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

ans = 0
for l in permutations(range(1,N)):
    l = [0] + list(l)
    cnt = 1
    for i in range(N-1):
        if edges[l[i]][l[i+1]] == 0:
            cnt = 0
    ans += cnt

print(ans)

Solution (Python):
import itertools

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

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

ls = [i for i in range(1, N)]
ans = 0
for route in itertools.permutations(ls, N-1):
    pre = 0
    for i in range(N-1):
        next_v = route[i]
        if next_v not in G[pre]:
            break
        pre = next_v
    else: ans += 1

print(ans)

Solution (Python):
N, M = map(int, input().split())
ab = [[int(i) for i in input().split()] for j in range(M)]

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

def rec(v, memo):
    if memo.count(-1) == 1:
        return 1

    memo[v] = 1

    count = 0
    for next_v in G[v]:
        if memo[next_v] == -1:
            count += rec(next_v, memo)

    memo[v] = -1
    return count

memo = [-1 for i in range(N)]
print(rec(0, memo))

Solution (Python):
N, M = map(int, input().split())
ab = [[int(i) for i in input().split()] for j in range(M)]

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

def rec(v, memo):
    memo[v] = 1

    if -1 not in memo:
        memo[v] = -1
        return 1

    count = 0
    for next_v in G[v]:
        if memo[next_v] == -1:
            count += rec(next_v, memo)

    memo[v] = -1
    return count

memo = [-1 for i in range(N)]
print(rec(0, memo))

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

import itertools
per = itertools.permutations([i for i in range(1,N+1)])
ans = 0
for item in per:
    if item[0] != 1:
        continue
    f = True
    for ind,num in enumerate(item):
        if ind + 1<= N-1:
            nnum = item[ind+1]
            if nnum not in edge[num]:
                f = False

    if f:
        ans += 1

print(ans)

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

result = []

import copy
def dfs(n,used,d):
    if d == N-1:
        result.append(1)
    for e in edge[n]:
        if used[e] == False:
            usedf = copy.deepcopy(used)
            usedf[e] = True
            dfs(e,usedf,d+1)


used = [False]*(N+1)
used[1] = True
dfs(1,used,0)
print(len(result))

Solution (Python):
from collections import defaultdict
import queue

def dfs(P,V,s,cnt):
    V[s] = 1
    
    
    if len(V) == sum(V):
        cnt += 1
        

    for t in P[s]:
        if V[t] > 0:
            continue
        
        V,cnt = dfs(P,V,t,cnt)
    V[s] = 0
    return V,cnt

def main():
    N,M = [int(x) for x in input().split()]
    paths = []
    for _ in range(M):
        a,b = [int(x) for x in input().split()]
        paths.append((a,b))

    
    P = defaultdict(list)
    for a,b in paths:
        P[a-1].append(b-1)
        P[b-1].append(a-1)

    V = [0]*N
    s = 0
    cnt = 0
    
    V,cnt = dfs(P,V,s,cnt)
    print(cnt)


if __name__ == '__main__':
    main()

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

from itertools import permutations
c = 0
for p in permutations(range(1, N)):
    pi = 0
    for pj in p:
        if not pj in G[pi]:
            break
        pi = pj
    else:
        c += 1
print(c)

Solution (Python):
n,m=[int(x) for x in input().rstrip().split()]
l=[[]*n for i in range(n)]
done=[False for i in range(n)]
for i in range(m):
  a,b=[int(x) for x in input().rstrip().split()]
  l[a-1].append(b-1)
  l[b-1].append(a-1)


def bfs():
  stack=[[0,[]]]
  ans=0
  while(stack):
    now,visited=stack.pop(0)
    if len(visited)==n-1:
      ans+=1    
    for i in l[now]:
      if i not in visited:
        stack.append([i,visited+[now]])
  return ans

print(bfs())

Solution (Python):
N, M = map(int, input().split())
p = [list(map(int, input().split())) for i in range(M)]
import itertools
v = list(map(list, itertools.permutations(range(2,N+1), N-1)))
cnt = 0
for i in range(len(v)):
    vit = True
    v_i = [1]+v[i]
    for j in range(N-1):
        if sorted(v_i[j:j+2]) not in p:
            vit = False
    if vit:
        cnt += 1
print(cnt)

Solution (Python):
import itertools

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

edge = [[int(s) - 1 for s in input().split()] for _ in range(M)]
graph = [[] for _ in range(N)]
for i, j in edge:
    graph[i].append(j)
    graph[j].append(i)

result = 0
for path in itertools.permutations(range(1, N)):
    cnt = 0
    for p1, p2 in zip([0] + list(path[:-1]), list(path)):
        cnt += p2 in graph[p1]
    result += cnt == (N - 1)

print(result)

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

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


def DFS(now, visited):
    if all(visited):
        return 1
    ans = 0
    for i in range(N):
        if not pathmat[now][i]:
            continue
        if visited[i]:
            continue
        visited[i]=True
        ans += DFS(i, visited)
        visited[i]=False
    return ans

print(DFS(0,visited))

Solution (Python):
import itertools

N,M = map(int,input().split())
l = [ i for i in range(2,N+1)]

dist = {i:[] for i in range(1,N+1)}

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

cnt = 0

for v in itertools.permutations(l):
  a = 1  
  for v1 in v:
    if a in  dist.get(v1):
      a = v1
      if a == v[-1]:
        cnt += 1
      continue
    else:
      break

print(int(cnt))