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):
def OneStrokePath():
    from collections import deque
    import copy
    n, m = map(int, input().split())
    graph = [[] for _ in range(n)]
    ans = 0
    
    for _ in range(m):
        a, b = map(int, input().split())
        graph[a-1].append(b-1)
        graph[b-1].append(a-1)
    q = deque()
    q.append([0, []])
        
    while q:
        x0, route0 = q.pop()
        if x0 in route0:
            continue
        route1 = copy.deepcopy(route0)
        route1.append(x0)
        if len(route1) == n:
            ans += 1
        for i in graph[x0]:
            if i in route1:
                continue
            q.append([i, route1])
    print(ans)  

if __name__ == '__main__':
    OneStrokePath()

Solution (Python):
def OneStrokePath():
    from collections import deque
    import copy
    n, m = map(int, input().split())
    graph = [[] for _ in range(n)]
    ans = 0
    
    for _ in range(m):
        a, b = map(int, input().split())
        graph[a-1].append(b-1)
        graph[b-1].append(a-1)
    q = deque()
    q.append([0, []])
        
    while q:
        x0, route0 = q.pop()
        if x0 in route0:
            continue
        route1 = copy.deepcopy(route0)
        route1.append(x0)
        if len(route1) == n:
            ans += 1
        for i in graph[x0]:
            if i in route1:
                continue
            q.append([i, route1])
    print(ans)  

if __name__ == '__main__':
    OneStrokePath()

Solution (Python):
import copy
N,M = map(int,input().split())
ls = [[] for i in range(N+1)]
for i in range(M):
    a,b = map(int,input().split())
    ls[a].append(b)
    ls[b].append(a)
cnt = 0
q = []
q.append([1,1,[False for i in list(range(N+1))]])
while len(q) > 0:
    [x,n,path] = q.pop()
    path[x] = True
    
    if path.count(True) == N:
        cnt += 1
        continue
    for j in ls[x]:
        if path[j] == False:
            q.append([j,n+1,path.copy()])
print(cnt)

Solution (Python):
import itertools
n,m=map(int,input().split())
num=[[] for _ in range(n)]
for i in range(m):
    a,b=map(int,input().split())
    num[a-1].append(b)
    num[b-1].append(a)
cnt=list(itertools.permutations(list(range(2,n+1))))
ans=0
for i in range(len(cnt)):
    num1=1
    num2=cnt[i]
    yn=0
    for j in range(n-1):
        if num2[j] not in num[num1-1]:
            yn=1
            break
        num1=num2[j]
    if yn==0:
        ans+=1
print(ans)

Solution (Python):
import itertools as it
n,m=map(int,input().split())
e=[[0 for i in range(n)] for j in range(n)]
for i in range(m):
  a,b=map(lambda x:int(x)-1,input().split())
  e[a][b]=1
  e[b][a]=1
 
c=0
for t in it.permutations([j+1 for j in range(n-1)]):
  i=(0,)+t
  c+=1
  for j in range(n-1):
    if e[i[j]][i[j+1]]==0:
      c-=1
      break
print(c)

Solution (Python):
import sys,os
from collections import defaultdict, deque
from math import ceil, floor
import itertools
if sys.version_info[1] >= 5:
    from math import gcd
else:
    from fractions import gcd
sys.setrecursionlimit(10**6)
write = sys.stdout.write
dbg = (lambda *something: print(*something)) if 'TERM_PROGRAM' in os.environ else lambda *x: 0
def main(given=sys.stdin.readline):
    input = lambda: given().rstrip()
    LMIIS = lambda: list(map(int,input().split()))
    II = lambda: int(input())
    MOD = 10**9+7

    N,M = LMIIS()
    edges = defaultdict(list)
    for i in range(M):
        a,b = LMIIS()
        edges[a].append(b)
        edges[b].append(a)
    ans = 0
    for l in itertools.permutations(range(2,N+1), N-1):
        prev = 1
        for v in l:
            if v in edges[prev]:
                prev = v
            else:
                break
        else:
            ans += 1
    print(ans)




