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, raw_input().split())
neighbor_graph = [[False] * N for _ in range(N)]
for _ in range(M):
  a, b = map(int, raw_input().split())
  neighbor_graph[a - 1][b - 1] = True
  neighbor_graph[b - 1][a - 1] = True

def find(now, checked):
  if len(checked) == N:
    return 1
  res = 0
  for i in set(range(N)) - checked:
    if neighbor_graph[now][i]:
      res += find(i, checked | {i})
  return res

print find(0, {0})

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

memo={}
for a,b in AB:
  
  memo.setdefault(a, set([])).add(b)
  memo.setdefault(b, set([])).add(a)

answer=0
from itertools import permutations
for p in permutations(list(range(2,N+1))):
  if p[0] not in memo[1]:
    continue
  for i in range(N-2):
    if p[i+1] in memo[p[i]]:
      pass
    else:
      break
  else:
    answer+=1
      
print(answer)

Solution (Python):

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


pointvisited = [False] * (n + 1)
pointvisited[0] = True
pointvisited[1] = True
ans = 0
def DFS(point):
    if all(pointvisited):
        global ans
        ans += 1
    nextpoints = findnextpoint(point)
    for nextpoint in nextpoints:
        if not pointvisited[nextpoint]:
            pointvisited[nextpoint] = True
            DFS(nextpoint)
            pointvisited[nextpoint] = False

def findnextpoint(point):
    nepo = []
    for i, a in enumerate(A):
        if a == point:
            nepo.append(B[i])
    for i, b in enumerate(B):
        if b == point:
            nepo.append(A[i])
    return nepo


DFS(1)
print(ans)

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


closed_list = [False] * N
closed_list[0] = True
cnt = 0
level = 1


def dfs(target):
    global cnt, level
    if all(closed_list):
        cnt += 1
        return
    
    for node in open_list[target]:
        
        if closed_list[node] is False:
            
            closed_list[node] = True
            
            level += 1
            dfs(node)
            level = 1
            
            closed_list[node] = False
    return


dfs(0)
print(cnt)

Solution (Python):
n,m=(int(i) for i in input().split())
mtrx=[[int(i) for i in input().split()] for j in range(m)]

mtrx+=[[mtrx[i][1],mtrx[i][0]] for i in range(m)]

mylist=[10*mtrx[i][0]+mtrx[i][1] for i in range(len(mtrx))]


perm = []
cnt=[]

def make_perm(n, m = 0):
    if n == m and perm[0]==1:
        flag=1
        for i in range(len(perm)-1):
            myval=10*perm[i]+perm[i+1]
            myval1=mylist.count(myval)
            flag=flag*myval1
        cnt.append(flag)
        
    else:
        for x in range(1, n + 1):
            if x in perm: continue
            perm.append(x)
            make_perm(n, m + 1)
            perm.pop()
            
make_perm(n)
print(sum(cnt))

Solution (Python):


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



closed_list = [False] * N
closed_list[0] = True
cnt = 0


def dfs(target):
    global cnt
    
    if all(closed_list):
        cnt += 1
        return
    for node in key_value[target]:
        
        
        if closed_list[node] is False:
            closed_list[node] = True
            dfs(node)
            closed_list[node] = False
        
    return


dfs(0)
print(cnt)

Solution (Python):
n,m=map(int,input().split())
edges=[[] for _ in range(n)]
for _ in range(m):
    a,b=map(int,input().split())
    a-=1; b-=1
    edges[a].append(b)
    edges[b].append(a)
visited=[False]*n
visited[0]=True
cnt=0

def dfs(fr):
    global cnt
    if all(visited):
        cnt+=1
        return
    for to in edges[fr]:
        if not visited[to]:
            visited[to]=True
            dfs(to)
            visited[to]=False
    return

dfs(0)
print(cnt)

Solution (Python):
from collections import defaultdict

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

