Problem:
 Score : 300 points    Problem Statement You are given an undirected unweighted graph with N vertices and M edges that contains neither self-loops nor double edges. Here, a self-loop is an edge where a_i = b_i (1≤i≤M) , and double edges are two edges where (a_i,b_i)=(a_j,b_j) or (a_i,b_i)=(b_j,a_j) (1≤i<j≤M) . How many different paths start from vertex 1 and visit all the vertices exactly once? Here, the endpoints of a path are considered visited.  For example, let us assume that the following undirected graph shown in Figure 1 is given.    Figure 1: an example of an undirected graph   The following path shown in Figure 2 satisfies the condition.    Figure 2: an example of a path that satisfies the condition   However, the following path shown in Figure 3 does not satisfy the condition, because it does not visit all the vertices.    Figure 3: an example of a path that does not satisfy the condition   Neither the following path shown in Figure 4, because it does not start from vertex 1 .    Figure 4: another example of a path that does not satisfy the condition       Constraints  2≦N≦8   0≦M≦N(N-1)/2   1≦a_i<b_i≦N   The given graph contains neither self-loops nor double edges.         Input The input is given from Standard Input in the following format:  N  M  a_1  b_1  a_2  b_2  :  a_M  b_M       Output Print the number of the different paths that start from vertex 1 and visit all the vertices exactly once.        Sample Input 1 3 3
1 2
1 3
2 3      Sample Output 1 2  The given graph is shown in the following figure:     The following two paths satisfy the condition:          Sample Input 2 7 7
1 3
2 7
3 4
4 5
4 6
5 6
6 7      Sample Output 2 1  This test case is the same as the one described in the problem statement.

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

l=len(x)
ans=0
for i in range(l):
    k=x[i]
    if k[0]==0:
        for j in range(n-1):
            if p[k[j]][k[j+1]]!=1:
                break
        else:
            ans+=1
            
    else:
        break
print(ans)

Solution (Python):
class Solver:
    def __init__(self, N, M, edges) -> None:
        self.N = N
        self.M = M
        self.edges = edges

    def find_next_node(self, current, visited):
        candidates = []
        for edge in self.edges:
            if edge[0] == current:
                candidates.append(edge[1])
            if edge[1] == current:
                candidates.append(edge[0])
        ret = []
        for node in candidates:
            bit = 2**(node - 1)
            if visited & bit == 0:
                
                ret.append(node)
        return ret

    def dfs(self, node, visited):
        """
        visitedのn番目のビットでノードnを訪ずれたか管理する
        """
        visited += 2**(node - 1)
        if visited == 2**self.N - 1:
            return 1
        movable_nodes = self.find_next_node(node, visited)
        return sum([self.dfs(next_node, visited) for next_node in movable_nodes])


    def solve(self) -> int:
        return self.dfs(1, 0)


if __name__ == "__main__":
    N, M = list(map(int, input().split()))
    edges = []
    for _ in range(M):
        edges.append(list(map(int, input().split())))

    s = Solver(N, M, edges)
    print(s.solve())

Solution (Python):
import itertools

n, m = map(int, input().split())
li = [list(map(int, input().split())) for i in range(m)]
iter_list = itertools.permutations(range(1, n + 1), n)


def checker(tup):
    if tup[0] != 1:
        return False
    for i in range(len(tup)-1):
        path = [tup[i], tup[i + 1]]
        re_path = [tup[i+1], tup[i]]
        if not (path in li or re_path in li):
            return False
    return True


res = 0
for i in iter_list:
    if checker(i):
        res += 1

print(res)

Solution (Python):
from itertools import permutations

N,M = map(int,input().split())
ab=[[]for i in range(N)]
for i in range(M):
    a,b = list(map(int,input().split()))
    ab[a-1].append(b-1)
    ab[b-1].append(a-1)
num = [i+1 for i in range(N-1)]
count = 0
for i in permutations(num):
    flag = True
    if i[0] not in ab[0]:
        continue
    for j in range(len(i)-1):
        if i[j+1] not in ab[i[j]]:
            flag = False
    if flag:
        count += 1
print(count)

Solution (Python):
import itertools
import numpy as np
n,m = map(int,input().split())
a = [0] * m
b = [0] * m
ans = 0
for i in range(m):
    a[i], b[i] = map(int, input().split())
    