if __name__ == '__main__':
    main()

Solution (Python):
import itertools as it
n,m=map(int,input().split())
e=[[0 for i in range(n)] for j in range(n)]
for i in range(m):
  a,b=map(lambda x:int(x)-1,input().split())
  e[a][b]=1
  e[b][a]=1

c=0
for t in it.permutations([j+1 for j in range(n-1)]):
  i=(0,)+t
  c+=1
  for j in range(n-1):
    if e[i[j]][i[j+1]]==0:
      c-=1
      break
print(c)

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


def dfs(node):
    if sum([1 for v in visited if v]) == N:
        return 1
    ret = 0
    for n in graph[node]:
        if visited[n]:
            continue
        visited[n] = True
        ret += dfs(n)
        visited[n] = False
    return ret


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)

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

Solution (Python):
import itertools

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


p = itertools.permutations(range(2, n + 1), n - 1)

cnt = 0
for v in p:
    if [1, v[0]] not in ab and [v[0], 1] not in ab:
        continue
    else:
        if all([n0, n1] in ab or [n1, n0] in ab for n0, n1 in zip(v, v[1:])):
            cnt += 1
print(cnt)

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

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

ans = 0
def dfs(i):
  global ans
  if all(reach[1:]):
    ans += 1
  for j in ma[i]:
    if reach[j] == 1:
      continue
    reach[j] = 1
    dfs(j)
    reach[j] = 0

reach=[0]*(n+1)
reach[1] = 1
dfs(1)
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)
    
    sum=0
    for edge in zip(l,l[1:]): 
        if tuple(sorted(edge)) in edges:
            sum+=1
    if sum==N-1:
        ans+=1
print(ans)

Solution (Python):

from math import floor, ceil, sqrt, factorial, log, gcd, log10
from itertools import accumulate, permutations, combinations, product, combinations_with_replacement, chain
from bisect import bisect_left, bisect_right
from collections import Counter, defaultdict, deque
from heapq import heappop, heappush, heappushpop, heapify
from copy import copy, deepcopy
import sys
INF = float('inf')
mod = 10**9+7
sys.setrecursionlimit(10 ** 8)


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





def LI(): return list(map(int, sys.stdin.buffer.readline().split()))




def I(): return int(sys.stdin.buffer.readline())





def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()




def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')







def IR(n): return [I() for i in range(n)]







def LIR(n): return [LI() for i in range(n)]







def SR(n): return [S() for i in range(n)]







def LSR(n): return [LS() for i in range(n)]







def SRL(n): return [list(S()) for i in range(n)]





n, m = LI()
graph = [[] for _ in range(n)]
v = [False] * n

for i in range(m):
    a, b = LI()
    graph[a - 1].append(b)
    graph[b - 1].append(a)


def dfs(now, depth):
    if v[now - 1]:
        return 0
    if depth == n-1:
        return 1
    ans = 0
    v[now - 1] = True
    for node in graph[now - 1]:
        ans += dfs(node, depth+1)

    v[now - 1] = False
    

    return ans


print(dfs(1, 0))

Solution (Python):

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

path_matrix = []


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


for m in range(M):
    line = map(int, input().split())
    paths = [x - 1 for x in line]
    path_matrix[paths[0]][paths[1]] = True
    path_matrix[paths[1]][paths[0]] = True


visited = [False] * N



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

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

    visited[now] = False

    return total_paths

print(dfs(0, 0))

Solution (Python):
import math
from math import gcd,pi,sqrt
INF = float("inf")
MOD = 10**9 + 7