edges = defaultdict(set)
used = [False] * N
for i in range(M):
    a, b = map(int, input().split())
    edges[a-1].add(b-1)
    edges[b-1].add(a-1)

def count(index):
    if all(used):
        return 1

    total = 0
    for dest in edges[index]:
        if not used[dest]:
            used[dest] = True
            total += count(dest)
            used[dest] = False
    return total

used[0] = True
print(count(0))

Solution (Python):
n,m=(int(i) for i in input().split())
mtrx=[[int(i) for i in input().split()] for j in range(m)]

mtrx+=[[mtrx[i][1],mtrx[i][0]] for i in range(m)]

mylist=[10*mtrx[i][0]+mtrx[i][1] for i in range(len(mtrx))]


perm = []
cnt=[]

def make_perm(n, m = 0):
    if n == m and perm[0]==1:
        flag=1
        for i in range(len(perm)-1):
            myval=10*perm[i]+perm[i+1]
            myval1=mylist.count(myval)
            flag=flag*myval1
        cnt.append(flag)
        
    else:
        for x in range(1, n + 1):
            if x in perm: continue
            perm.append(x)
            make_perm(n, m + 1)
            perm.pop()
            
make_perm(n)
print(sum(cnt))

Solution (Python):
N, M = map(int, input().split())
r = [[] * N for i in range(N)]
reached = [0] * N
reached[0] = 1
count = 0
 
def dfs(now):
    global count
    if all(reached):
        count += 1
    for next in r[now]:
        if reached[next] == 0:
            reached[next] = 1
            dfs(next)
            reached[next] = 0
 
for i in range(M):
    a, b = map(lambda x: int(x) - 1, input().split())
    r[a].append(b)
    r[b].append(a)
 
dfs(0)
 
print(count)

Solution (Python):
import copy

N, M = list(map(int, input().split()))
route = [[0 for i in range(N)] for l in range(N)]
count = 0
for i in range(M):
    a, b = list(map(int, input().split()))
    route[a-1][b-1] = 1
    route[b-1][a-1] = 1

queue = [[[0],i] for  i in range(N) if route[0][i]]

while len(queue):
    r = queue.pop(0)
    n = r[1]
    r[0].append(n)
    if len(r[0]) == N:
        count += 1
    else:
        for i in range(1, N):
            if route[n][i] and i not in r[0]:
                x = copy.deepcopy(r[0])
                queue.append([x, i])

print(count)

Solution (Python):
n, m = [int(x) for x in input().split(' ')]
 
edges = set([tuple(input().split(' ')) for _ in range(m)])
edges.update([(x[1], x[0]) for x in list(edges)])
 
 
def dfs(node, history):
    ans = 0
    if len(history) == n - 1:
        return 1
 
    nextnodes = [
        x[1] for x in edges if x[1] not in history and x[0] == node and x[1] != node
    ]
    history.add(node)
    for next in nextnodes:
        ans += dfs(next, history)
    history.remove(node)
    return ans
 
 
print(dfs('1', set()))

Solution (Python):
N, M = map(int, input().split())
r = [[] * N for i in range(N)]
reached = [0] * N
reached[0] = 1
count = 0

def dfs(now, pre):
    global count
    if all(reached):
        count += 1
    for next in r[now]:
        if next != pre:
            if reached[next] == 0:
                reached[next] = 1
                dfs(next, now)
                reached[next] = 0

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

dfs(0, -1)

print(count)

Solution (Python):
N, M = map(int, input().split())
r = [[] * N for i in range(N)]
reached = [0] * N
reached[0] = 1
count = 0

def dfs(now):
    global count
    if all(reached):
        count += 1
    for next in r[now]:
        if reached[next] == 0:
            reached[next] = 1
            dfs(next)
            reached[next] = 0

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

dfs(0)

print(count)

Solution (Python):
import numpy as np
N, M = map(int, input().split())
 
G = np.zeros((N, N)) 
total_path_num = 0
not_reach_node = list(range(1, N))
node = 0
 