gudge = np.zeros((n, n), dtype = np.int64)
for i in range(m):
    gudge[a[i]-1][b[i]-1] = 1
    gudge[b[i]-1][a[i]-1] = 1

retsu = [i+2 for i in range(n-1)]
p = itertools.permutations(retsu, n-1)

for v in p:
    path = [1]+list(v)
    flag = 1
    for i in range(n-1):
        if gudge[path[i]-1][path[i+1]-1] != 1:
            flag = 0
            break
            
    ans += flag
    
print(ans)

Solution (Python):
import numpy as np
import itertools

n, m = map(int, input().split())
G = np.zeros((n, n), dtype = np.int64)
for i in range(m):
    u, v = map(int, input().split())
    G[u - 1][v - 1] = 1
    G[v - 1][u - 1] = 1

ans = 0
nums = [i for i in range(1, n)]
for perm in itertools.permutations(nums):
    path = [0] + list(perm)
    ok = True
    for i in range(n - 1):
        if G[path[i]][path[i + 1]] != 1:
            ok = False
            break
    ans += ok
print(ans)

Solution (Python):
import pprint

def dfs(v, n, visited):
    all_visited = True

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

    if all_visited:
        return 1

    ret = 0
    for i in range(n):
        if edges[v][i] is False:
            continue
        if visited[i]:
            continue

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


N, M = tuple(map(int, input().split()))
nmax = 8
edges = [[False] * nmax for _ in range(nmax)]
for _ in range(M):
    A, B = tuple(map(int, input().split()))
    edges[A-1][B-1] = True
    edges[B-1][A-1] = True

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

Solution (Python):
from itertools import permutations
N,M = map(int,input().split())
table=[[]for i in range(N)]
for i in range(M):
    a,b=map(int,input().split())
    table[a-1].append(b-1)
    table[b-1].append(a-1)
 
def f(L,k):
    for a in L:
        if a==k:
            return True
    return False
 
S=[i for i in range(1,N)]
ans =0
for s in permutations(S,N-1):
    flag =True
    if not f(table[0],s[0]):
        continue
    for i in range(N-2):
        if not f(table[s[i]],s[i+1]):
            flag =False
    if flag:
        ans+=1
print(ans)

Solution (Python):
from itertools import permutations

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

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

ans = 0
for perm in permutations(range(1, N), r=N-1):
    for prev, now in zip((0,) + perm, perm):
        if not now in edges[prev]:
            break
    else:
        ans += 1

print(ans)

Solution (Python):
import sys 

sys.setrecursionlimit(10**6)

N, M = map(int, input().split())
G = [list(map(int, input().split())) for _ in range(M)]
visited = [True if v == 0 else False for v in range(N)]
adj = {i+1:[] for i in range(N)}


for g in G:
  adj[g[0]].append(g[1])
  adj[g[1]].append(g[0])
  
def dfs(adj, visited, x):
  if all(visited):
    return 1
  count = 0
  for v in adj[x]:
    if visited[v-1]:
      continue
    visited[v-1] = True
    count += dfs(adj, visited, v)
    visited[v-1] = False
  return count

print(dfs(adj, visited, 1))

Solution (Python):
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

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

def dfs(v,n,visited):
  visited[v]=True

  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

def main():
  n,m=LI()
  for _ in range(m):
    a,b=LI()
    graph[a-1][b-1]=True
    graph[b-1][a-1]=True

  visited=[False for _ in range(n)]
  visited[0]=True
  return dfs(0,n,visited)


print(main())

Solution (Python):
import itertools

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

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

num = [i for i in range(1,n)]
ans = 0


for v in itertools.permutations(num):
    bre = False
    if li[0][v[0]] == 0:
        continue
    for i in range(len(v)-1):
        if li[v[i]][v[i+1]] == 0:
            bre = True
            break
    if bre:
        continue
    else:
        ans += 1
print(ans)

Solution (Python):
n, m = map(int, input().split())
conn = [[False]*n for _ in range(n)]
visited = [False] * n
v = []
for _ in range(m):
    i, j = map(int, input().split())
    v.append([i-1, j-1])

for s, e in v:
    conn[s][e] = conn[e][s] = True