import sys
sys.setrecursionlimit(10**6)
import itertools
import bisect
from collections import Counter,deque
def i_input(): return int(input())
def i_map(): return map(int, input().split())
def i_list(): return list(i_map())
def i_row(N): return [i_input() for _ in range(N)]
def i_row_list(N): return [i_list() for _ in range(N)]
def s_input(): return input()
def s_map(): return input().split()
def s_list(): return list(s_map())
def s_row(N): return [s_input for _ in range(N)]
def s_row_str(N): return [s_list() for _ in range(N)]
def s_row_list(N): return [list(s_input()) for _ in range(N)]


def main():
    global L
    N,m = i_map()
    l = [[0]*N for i in range(N)]

    for i in range(m):
        a,b = i_map()
        a -= 1
        b -= 1
        l[a][b] = 1
        l[b][a] = 1

    L = 0
    v = [0] * N
    v[0] = 1

    def dfs(n):
        global L
        if 0 not in v:
            L += 1
            return

        for i in range(N):
            if l[n][i] == 1 and v[i] == 0:
                v[i] = 1
                dfs(i)
                v[i] = 0

    dfs(0)
    print(L)



if __name__=="__main__":
    main()

Solution (Python):
import math
from math import gcd,pi,sqrt
INF = float("inf")
MOD = 10**9 + 7

import sys
sys.setrecursionlimit(10**6)
import itertools
import bisect
from collections import Counter,deque
def i_input(): return int(input())
def i_map(): return map(int, input().split())
def i_list(): return list(i_map())
def i_row(N): return [i_input() for _ in range(N)]
def i_row_list(N): return [i_list() for _ in range(N)]
def s_input(): return input()
def s_map(): return input().split()
def s_list(): return list(s_map())
def s_row(N): return [s_input for _ in range(N)]
def s_row_str(N): return [s_list() for _ in range(N)]
def s_row_list(N): return [list(s_input()) for _ in range(N)]


def main():
    N,m = i_map()
    l = [[0]*N for i in range(N)]

    for i in range(m):
        a,b = i_map()
        a -= 1
        b -= 1
        l[a][b] = 1
        l[b][a] = 1

    L = []

    def dfs(n,a):
        a = a + str(n)
        if len(a) == N:
            L.append(1)
            return

        for i in range(N):
            if l[n][i] == 1 and str(i) not in a:
                dfs(i,a)

    dfs(0,"")
    print(len(L))





if __name__=="__main__":
    main()

Solution (Python):
def dfs(place,number,checkedList,path):
  checkedList[place] = 1
  if sum(checked) == number:
    return 1
  pathNumber = 0
  for i in path[place]:
    if checkedList[i] == 1:
      continue
    pathNumber += dfs(i,number,checkedList,path)
    checkedList[i] = 0
  return pathNumber  

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

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

Solution (Python):
def li():
    return [int(x) for x in input().split()]


import itertools as it
from collections import defaultdict

N, M = li()
G = defaultdict(list)

for _ in range(M):
    a, b = li()
    G[a].append(b)
    G[b].append(a)

L = range(2, N+1)


p = it.permutations(L)
cnt = 0
for t in p:
    b = 1
    ok = True
    for i in range(len(t)):
        a, b = b, t[i]
        if b not in G[a]:
            ok = False
            break
    if ok:
        cnt += 1

print(cnt)

Solution (Python):
import itertools
N, M = map(int, input().split())
edges = [list(map(int, input().split())) for i in range(M)]
graph =[[] for i in range(N+1)]
for edge in edges:
    graph[edge[0]].append(edge[1])
    graph[edge[1]].append(edge[0])

node = [i for i in range(1, N+1)]
per_list = list(itertools.permutations(node))
count = 0
for l in per_list:
    if l[0] != 1:
        continue
    flg = 0
    for i in range(len(l)-1):
        if not (l[i+1] in graph[l[i]]):
            flg = 1
            break
    if not flg:
        count += 1

print(count)

Solution (Python):
import math as mt
import sys, string
from collections import Counter, defaultdict
input = sys.stdin.readline


I = lambda : int(input())
M = lambda : map(int, input().split())
ARR = lambda: list(map(int, input().split()))