for i in range(M):
  a, b = map(int, input().split())
  G[a-1, b-1] += 1
  G[b-1, a-1] += 1
  
def search_path(G, not_reach_node, node):
  global total_path_num
  if len(not_reach_node) == 0:
    total_path_num += 1
    return total_path_num
  
  for x in np.where((G[node] == 1))[0]:
    if (x in not_reach_node):
      not_reach_node_copy = not_reach_node.copy()
      not_reach_node_copy.remove(x)
      search_path(G, not_reach_node_copy, x)

search_path(G, not_reach_node, node)      	
 
print(total_path_num)

Solution (Python):
import itertools

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

count = 0
for V in itertools.permutations(range(1, N)):
    if V[0] in E[0] and all(V[i] in E[V[i-1]] for i in range(1, N-1)):
        count += 1
print(count)

Solution (Python):
N,M = map(int,input().split())
edges = [list() for _ in range(N)]
for i in range(M):
    a,b = map(int,input().split())
    edges[a-1].append(b-1)
    edges[b-1].append(a-1)
visited = [0]*N
cnt = 0
def dfs(u,visited):
    visited = visited[:]
    global cnt
    visited[u] = True
    if all(visited):
        cnt += 1
        return
    for v in edges[u]:
        if not visited[v]:
            dfs(v,visited)
    return 0

dfs(0,visited)
print(cnt)

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

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

def dfs(v, used):
    if not False in used:       
        return 1

    ans = 0
    for i in range(N):           
        if not adj_matrix[v][i]: 
            continue
        if used[i]:              
            continue

        used[i] = True           
        ans += dfs(i, used)
        used[i] = False          

    return ans

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

print(dfs(0, used))

Solution (Python):
n, m = map(int, input().split())
ab=[list(map(int, input().split())) for i in range(m)]
e=[[0]*10 for i in range(10)]
for abi in ab:
    e[abi[0]][abi[1]]=1
    e[abi[1]][abi[0]]=1
ans=0
def dfs(l, v):
    l.append(v)
    if len(l)==n:
        global ans
        ans+=1
        return
    for i in range(10):
        if e[v][i]==1 and i not in l:
            ll=[i for i in l]
            dfs(ll, i)
    return
dfs([],1)
print(ans)

Solution (Python):
def dfs(n,depth):
    if used[n]:
        return 0
    if depth==N:
        return 1
    used[n]=1
    ans=0
    for i in range(N):
        if connect[n][i]:
            ans+=dfs(i,depth+1)
    used[n]=0
    return ans

N,M=map(int,input().split())
used=[0]*N
connect=[[0 for i in range(N)]for j in range(N)]
a=[];b=[]

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

for i in range(M):
    connect[a[i]][b[i]]=connect[b[i]][a[i]]=1

print(dfs(0,1))

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

ans = 0

for i in itertools.permutations(range(2,N+1)):
    f = 0
    
    for n in range(0,N-2):
        
        if adj[0][i[0]-1] != 1:
            f = 1
            break
        if adj[i[n]-1][i[n+1]-1] != 1:
            
            f = 1
            break
    if f == 0:
        
        ans += 1
print(ans)

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

d = [0]*n
d[0] = 1
cnt = 0

def dfs(x):
  global cnt
  if all(d):
    cnt += 1
    return
  for i in D[x]:
    if d[i] == 0:
      d[i] = 1
      dfs(i)
      d[i] = 0

dfs(0)
print(cnt)

Solution (Python):
from itertools import permutations

n,m = map(int,input().split())
D = [[0]*n for i in range(n)]
for i in range(m):
	a,b = map(int,input().split())
	D[a-1][b-1] = 1
	D[b-1][a-1] = 1
cnt = 0
for a in permutations(range(n)):
	if a[0] != 0:
		break
	tmp = 1
	for i in range(n-1):
		tmp = tmp * D[a[i]][a[i+1]]
	cnt += tmp