def search(now, depth):
    if visited[now] is True:
        return 0
    if depth == n-1:
        return 1
    visited[now] = True
    ret = 0
    for i in range(n):
        if conn[now][i] is True:
            ret += search(i, depth+1)
    visited[now] = False
    return ret

print(search(0, 0))

Solution (Python):
import sys

sys.setrecursionlimit(10**6)

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


def dfs(graph, visited, v):
    if all(visited):
        return 1

    cnt = 0
    for u in graph[v]:
        if visited[u]:
            continue
        visited[u] = True
        cnt += dfs(graph, visited, u)
        visited[u] = False

    return cnt


visited = [False] * len(graph)
visited[0] = True
ans = dfs(graph, visited, 0)
print(ans)

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

used = []
connect = []
N = 0
M = 0


def main():
    global used
    global connect
    global N
    global M
    sc = Scan()
    N, M = sc.intarr()
    a = [0] * M
    b = [0] * M
    for i in range(M):
        aa, bb = sc.intarr()
        a[i] = aa - 1
        b[i] = bb - 1
    connect = [[0] * N for i in range(N)]
    used = [0] * N
    for i in range(M):
        connect[a[i]][b[i]] = 1
        connect[b[i]][a[i]] = 1

    print(dfs(0, 1))


def dfs(now, depth):
    global used
    global connect
    if used[now] == 1:
        return 0

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


class Scan():

    def intarr(self):
        num_array = list(map(int, input().split()))
        return num_array

    def intarr_ver(self, n):
        return [int(input()) for _ in range(n)]

    def strarr(self):
        line = input()
        array = line.split(' ')
        array[-1] = array[-1].strip('\n')
        return array


def display(array):
    for a in range(len(array)):
        if len(array) - a != 1:
            print(array[a], end=' ')
        else:
            print(array[a])


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


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


main()

Solution (Python):
def dfs(g, v, i):
    if len(v) == len(g) - 1:
        return 1
    v.add(i)
    c = 0
    for u in g[i]:
        if u not in v:
            c += dfs(g, v, u)
    v.remove(i)
    return c


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

print(dfs(tree, set(), 0))

Solution (Python):


import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

N, M = MAP()
G = list2d(N, N, 0)
for i in range(M):
    a, b = MAP()
    a -= 1; b -= 1
    G[a][b] = G[b][a] = 1


dp = list2d(1<<N, N, 0)

dp[1][0] = 1
for S in range(1, 1<<N):
    for i in range(N):
        
        if not S & 1<<i:
            continue
        for j in range(N):
            
            if S & 1<<j:
                continue
            
            if G[i][j]:
                dp[S|1<<j][j] += dp[S][i]

ans = sum(dp[(1<<N)-1])
print(ans)

Solution (Python):


import sys
from itertools import permutations

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

N, M = MAP()
edges = set()
for i in range(M):
    a, b = MAP()
    a -= 1; b -= 1
    edges.add((a, b))
    edges.add((b, a))

cnt = 0
for perm in permutations(range(N)):
    if perm[0] != 0:
        continue
    for i in range(N-1):
        a = perm[i]
        b = perm[i+1]
        if (a, b) not in edges:
            break
    else:
        cnt += 1
print(cnt)

Solution (Python):
def dfs(g, v, i):
    if len(v) == len(g) - 1: return 1
    v.add(i)
    c = 0
    for u in g[i]:
        if u not in v: c += dfs(g, v, u)
    v.remove(i)
    return c

n, m = map(int, input().split())
g = [list() for _ in range(n)]
for _ in range(m):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    g[a].append(b)
    g[b].append(a)
print(dfs(g, set(), 0))

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

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

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

transported = [0]
count = 0

def dfs(loc):
    global count
    if graph[loc] != []:
        for i in graph[loc]:
            if i not in transported:
                transported.append(i)
                dfs(i)
                transported.remove(i)

        if len(transported) == n:
            count += 1



for i in graph[0]:
    transported = [0, i]
    dfs(i)

print(count)

Solution (Python):
import sys
import itertools
sys.setrecursionlimit(10**9)
INF=10**18
def input():
    return sys.stdin.readline().rstrip()