ans = 0
def dfs(u, graph, visited, curr_len, req_len):
    global ans
    if visited[u]:
        return
    visited[u] = 1
    if curr_len == req_len:
        ans += 1
        visited[u] = 0
        return
    for kid in graph[u]:
        dfs(kid, graph, visited, curr_len+1, req_len)
    visited[u] = 0

def main():
    global ans
    n, m = M()
    graph = defaultdict(list)
    for _ in range(m):
        u, v = M()
        graph[u].append(v)
        graph[v].append(u)
    visited = [0 for _ in range(n+1)]
    dfs(1, graph, visited, 0, n - 1)
    print(ans)

tc = 1

for _ in range(tc):
    main()

Solution (Python):
from itertools import permutations
from math import factorial

n, m = map(int, input().split(' '))
edge = []
for i in range(m):
    ai, bi = map(int, input().split(' '))
    edge.append([ai, bi])

l = [i for i in range(1, n+1)]
ls = list(permutations(l))
ans = 0
for i in range(factorial(n-1)):
    y = 0
    for j in range(n-1):
        for k in edge:
            if (ls[i][j+1] in k) and (ls[i][j] in k):
                y += 1
    if y == n-1:
        ans += 1

print(ans)

Solution (Python):

def dfs(now_node, depth):
    if seen[now_node]:
        return 0
    if depth == N:
        return 1
    seen[now_node] = True  
    connect_nodes = graph[now_node]
    ans = 0
    for node in connect_nodes:
        ans += dfs(node, depth+1)
    seen[now_node] = False  
    return ans

N, M = map(int, input().split())
edges = [list(map(int, input().split())) for i in range(M)]
graph =[[] for i in range(N+1)]
for edge in edges:
    graph[edge[0]].append(edge[1])
    graph[edge[1]].append(edge[0])


seen = [False for i in range(N+1)]
seen[0] = True

print(dfs(1, 1))

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)

res = 0
for P in permutations(range(N), N):
    if P[0] != 0:
        continue
    for i in range(N - 1):
        if P[i + 1] not in G[P[i]]:
            break
    else:
        res += 1

print(res)

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)

res = 0
for P in permutations(range(N), N):
    if P[0] != 0:
        continue
    for i in range(N - 1):
        if P[i + 1] not in G[P[i]]:
            break
    else:
        res += 1

print(res)

Solution (Python):
from itertools import permutations


N, M = map(int, input().split())
S = []
for i in range(M):
    a, b = map(int, input().split())
    S.append([a, b])
    
vertex = (i+1 for i in range(N))
all_path = list(permutations(vertex))

ans = 0
for p in all_path:
    flag = True
    if p[0] == 1:
        for i in range(N-1):
            if [p[i], p[i+1]] not in S and [p[i+1], p[i]] not in S:
                flag = False
                break
        if flag:
            ans += 1
                
print(ans)

Solution (Python):
from itertools import permutations

def getval():
    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)
    return n,m,g

def main(n,m,g):
    ans = 0
    for p in permutations(range(n-1)):
        flag = True
        idx = 0
        for i in p:
            if not i+1 in g[idx]:
                flag = False
                break
            idx = i+1
        if flag:
            ans += 1
    print(ans)

if __name__=="__main__":
    n,m,g = getval()
    main(n,m,g)

Solution (Python):
import itertools

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

ans = 0
for i in itertools.permutations(pattern):
    flag = True
    if i[0] != 0:
        continue
    for j in range(len(i) - 1):
        now = i[j]
        next = i[j+1]
        if not next in G[now]:
            flag = False
    if flag:
        ans += 1
print(ans)

Solution (Python):
import itertools

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

ans = 0
for i in itertools.permutations(pattern):
    flag = True
    if i[0] != 0:
        continue
    for j in range(len(i) - 1):
        if not i[j+1] in G[i[j]]:
            flag = False
    if flag:
        ans += 1
print(ans)

Solution (Python):
from itertools import permutations
from math import factorial