print(cnt)

Solution (Python):
import itertools

N,M = (int(i) for i in input().split())
li = [[None]*N for i in range(N)]
cnt = 0

for i in range(N):
  li[i][i] = 1

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

for i in itertools.permutations(range(1,N)):
  if li[i[0]][0] == 1:
    flag = True
    for j in range(1,N-1):
      if li[i[j]][i[j-1]] == None:
        flag = False
        break
    if flag:
      cnt += 1

print(cnt)

Solution (Python):
n,m = (int(i) for i in input().split())
e = sorted([[int(i)-1 for i in input().split()] for i in range(m)])

g = [[0 for i in range(n)] for j in range(n)]
for x in e:
    g[x[0]][x[1]] = 1
    g[x[1]][x[0]] = 1

import copy
count = 0
def f(idx, arr):
    used = copy.copy(arr)
    global count
    used[idx] = 1
    if used.count(0) == 0:
        count += 1

    for i, x in enumerate(g[idx]):
        if x==1 and used[i]==0:
            f(i, used)

used = [0]*n
f(0, used)

print(count)

Solution (Python):
N,M=map(int,input().split(' '))
A=[sorted(list(map(int,input().split(' ')))) for i in range(M)]
ans=0
stack=[1]
visited=[1]
def dfs():
    global stack
    global ans
    
    if stack==[]:
        return None
    else:
        
        if len(stack)==N: 
            ans+=1
            stack.pop(0)
        else:
            for i in range(1,N+1): 
                if i not in stack and sorted([stack[0], i]) in A:
                    stack = [i] + stack
                    dfs()
            stack.pop(0)
dfs()
print(ans)

Solution (Python):
n, m = map(int, input().split())
sides = [list(map(int, input().split())) for _ in range(m)]
check = [0] * n
ans = 0

def DFS(v):
    
    if check.count(0) == 0:
        global ans
        ans += 1
        return
    for side in sides:
        if side[0] == v and check[side[1]-1] == 0:
            check[side[1]-1] = 1
            DFS(side[1])
            check[side[1]-1] = 0
        if side[1] == v and check[side[0]-1] == 0:
            check[side[0]-1] = 1
            DFS(side[0])
            check[side[0]-1] = 0
    return ans


check[0] = 1
print(DFS(1))

Solution (Python):

import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)


def read_int():
    return int(input())


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


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, M, AB):
    g = defaultdict(set)

    for a, b in AB:
        g[a].add(b)
        g[b].add(a)

    ans = 0
    for ns in permutations(range(2, N+1), N-1):
        ns = list(ns)
        ns.insert(0, 1)
        for i in range(N-1):
            if ns[i+1] not in g[ns[i]]:
                break
        else:
            ans += 1
    return ans


def main():
    N, M = read_int_n()
    AB = [read_int_n() for _ in range(M)]
    print(slv(N, M, AB))


if __name__ == '__main__':
    main()

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

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

vis_N = [-1]*(N+1)
count = 0
vis_N[1] = 1

def search(a):
    global count,vis_N,vis_Nij
    
    if sum(vis_N)+1 == N:
        count = count + 1
        return
    
    for i in range(M):
        if (P[i][0] == a and vis_N[P[i][1]] == -1) or (P[i][1] == a and vis_N[P[i][0]] == -1):
            if P[i][0] == a:
                nxt = P[i][1]
            else:
                nxt = P[i][0]
            
            vis_N[nxt] = 1
            search(nxt)
            vis_N[nxt] = -1
    
    return

search(1)
print(count)

Solution (Python):
n,m = map(int, input().split())
arr = [list() for _ in range(n)]
for _ in range(m):
  a,b = map(int, input().split())
  arr[a-1].append(b)
  arr[b-1].append(a)
d = [0]*n
d[0] = 1
cnt = 0
def dfs(x):
  global cnt
  if all(d):
    cnt += 1
    return
  for i in arr[x-1]:
    if d[i-1] == 0:
      d[i-1] = 1
      dfs(i)
      d[i-1] = 0