def main():
    N,M=map(int,input().split())
    edge=[[] for _ in range(N)]
    for i in range(M):
        a,b=map(lambda x:int(x)-1,input().split())
        edge[a].append(b)
        edge[b].append(a)
    l=list(range(1,N))
    ps=itertools.permutations(l)
    ans=0
    for p in ps:
        node=0
        for nextnode in p:
            if nextnode in edge[node]:
                node=nextnode
            else:
                break
        else:
            ans+=1
    print(ans)

if __name__ == '__main__':
    main()

Solution (Python):

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

Solution (Python):
import sys

sys.setrecursionlimit(10**6)




count = 0
def dfs(graph, v, seen):
    
    
    if not False in seen:
        global count
        count += 1
        return
    
    
    for i in graph[v]:
        
        if seen[i]:
            continue
        
        
        seen[i] = True
        
        dfs(graph, i, seen)
        
        seen[i] = False
        
    return
        
        



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)
    
seen = [False for i in range(N)]
seen[0] = True
dfs(graph, 0, seen)


print(count)

Solution (Python):
import sys


sys.setrecursionlimit(10**6)

count = 0
def dfs(graph, v, seen):

    if not False in seen:
        global count
        count += 1
        return

    
    for i in graph[v]:
        if seen[i]:
            continue
        seen[i] = True
        dfs(graph, i, seen)
        seen[i] = False
    
    return


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)

seen = [False for i in range(N)]
seen[0] = True
dfs(graph, 0, seen)

print(count)

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

g = [[] for _ in range(N)]

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

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

def dfs(v, visited):
  if all(visited):
    return 1
  total = 0
  for cv in g[v]:
    if not visited[cv]:
      visited[cv] = True
      total += dfs(cv, visited)
      visited[cv] = False
  return total
    
visited[0] = True
ret = dfs(0, visited)
print(ret)

Solution (Python):
import itertools
 
N, M = map(int, input().split())
graph = [[0] * N for i in range(N)]
for i in range(M):
    a, b = map(int, input().split())
    graph[a-1][b-1] = 1
    graph[b-1][a-1] = 1
 
p = list(itertools.permutations(range(N)))
 
Sum = 0
 
for i in range(len(p)):
    if p[i][0] != 0:
        break
    for j in range(N - 1):
        if graph[p[i][j]][p[i][j + 1]] != 1:
            break
        elif j == N - 2:
            Sum += 1
 
print(Sum)

Solution (Python):
from collections import deque

def dfs(corrent, cnt):
  if cnt == N-1:
    return 1
  visited[corrent] = True
  ret = 0
  for to in graph[corrent]:
    if visited[to] == True:
      continue
    ret += dfs(to, cnt+1)
  visited[corrent] = False
  return ret


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

ans = 0
visited = [False]*(N)

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

print(dfs(0, 0))

Solution (Python):
from itertools import permutations

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

patterns = list(permutations(range(n)))

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

ans = 0
for p in patterns:
    if p[0] != 0:
        continue
    ok = True
    for i in range(n-1):
        if not g[p[i]][p[i+1]]:
            ok = False
    if ok:
        ans += 1
print(ans)

Solution (Python):
N, M = list(map(int, input().split()))
E = [[False]*N for _ in range(N)]
for m in range(M):
    a, b = list(map(int, input().split()))
    E[a-1][b-1] = E[b-1][a-1] = True

P = []
V = [False]*N
V[0] = True
p = [0] + [None]*(N-1)
def dfs(i):
    if i==N:
        P.append(p[:])
        return
        
    for v, visited in enumerate(V):
        if not visited:
            p[i] = v
            V[v] = True
            dfs(i+1)
            V[v] = False

dfs(1)

ans = 0
for p in P:
    ok = True
    for i in range(N-1):
        if not E[p[i]][p[i+1]]:
            ok = False
            break
    if ok: ans+=1
print(ans)

Solution (Python):


import copy
import sys
input = sys.stdin.readline


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



Graph_list = [[] for i in range(N)]


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

    
    Graph_list[a].append(b)
    Graph_list[b].append(a)

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

def dfs(i, current, visited):   
    
    if i >= N-1:

        
        if all(visited):
            global ans_count
            ans_count += 1
            return 
        return 

    for j in Graph_list[current]:
        if visited[j] == False:
            
            visited[j] = True
            
            dfs(i + 1, j, visited)

            visited[j] = False

dfs(0, 0, visited)
print(ans_count)

Solution (Python):