n, m = map(int, input().split(' '))
edge = []

for i in range(m):
    ai, bi = map(int, input().split(' '))
    edge.append([ai,bi])


x = [i for i in range(1,n+1)]
ls = list(permutations(x))
ans = 0
for l in range(factorial(n-1)):
    cnt = 0
    for i in range(n-1):
        for j in range(m):
            if (ls[l][i] in edge[j]) and (ls[l][i+1] in edge[j]):
                cnt += 1
    if cnt == n-1:
        ans += 1


print(ans)

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

def dfs(x, G, seen):
    seen[x] = True
    flag = True
    for i in seen:
        if i == False:
            flag = False
    if flag:
        return 1
    res = 0
    for i in G[x]:
        if seen[i]:
            continue
        res += dfs(i, G, seen)
        seen[i] = False
    return res

print(dfs(0, G, seen))

Solution (Python):
from collections import defaultdict
N, M = map(int, input().split())
d = defaultdict(list)
for _ in range(M):
    a, b = map(int, input().split())
    d[a].append(b)
    d[b].append(a)


def dfs(n, path):
    count = 0
    path.append(n)
    if len(path) == N:
        count += 1
        return count

    for i in range(len(d[n])):
        if d[n][i] not in path:
            count += dfs(d[n][i], path)
            path.pop()

    return count


print(dfs(1, []))

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

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


def dfs(n, path):
    count = 0
    path.append(n)
    if len(path) == N:
        count += 1
        return count
    for i in d[n]:
        if i not in path:
            count += dfs(i, path)
            path.pop()

    return count


print(dfs(1, []))

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

checked = [0] * 8
path = [[] for _ in range(8)]

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

ans = 0

def dfs(place):
  checked[place] = 1
  if sum(checked) == N:
    return 1
  ret = 0
  for i in path[place]:
    if checked[i] == 1:
      continue
    ret += dfs(i)
    checked[i] = 0
  return ret

print(dfs(0))

Solution (Python):
N, M = map(int, input().split())
leng = [set() for i in range(N+1)]
res = 0
for _ in range(M):
  a,b = map(int, input().split())
  leng[a].add(b)
  leng[b].add(a)
def check(arr):
  for i in range(N-1):
    if arr[i+1] not in leng[arr[i]]:
      return False
  return True

import itertools
for i in itertools.permutations([x for x in range(2,N+1)]):
  if check([1]+list(i)):
    res += 1
print(res)

Solution (Python):
import collections
import copy

def dfs(i,basho,memo):
    global ans
    
    if memo[basho]==1:
        return
    memo[basho]=1
    if i == n:
        if sum(memo)==n:
            ans += 1
        return
    tmp = collections.Counter(graph[basho])
    
    for next_basho in tmp.keys():
        copy_memo = copy.copy(memo)
        dfs(i+1,next_basho,copy_memo)

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

memo = [0 for i in range(n+1)]
ans = 0
dfs(1,1,memo)
print(ans)

Solution (Python):
import sys
import itertools
sys.setrecursionlimit(10**6)

N,M=map(int,input().split())
tmp=[x for x in range(1,N)]
Cases=itertools.permutations(tmp)
G=[[] for _ in range(N)]
seen=[0]*N

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

def solve(v,case,cnt,N):
    if cnt==N-1: return True
    for nv in G[v]:
        if nv==case[cnt]:
            return solve(nv,case,cnt+1,N)
    return False

ans=0
for case in Cases:
    if solve(0,case,0,N): ans+=1
print(ans)

Solution (Python):
N, M = map(int,input().split())
adj = [set() for i in range(N+1)]
for i in range(M):
	u, v = map(int,input().split())
	adj[u].add(v)
	adj[v].add(u)

def good(p):
	for i in range(N-1):
		if p[i+1] not in adj[p[i]]:
			return False
	return True

ans = 0

from itertools import permutations
for p in permutations(range(2,N+1)):
	if good([1]+list(p)):
		ans += 1