dfs(1)
print(cnt)

Solution (Python):
n,m = map(int, input().split())
arr = [[0]*n for _ in range(n)]
for _ in range(m):
  a,b = map(int, input().split())
  arr[a-1][b-1] = 1
  arr[b-1][a-1] = 1
d = [0]*n
d[0] = 1
cnt = 0
def dfs(x):
  global cnt
  if all(d):
    cnt += 1
  for i in range(1,n+1):
    if arr[x-1][i-1] and d[i-1] == 0:
      d[i-1] = 1
      dfs(i)
      d[i-1] = 0
dfs(1)
print(cnt)

Solution (Python):
from collections import deque


def main():
    N, M = map(int, input().split())
    adj = [set() for _ in range(N)]
    for i in range(M):
        a, b = map(int, input().split())
        adj[a-1].add(b-1)
        adj[b-1].add(a-1)
    ans = 0
    q = deque([(0, set([0]))])
    while len(q):
        cur, visited = q.popleft()
        if len(visited) == N:
            ans += 1
            continue
        for nxt in adj[cur]:
            if nxt not in visited:
                nxtvst = set(visited)
                nxtvst.add(nxt)
                q.append((nxt, nxtvst))
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):




n, m = map(int, input().split())
graph = [[] for _ in range(n)]
for _ in range(m):
    s, t = map(int, input().split())
    graph[s - 1].append(t - 1)
    graph[t - 1].append(s - 1)

ans = 0

path = [0, [0]]
stack = [path]

while len(stack) > 0:
    cur = stack.pop()
    if len(cur[1]) == n:
        ans += 1
    else:
        for g in graph[cur[0]]:
            if g not in cur[1]:
                nex = cur[1][:]
                nex.append(g)
                stack.append([g, nex])

print(ans)

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

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

visited=[]
for j in range(n):
  visited.append(False)

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

visited[0]=True

print(dfs(n,0,graph,visited))

Solution (Python):

import copy
N,M=map(int,input().split())
C={}
for m in range(M):
	a,b=list(map(int,input().split()))
	C[b]=C.get(b,[])+[a]
	C[a]=C.get(a,[])+[b]
def Search(a,check):
	ans=0
	if all(check):
		return 1
	else:
		check[a-1]=1
		for b in C[a]:
			tmp=copy.deepcopy(check)
			if check[b-1]!=1:
				tmp[b-1]=1
				ans+=Search(b,tmp)
		return ans
print(Search(1,[0]*N))

Solution (Python):
import numpy as np
from itertools import permutations
import copy

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

adj = np.zeros((n,n))

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

cnt = 0
for p in permutations(range(n)):
	if p[0]!=0:
		continue
	tmp_adj = copy.deepcopy(adj)
	for i in range(n-1):
		if tmp_adj[p[i],p[i+1]] != 1:
			
			break
	else:
		
		cnt += 1

print(cnt)

Solution (Python):
N, M = map(int, input().split())
G = [[] for i 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)
cnt = [0]
def dfs(V, s):
    V[s] = 1
    if sum(V) == N:
        cnt[0] += 1                    
    else:
        for adj in G[s]:
            if V[adj] == 0:             
                dfs(V[:adj] + [1] + V[adj + 1:], adj)
dfs([0] * N, 0)
print(cnt[0])

Solution (Python):
N,M=map(int,input().split())
from collections import defaultdict
branch=defaultdict(set)
for m in range(M):
    a,b=map(int,input().split())
    branch[a]|={b,}
    branch[b]|={a,}
    
now=1
ans=0
def go(N,now,branch,visited,ans):
    if len(visited)==N:return ans+1
    for b in branch[now]:
        if b in visited:continue
        ans=go(N,b,branch,visited|{now,b},ans)
    return ans