import copy
import sys
input = sys.stdin.readline


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



Graph_list = [[] for i in range(N)]


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

    
    Graph_list[a].append(b)
    Graph_list[b].append(a)

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

def dfs(i, current, visited):   
    
    if i >= N-1:

        
        if all(visited):
            global ans_count
            ans_count += 1
            return 
        return 

    for j in Graph_list[current]:
        if visited[j] == False:
            
            visited[j] = True
            
            dfs(i + 1, j, visited)

            visited[j] = False

dfs(0, 0, visited)
print(ans_count)

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

for _ in range(m):
    a, b = map(int, input().split())
    ab.add((a, b))
    ab.add((b, a))

cnt = 0
for x in itertools.permutations(range(1, n + 1)):
    if x[0] != 1:
        break
    flag = True
    for i in range(len(x)-1):
        if (x[i], x[i + 1]) not in ab:
            flag = False
            break
    if flag:
        cnt += 1
print(cnt)

Solution (Python):
from collections import deque

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)

   
check = [0]*n
count = 0
def dfs(i):
    check[i-1] = 1
    result = 0
    if not 0 in check:
        
        return 1
        

    for j in E[i]:
        if check[j-1] == 0:
            check[j-1] = 1
            result += dfs(j)
            check[j-1]=0

    return result


print(dfs(1))

Solution (Python):
import sys
sys.setrecursionlimit(1000000)
N, M = map(int, input().split())
G = {k: [] for k in range(N)}
for _ in range(M):
    a, b = map(int, input().split())
    
    G[a-1].append(b-1)
    G[b-1].append(a-1)

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


def dfs(v):
    if all(visited):
        return 1
    r = 0
    for nv in G[v]:
        if visited[nv] is False:
            visited[nv] = True
            r += dfs(nv)
            visited[nv] = False
    return r


print(dfs(0))

Solution (Python):
import copy
n, m = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(m)]
cnt = 0
fin = set([i + 1 for i in range(n)])
def path(now, edges, past):
    global cnt
    if set(past) == fin:
        cnt += 1
        return 0
    for i in range(len(edges)):
        if now == edges[i][0] and edges[i][1] not in past:
            new_now = edges[i][1]
            new_edges = copy.deepcopy(edges)
            new_past = copy.deepcopy(past)
            new_edges.pop(i)
            new_past.append(edges[i][1])
            
            path(new_now, new_edges, new_past)
        elif now == edges[i][1] and edges[i][0] not in past:
            new_now = edges[i][0]
            new_edges = copy.deepcopy(edges)
            new_past = copy.deepcopy(past)
            new_edges.pop(i)
            new_past.append(edges[i][0])
            
            path(new_now, new_edges, new_past)

for i in range(m):
    if ab[i][0] == 1:
        edges = copy.deepcopy(ab)
        edges.pop(i)
        path(ab[i][1], edges, [1, ab[i][1]])
    elif ab[i][1] == 1:
        edges = copy.deepcopy(ab)
        edges.pop(i)
        path(ab[i][0], edges, [1, ab[i][0]])
print(cnt)

Solution (Python):



def dfs():
    path = 1
    lst_path = []
    lst_path.append((0, path))
    cnt = 0
    while len(lst_path) > 0:
        node, path = lst_path.pop()
        for i in G[node]:
            if not path & (1 << i):
                if path + (1 << i) == -1 + (1 << N):
                    cnt += 1
                    continue
                lst_path.append((i, path + (1 << i)))
    return cnt

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)
    
result = dfs()
print(result)

Solution (Python):
import itertools


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

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

ans = 0
for x in itertools.permutations(range(1, N)):
    
    flag = True
    now = 0
    for e in x:
        if not graph[now][e]:
            flag = False
        now = e
    if flag:
        ans += 1
print(ans)

Solution (Python):
from copy import copy
N, M = map(int, input().split())
br = [[] for _ in range(N)]
for _ in range(M):
    a, b = map(int, input().split())
    br[a-1].append(b-1)
    br[b-1].append(a-1)
ans = 0
stack = []
seen = [False]*N
seen[0] = True
stack.append((0, copy(seen)))
while len(stack):
    n, s = stack.pop()
    f = False
    for m in br[n]:
        if not s[m]:
            s2 = copy(s)
            s2[m] = True
            stack.append((m, s2))
            f = True
    if not f and not False in s:
        ans += 1