print(ans)

Solution (Python):



class Node():
    def __init__(self, idx):
        self.idx = idx
        self.next_node = []
    
    def add_node(self, node):
        self.next_node.append(node)

N, M = map(int, input().split())
nodes = {i:Node(i) for i in range(1,N+1)}

for m in range(M):
    a,b = map(int, input().split())
    nodes[a].add_node(nodes[b])
    nodes[b].add_node(nodes[a])

def permutation_search(idxs, now_idx):
    if len(idxs) == 0:
        return 1

    num = 0
    for i in range(len(idxs)):
        next_idx = idxs[i]
        next_idxs = idxs[:i]+idxs[i+1:]
        if next_idx in [node.idx for node in nodes[now_idx].next_node]:
            num += permutation_search(next_idxs, next_idx)
    
    return num

total = permutation_search([i for i in range(2,N+1)], 1)

print(total)

Solution (Python):
import itertools
from collections import deque

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

p = [i for i in range(1,N)]
q = list(itertools.permutations(p))

s = deque()
for i in range(len(q)):
    x = 0
    flag = 0
    for y in q[i]:
        if table[x][y] == 0:
            flag = 1
            break
        x = y
    if flag == 0:
        ans += 1

print(ans)

Solution (Python):
n,m=map(int,input().split())
root=[[] for _ in range(n+1)]
for i in range(m):
    a,b=map(int,input().split())
    root[a].append(b)
    root[b].append(a)
s=[0]*(n+1)
s[0]=1
s[1]=1
ans=0
def f(a,x):
    global ans
    for i in root[a]:
        if x[i]==0:
            x[i]=1
            f(i,x)
            x[i]=0
    if x.count(1)==n+1:
        ans+=1
f(1,s)
print(ans)

Solution (Python):
def dfs(v, used):
  if not False in used: return 1
  ans = 0
  for i in range(n):
    if not matrix[v][i]: continue
    if used[i]: continue
    used[i] = True
    ans += dfs(i, used)
    used[i] = False
  return ans

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

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

print(dfs(0, used))

Solution (Python):
n,m=map(int,input().split())
road=[[] for _ in range(n+1)]
for i in range(m):
    a,b=map(int,input().split())
    road[a].append(b)
    road[b].append(a)
dp=[[0]*(n+1) for _ in range(2**n)]
dp[1][1]=1
for i in range(1,2**n):
    for j in range(1,n+1):
        for k in road[j]:
            if not (i>>(k-1))&1:
                dp[i+2**(k-1)][k]+=dp[i][j]
print(sum(dp[2**n-1]))

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

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


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


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

Solution (Python):
import numpy as np
import itertools
import queue

def accept_input():
    N,M = map(int,input().split())
    G = {}
    for _ in range(M):
        a,b = map(int,input().split())
        if a not in G:
            G[a] = [b]
        else:
            G[a].append(b)
        if b not in G:
            G[b] = [a]
        else:
            G[b].append(a)
    return N,M,G


def widthsearch(q):
    global curvisited
    movelist = [(0,1),(0,-1),(1,0),(-1,0)] 
    lastplace = ((0,0),0)
    cur = 0
    while curvisited < H*W:
        q1 = queue.Queue()
        cur += 1
        while not q.empty():
            pack = q.get()
            y = pack[0][0]
            x = pack[0][1]
            num = pack[1]
            for move in movelist:
                if y+move[0] == -1 or y + move[0] == H or x+move[1] == -1 or x + move[1] == W:
                    continue
                elif visitedlist[y+move[0]][x+move[1]] == 1:
                    continue
                elif S[y+move[0]][x+move[1]] == "
                    continue
                else:
                    visitedlist[y+move[0]][x+move[1]] = 1
                    curvisited += 1
                    q1.put(((y+move[0],x+move[1]),num+1))
            if curvisited == H*W:
                break
        q = q1
    return cur