print(go(N,1,branch,{1,},0))

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


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

cnt = 0

def search(i,visited):
    global cnt
    if len(visited)==n:
        cnt += 1
    
    
    
    for v in to[i]:
        if v not in visited:
            search(v,visited+[v])
search(0,[0])
print(cnt)

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

to = [[] for i in range(n)]
for i in range(m):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    to[a].append(b)
    to[b].append(a)
cnt = 0
def search(i,visited):
    global cnt
    if len(visited)==n:
        cnt += 1
    for v in to[i]:
        if v not in visited:
            search(v,visited+[v])
search(0,[0])
print(cnt)

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

V = [i+1 for i in range(N)]
import itertools

ptr = list(itertools.permutations(V, N))

res = 0
for p in ptr:       
    if p[0] == 1:
        now = 1
        flag = [0 for _ in range(N)]
        flag[0] = 1
        for i in range(N-1):
            for j in range(M):
                if A[j][0] == now and A[j][1] == p[i+1]:
                    flag[A[j][1] - 1] += 1
                    now = p[i+1]
                if A[j][1] == now and A[j][0] == p[i+1]:
                    flag[A[j][0] - 1] += 1
                    now = p[i+1]
                    
        tmp = 1         
        for i in range(N):
            if flag[i] != 1:
                tmp = 0
                break
                
        res += tmp
 
print(res)

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

visited=[False]*n
count=0
def dfs(u,visited):
  global count
  visited=visited[:]
  visited[u]=True
  if all(visited):
    count+=1
    return
  for v in edges[u]:
    if not visited[v]:
      dfs(v,visited)
  return False

dfs(0,visited)
print(count)

Solution (Python):
from collections import defaultdict, deque

def main():
    n, m = map(int, input().split())
    edges = defaultdict(list)

    for _ in range(m):
        a, b = [int(s) - 1 for s in input().split()]
        edges[a].append(b)
        edges[b].append(a)
    
    visited = 1
    pos = 0
    mask = (1 << n) - 1
    print(solve(edges, pos, visited, mask))
    
def solve(edges, pos, visited, mask):
    if visited == mask:
        return 1

    s = 0
    for e in edges[pos]:
        if ((1 << e) & visited) == 0:
            s += solve(edges, e, visited | (1 << e), mask)
    
    return s

main()

Solution (Python):
import itertools

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

per=[i for i in range(2,N+1)]
permu=[]
for i in itertools.permutations(per):
    lst=[1]
    lst.extend(i)
    permu.append(lst)
num=0
for lst in permu:
    can=True
    for i in range(N-1):
        if not([lst[i],lst[i+1]] in ab) and not([lst[i+1],lst[i]] in ab):
            can=False
            break
    if can:
        num+=1
print(num)

Solution (Python):
N,M=map(int,input().split())
hen = [[False]*N for _ in range(N)]
checked = [False]*N
ans = [0]

def dfs(x):
    if checked[x]==True:
        return
    checked[x]=True
    if checked.count(False)==0:
        ans[0] += 1
        checked[x]=False
        return

    for j in range(0, N):
        if hen[x][j] == True:
            dfs(j)
    checked[x] = False



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

dfs(0)
print(ans[0])

Solution (Python):
import itertools

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

def is_path(seq):
    for idx in range(len(seq)):
        if idx == 0:
            if [1, seq[idx]] not in edges and [seq[idx], 1] not in edges:
                return False
        else:
            if [seq[idx-1], seq[idx]] not in edges and [seq[idx], seq[idx-1]] not in edges:
                return False
    return True
        
num = 0
for seq in list(itertools.permutations(list(range(2, N+1)))):
    if is_path(seq):
        num += 1
print(num)

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

to = [[] for i in range(N)]
for i in range(M):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    to[a].append(b)
    to[b].append(a)
cnt = 0
def search(i,visited):
    global cnt
    if len(visited) == N:
        cnt += 1
    for v in to[i]:
        if v not in visited:
            search(v,visited+[v])