print(ans)

Solution (Python):
n, m = map(int, input().split())
Adj_dict = {}
for i in range(n):
    new = {i:[]}
    Adj_dict.update(new)
for _ in range(m):
    a, b = map(int, input().split())
    Adj_dict[a-1].append(b-1)
    Adj_dict[b-1].append(a-1)

Visit_list = [True] + [False for _ in range(n-1)]
count = 0

def Path(dict, start, Visited):

    if all(Visited):
        global count
        count += 1
        return

    for node in dict[start]:
        if Visited[node] == False:
            Visited[node] = True
            Path(dict, node, Visited)
            Visited[node] = False
    return

Path(Adj_dict, 0, Visit_list)
print(count)

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)
ans = 0


def dfs(v, history):
    if len(history) == N:
        global ans
        ans += 1
    else:
        children = graph[v]
        for child in children:
            if child not in history:
                dfs(child, history + (child,))


def solve():
    dfs(1, (1,))
    print(ans)


if __name__ == '__main__':
    solve()

Solution (Python):
import sys


sys.setrecursionlimit(10**6)

count = 0
def dfs(graph, v, seen):

    if not False in seen:
        global count
        count += 1
        return

    
    for i in graph[v]:
        if seen[i]:
            continue
        seen[i] = True
        dfs(graph, i, seen)
        seen[i] = False
    
    return


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)

seen = [False for i in range(N)]
seen[0] = True
dfs(graph, 0, seen)

print(count)

Solution (Python):

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

from_to_dict = dict()

for i in range(M):
    a,b = map(int, input().split())
    
    if a in from_to_dict:
        from_to_dict[a].add(b)
    else:
        from_to_dict[a] = set([b])
        
    if b in from_to_dict:
        from_to_dict[b].add(a)
    else:
        from_to_dict[b] = set([a])
        

candidate_list = [i+1 for i in range(N)]
ans = 0

for candidate in list(itertools.permutations(candidate_list)):
    if candidate[0] == 1:
        for i in range(len(candidate)-1):
            from_node = candidate[i]
            to_node = candidate[i+1]

            if to_node not in from_to_dict[from_node]:
                break
        else:
            ans += 1
                          
print(ans)

Solution (Python):
import sys

input = sys.stdin.readline
N,M=map(int,input().rstrip().split())
G=[[0 for _ in range(N)] for __ in range(N)]
used=[0 for _ in range(N)]
used[0]=True

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

def resolve():
    print(dfs(0,used))


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

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

    



from io import StringIO
import unittest

class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)
    def test_入力例_1(self):
        input = """3 3
1 2
1 3
2 3"""
        output = """2"""
        self.assertIO(input, output)
    def test_入力例_2(self):
        input = """7 7
1 3
2 7
3 4
4 5
4 6
5 6
6 7"""
        output = """1"""
        self.assertIO(input, output)

if __name__ == "__main__":
    
    resolve()

Solution (Python):
import sys
import itertools


def check(i,array):
    now=0
    while True:
        flag=0
        if(now==len(i)-1):
            return 1
        for x in array:
            if(i[now]==x[0] and i[now+1]==x[1] or \
                i[now]==x[1] and i[now+1]==x[0]):

                flag=1
                now+=1
                break

        if(flag==0):
            return 0


def main():
    N, M = map(int,input().split())

    array=[]
    sum=0

    for _ in range(0, M):
        array.append(list(map(int,input().split())))


    for i in itertools.permutations(range(1,N+1),N):
        if(i[0]==1):
            sum += check(i,array)
    print(sum)

main()

Solution (Python):
import sys
import itertools


def check(i,array):
    now=0
    while True:
        flag=0
        if(now==len(i)-1):
            return 1
        for x in array:
            if(i[now]==x[0] and i[now+1]==x[1] or \
                i[now]==x[1] and i[now+1]==x[0]):

                flag=1
                now+=1
                break

        if(flag==0):
            return 0


def main():
    N, M = map(int,input().split())

    array=[]
    sum=0

    for _ in range(0, M):
        array.append(list(map(int,input().split())))


    for i in itertools.permutations(range(1,N+1),N):
        if(i[0]==1):
            sum += check(i,array)
    print(sum)

main()