N,M,G = accept_input()
l = []
for i in range(2,N+1):
    l.append(i)
al = 0
for comb in itertools.permutations(l, N-1):
    if comb[0] not in G[1]:
        continue
    for i in range(0,N-2):
        if comb[i+1] not in G[comb[i]]:
            break
    else:
        al += 1
print(al)

Solution (Python):
def dfs(start,path):
    res = 0
    path.append(start)
    if len(path) == N:
        res += 1
        return res
    for i in graph[start]:
        if i not in path:
            res += dfs(i,path)
            path.pop()
    return res

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

Solution (Python):
n,m=map(int,input().split())
root=[[] for _ in range(n+1)]
for i in range(m):
    a,b=map(int,input().split())
    root[a].append(b)
    root[b].append(a)
s=[0]*(n+1)
s[0]=1
s[1]=1
ans=0
def f(a,x):
    global ans
    for i in root[a]:
        if x[i]==0:
            x[i]=1
            f(i,x)
            x[i]=0
    if x.count(1)==n+1:
        ans+=1
f(1,s)
print(ans)

Solution (Python):
n,m=map(int,input().split())
root=[[] for _ in range(n+1)]
for i in range(m):
    a,b=map(int,input().split())
    root[a].append(b)
    root[b].append(a)
s=[0]*(n+1)
s[0]=1
s[1]=1
ans=0
def f(a,x):
    global ans
    for i in root[a]:
        if x[i]==0:
            z=[x[j] for j in range(n+1)]
            z[i]=1
            f(i,z)
    if x.count(1)==n+1:
        ans+=1
f(1,s)
print(ans)

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)

stack = []
stack.append([0, set()])
ans = 0
while stack:
  v, visited = stack.pop()
  visited.add(v)
  if len(visited) == N:
    ans += 1
    continue
  for child in G[v]:
    if child in visited:
      continue
    visited_c = visited.copy()
    stack.append([child, visited_c])
  
print(ans)

Solution (Python):
from itertools import permutations

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

graph = [[False]*(N+1) for i in range(N+1)]

for i ,j in Alist:
  graph[i][j] = True
  graph[j][i] = True

route = permutations(range(1,N+1))

count = 0
for i in route:
  flag = True
  if i[0] !=1:
    continue
  for j in range(N-1):
    if graph[i[j]][i[j+1]] == False:
      flag = False
      break
  
  if flag == True:
    count += 1

print(count)

Solution (Python):
from itertools import permutations

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

graph = [[False]*(N+1) for _ in range(N+1)]

for i,j in l:
    graph[i][j] = True
    graph[j][i] = True

pattern = permutations(range(1,N+1))

cnt = 0
for i in pattern:
    flag = True
    if i[0] != 1:
        continue
    for j in range(N-1):
        if graph[i[j]][i[j+1]] == False:
            flag = False
            break
    
    if flag:
        cnt += 1

print(cnt)

Solution (Python):
def dfs(g,v,depth):
    if seen[v]==True:return 0
    if depth==n:return 1
    seen[v] = True
    paths = 0
    for next_v in g[v]:
        paths += dfs(g,next_v,depth+1)
    seen[v] = False
    return paths
        
n,m = map(int,input().split())

g = [[]*(n+1) for _ in range(n+1)]

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

seen = [False]*(n+1)
    
print(dfs(g,1,1))

Solution (Python):
import itertools
n,m = map(int,input().split())
tf = [[False for _ in range(n)] for _ in range(n)]
for _ in range(m):
  ai,bi = map(int,input().split())
  ai -= 1
  bi -= 1
  tf[ai][bi] = True
  tf[bi][ai] = True
l = [i for i in range(1,n)]
c = 0
for v in itertools.permutations(l,n-1):
    if tf[0][v[0]] == True:
      flag = True
      for i in range(n-2):
        if tf[v[i]][v[i+1]] == False:
          flag = False
          break
      if flag:
        c += 1
print(c)