search(0,[0])
print(cnt)

Solution (Python):
n, m = map(int, input().split())
A = [[int(i) for i in input().split()] for i in range(m)]

vis = [0] * n
vis[0] = 1

G = [[0] * n for i in range(n)]
for a, b in A:
    G[a -1][b - 1] = 1
    G[b - 1][a - 1] = 1
    
cnt = 0
    
def dfs(x):
    global cnt
    if sum(vis) == n:
        cnt += 1
        return
    for i in range(n):
        if G[x][i] == 1 and vis[i] == 0:
            vis[i] = 1
            dfs(i)
            vis[i] = 0
    return

dfs(0)
print(cnt)

Solution (Python):

from collections import defaultdict
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = SR()
    return l
mod = 1000000007






n,m = LI()
v = LIR(m)
p2 = [1]
for i in range(n):
    p2.append(p2[-1]*2)
dp = [[0 for i in range(p2[n])] for j in range(n)]
dp[0][1] = 1
for i in range(1,p2[n]):
    for k in range(n):
        for a,b in v:
            a -= 1
            b -= 1
            if k==a or k == b:
                c = p2[a]
                d = p2[b]
                if i&c and not i&d:
                    dp[b][i|d] += dp[k][i]
                if (not i&c) and i&d:
                    dp[a][i|c] += dp[k][i]
ans = 0
for i in range(1,n):
    ans += dp[i][-1]
print(ans)

Solution (Python):
from collections import defaultdict


def solve(N, ab, ne_table, start: int, used: set):
    if len(used) == N:
        return 1
    res = 0
    next_list = ne_table[start]
    for i in next_list:
        if i not in used:
            res += solve(N, ab, ne_table, i, used.union({i}))
    return res


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

    ab = [
        [int(a) - 1 for a in input().split()]
        for _ in range(M)
    ]

    ne_table = defaultdict(lambda: [])
    for (a, b) in ab:
        ne_table[a].append(b)
        ne_table[b].append(a)

    print(solve(N, ab, ne_table, 0, {0}))


if __name__ == '__main__':
    main()

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

cnt = 0
all_visited = False
def dfs(link, V, i):
    global cnt
    global all_visited
    for j in range(N):
        if V[j] == 0:
            all_visited = False
            break
        all_visited = True
    
    if all_visited == True:
        cnt += 1
        return
    
    adj = len(link[i])
    for j in range(adj):
        if V[link[i][j]] == 0:
            V[link[i][j]] = 1
            dfs(link, V, link[i][j])
            V[link[i][j]] = 0


a = list(map(int,input().split()))
N = a[0]
M = a[1]
link = [[] for i in range(N)]
visited = [0 for i in range(N)]
for i in range(M):
    temp = list(map(int,input().split()))
    link[temp[0]-1].append(temp[1]-1)
    link[temp[1]-1].append(temp[0]-1)
visited[0] = 1
dfs(link, visited, 0)
print(str(cnt))

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


COUNT = 0
def func(choose,choosen,count):
    new_count = count
    if len(choose) == 0:
        can_move =True
        for i in range(len(choosen) - 1):
            can_move = can_move and edge[choosen[i]][choosen[i+1]]
        if can_move:
            
            return count + 1
        return count
    for i in range(len(choose)):
        new_choosen = choosen + [choose[i]]
        new_count = func(choose[:i] + choose[i + 1:],new_choosen,new_count)
    return new_count

a = func([i for i in range(1,N)],[0],0)
print(a)

Solution (Python):
from collections import defaultdict
from collections import deque

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

graph = defaultdict(list)
edges = []


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

ans = 0

def dfs(graph, node_start, visited):
    global ans
    if len(set(visited)) == len(set(graph)):
        ans += 1
        return
    for node_end in graph[node_start]:
        
        if node_end not in visited:
            dfs(graph, node_end, visited + [node_end])
    return

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