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

Solution (Python):
import sys
from collections import defaultdict

input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)


def main():

    N, M = map(int, input().split())
    G = defaultdict(lambda: [])

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

    

    def dfs(v, is_visited):
        if sum(is_visited) == N:
            return 1
        ans = 0
        for u in G[v]:
            if is_visited[u]:
                continue
            is_visited[u] = True
            ans += dfs(u, is_visited)
            is_visited[u] = False

        return ans

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

    print(dfs(0, is_visited))


if __name__ == "__main__":
    main()

Solution (Python):
def DFS(s):
    global ans,color
    color[s]="black"
    if "white" not in color:
        ans +=1
    for i in M[s]:
        if color[i]=="white":
            DFS(i)
    color[s]="white"


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

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

color=["white" for _ in range(n)]
ans=0
DFS(0)

print(ans)

Solution (Python):
def DFS(s):
    global ans,color
    color[s]="gray"
    if "white" not in color:
        ans +=1
    for i in M[s]:
        if color[i]=="white":
            DFS(i)
    color[s]="white"


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

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

color=["white" for _ in range(n)]
ans=0
DFS(0)

print(ans)

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

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

ans=0
for A in permutations(range(n),n):
    if A[0]==0:
        for i in range(n):
            if i==n-1:
                ans +=1
                break
            if A[i+1] not in M[A[i]]:break

print(ans)

Solution (Python):
import itertools
from pprint import pprint

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

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





vertexes = list(itertools.permutations(range(2,n+1)))



counter = 0


for v in vertexes:
    
    for s in sides:
        if s[0] == 1 and s[1] == v[0]:
            break
        elif s[1] == 1 and s[0] == v[0]:
            break
    else:
        
        continue

    for j in range(n-2):
        for s in sides:
            if v[j] == s[0] and v[j+1] == s[1]:
                break
            elif v[j] == s[1] and v[j+1] == s[0]:
                break
        else:
            break
    else:
        counter += 1



print(counter)

Solution (Python):
import sys
readline = sys.stdin.readline
from collections import deque

def main():
    N, M = map(int, readline().rstrip().split())
    path = [[False] * N for _ in range(N)]
    for _ in range(M):
        a, b = map(int, readline().rstrip().split())
        path[a-1][b-1] = True
        path[b-1][a-1] = True
    
    que = deque([[0]])  
    cnt = 0
    while que:
        visited = que.popleft()
        if len(visited) == N:
            cnt += 1
            continue
        pre = visited[-1]
        for next in range(N):
            if next not in visited and path[pre][next]:
                que.append(visited+[next])
            
    print(cnt)

if __name__ == '__main__':
    main()

Solution (Python):
from collections import deque

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)
  graph[b-1].append(a)
  
seen = [False]*n
finished = [False]*n
count = 0

def dfs(v):
  global graph
  global seen
  global count
  
  seen[v] = True
  if seen == [True]*n:
    count += 1

  for next_v in graph[v]:
    if seen[next_v-1]: 
      continue
    dfs(next_v-1)
    
  seen[v] = False
  	
dfs(0)
print(count)

Solution (Python):
import itertools

N, M = map(int, input().split())
pl = itertools.permutations([i for i in range(1, N + 1)])
ab = [list(map(int, input().split())) for _ in range(M)]
ans = 0
for l in pl:
    if l[0] != 1:
        continue
    f = True
    for i in range(N - 1):
        if not ([l[i], l[i + 1]] in ab or [l[i + 1], l[i]] in ab):
            f = False
            break
    if f:
        ans += 1
print(ans)

Solution (Python):
import sys
from itertools import permutations
sys.setrecursionlimit(1000000) 

def main():
    input = sys.stdin.readline  
    N, M = map(int, input().rstrip().split())
    path_list = []
    for _ in range(M):
        a, b = map(int, input().rstrip().split())
        path_list.append((a-1, b-1))
        path_list.append((b-1, a-1))

    count = 0
    for path in permutations(range(1, N)):
        now_posi = 0
        for next_posi in path:
            if (now_posi, next_posi) not in path_list:
                break
            now_posi = next_posi
        else:
            count += 1
    print(count)

if __name__ == '__main__':
    main()

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

from itertools import permutations

n, m = map(int, readline().split())
graph = [[] for _ in range(n + 1)]
for i in range(m):
    a, b = map(int, readline().split())
    graph[a].append(b)
    graph[b].append(a)
ans = 0
for check in permutations(range(1, n + 1)):
    if check[0] != 1:
        break
    for u, v in zip(check, check[1:]):
        if v not in graph[u]:
            break
    else:
        ans += 1
print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(10**7)
import copy
N,M=map(int,input().split())
G=[[]for _ in range(N)]

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

ans=0
def bfs(v,chk,G):
    global ans
    
    if chk[v]!=0:
        return
    chk[v]=1
    if sum(chk)==N:
        ans+=1
    for tmp in G[v]:
        chk1=copy.copy(chk)
        bfs(tmp,chk1,G)

chk=[0]*N
bfs(0,chk,G)
print(ans)

Solution (Python):
from collections import defaultdict


n, m = map(int, input().split())
e = [list(map(int, input().split())) for _ in range(m)]
g = defaultdict(set)

for dep, dest in e:
    g[dep].add(dest)
    g[dest].add(dep)

def dfs(i, visited=[]):
    if len(visited) == n:
        return 1
    res = 0
    for node in g[i]:
        if node not in visited:
            visited.append(node)
            res += dfs(node, visited)
            visited.pop()
    return res

ans = dfs(1, visited=[1])
print(ans)

Solution (Python):
import itertools
n,m=map(int,input().split())
l=[list(map(int,input().split())) for i in range(m)]
s=list(itertools.permutations(range(1,n+1)))
count=0
for lis in s:
    flag=False
    if lis[0]==1:
        if all([lis[i],lis[i+1]] in l or [lis[i+1],lis[i]] in l for i in range(n-1)):
            count+=1          
print(count)

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

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

l = [i+1 for i in range(N)]
P = list(permutations(l))
P = P[:factorial(N-1)]

ans = 0
for p in P:
    path = True
    for i in range(len(p)-1):
        if not ((p[i],p[i+1]) in ab or (p[i+1],p[i]) in ab):
            path = False
            break
    if path:
        ans += 1

print(ans)

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

AB = []
for i in range(M):
    ab = list(map(int, input().split()))
    AB.append(ab)
    
import itertools

per = list(itertools.permutations(list(range(2, N+1))))

count = 0
for i in range(len(per)):
    
    path = [1] + list(per[i])
    
    
    for j in range(len(path)-1):
        p1 = [path[j], path[j+1]]
        p2 = [path[j+1], path[j]]
        if (p1 not in AB) and (p2 not in AB):
            break
    else:
        count += 1
        
print(count)

Solution (Python):
import itertools
import math
N, M = map(int, input().split())
a = []
ans = 0
for _ in range(M):
  a.append(set(map(int, input().split())))
for ind in itertools.permutations([i for i in range(N)]):
  if ind[0] != 0:
    break
  flag = True
  for i in range(N):
    if i == N-1:
      break
    if not(set([ind[i]+1, ind[i+1]+1]) in a):
      flag = False
  if flag:
    ans += 1
print(ans)

Solution (Python):
import itertools
n,m = map(int,input().split())
ab = []
count = 0
for i in range(m):
  ab.append(set(map(int,input().split())))
ns = [i for i in range(1,n+1)]
ptn = [i for i in list(itertools.permutations(ns)) if i[0]==1]
for i in ptn:
  first = i[0]
  for s in range(1,n):
    if {first,i[s]} not in ab:
      break
    first=i[s]
  else:
    count +=1
print(count)

Solution (Python):
import sys

N, M = map(int, sys.stdin.readline().rstrip().split())
edges = [[] for _ in range(N)]
for _ in range(M):
    a, b = map(int, sys.stdin.readline().rstrip().split())
    edges[a-1].append(b-1)
    edges[b-1].append(a-1)


ans = 0
visited = set()
def dfs(s, count):
    global ans;
    
    if count == N:
       ans += 1
       return
    visited.add(s)
    for e in edges[s]:
        if e not in visited:
            dfs(e, count+1)
    visited.remove(s)

dfs(0, 1)
print(ans)

Solution (Python):
import itertools

n, m = map(int, input().split())
AB = []
for i in range(m):
    AB.append(list(map(int, input().split())))
ct = 0
N_lis = [(i + 2) for i in range(n - 1)]
Pat = itertools.permutations(N_lis)
for one_case in Pat:
    tmp = 1
    all_flag = True
    for j in one_case:
        flag = False
        for k in range(m):
            if AB[k][0] == tmp:
                if AB[k][1] == j:
                    tmp = j
                    flag = True
                    break
            elif AB[k][1] == tmp:
                if AB[k][0] == j:
                    tmp = j
                    flag = True
                    break
        if not flag:
            all_flag = False
            break
    if all_flag:
        ct += 1
print(ct)

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

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

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

for i in range(M):
    if A[i][0] > A[i][1]: A[i][0], A[i][1] = A[i][1], A[i][0]
    graph_data[A[i][0]-1][A[i][1]-1] = graph_data[A[i][1]-1][A[i][0]-1] = 1
    
visited = [False] * N

def dfs(now, depth):
    if visited[now]:
        return 0
    if depth == N - 1:
        return 1
    
    visited[now] = True
    total_path = 0
    for i in range(0,N):
        if graph_data[now][i] == 1: 
            total_path +=  dfs(i, depth + 1)
    visited[now] = False
    
    return total_path

print(dfs(0,0))

Solution (Python):
import itertools

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

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

cnt = 0

for each in itertools.permutations(range(N)):
    if each[0] != 0:
        break
    factor = 1
    for i in range(N-1):
        factor *= adj_matrix[each[i]][each[i+1]]
    cnt += factor

print(cnt)

Solution (Python):
import itertools

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

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

count = 0
for j in itertools.permutations(range(N)):
    if j[0] != 0:
        continue
    for k in range(N):
        if k == N-1:
            count += 1
            break
        if not path[j[k]][j[k+1]]:
            break
print(count)

Solution (Python):

def dfs(node, paths, visited, n):
  
  if not False in visited:
    return 1

  count = 0

  for nn in paths[node]:
    
    if(visited[nn]):
      continue

    visited[nn] = True
    count += dfs(nn, paths, visited, n)
    visited[nn] = False

  return count

def main():
  N, M = list(map(int, input().split()))
  paths = [[] for i in range(N)]
  visited = [False] * N

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

  visited[0] = True
  print(dfs(0, paths, visited, N))


if __name__ == "__main__":
    main()

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

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



l=list(range(1,n))
p = list(permutations(l, n - 1))

ans=0
for i in p:

    flg=0
    if i[0] not in ab[0]:
        continue   
    for j in range(n-2):
        if i[j+1] in ab[i[j]]:
            continue
        else:
            flg=1
            break
    if flg==0:
        ans+=1
print(ans)

Solution (Python):
from itertools import permutations
n,m=map(int,input().split())
ab=[[] for _ in range(n)]
for i in range(m):
    a,b=map(int,input().split())
    ab[a-1].append(b-1)
    ab[b-1].append(a-1)
l=list(range(1,n))
p=list(permutations(l,n-1))
ans=0
for i in p:
    flg=0
    if i[0] not in ab[0]:
        continue   
    for j in range(n-2):
        if i[j+1] in ab[i[j]]:
            continue
        else:
            flg=1
            break
    if flg==0:
        ans+=1
print(ans)

Solution (Python):
from itertools import permutations

n, m = [int(i) for i in input().split()]
g = [[False] * n for i in range(n)]
for i in range(m):
    a, b = [int(i) - 1 for i in input().split()]
    g[a][b] = g[b][a] = True

ans = 0
for i in permutations(list(range(n)), n):
    if i[0] != 0:
        break

    for j in range(n):
        if j == n - 1:
            ans += 1
            break
        if not g[i[j]][i[j+1]]:
            break

print(ans)

Solution (Python):
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)
dp = [[0]*N for _ in range(1<<N)]

dp[1][0] = 1

for bit in range(1<<N):
  for n in range(N):
    if(bit>>n & 1 == 0):
      continue
    for to in graph[n]:
      if(bit>>to & 1 == 1):
        continue
      next_bit = bit | (1<<to)
      dp[next_bit][to] += dp[bit][n]

ans = 0
for i in range(1, N):
  ans += dp[(1<<N)-1][i]
print(ans)

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

rel_t = [[False for i in range(n)] for j in range(n)]

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

cnt=0
n_list = [i for i in range(n)]
for l in permutations(n_list,len(n_list)):
    if(l[0]!=0):
        continue
    judge=[rel_t[l[i]][l[i+1]] for i in range(n-1)]
    if all(judge):
        cnt+=1

print(cnt)

Solution (Python):
import sys
sys.setrecursionlimit(10000)
n,m = map(int,input().split())
rel = [[False for i in range(n+1)] for i in range(n+1)]
for i in range(m):
    a,b = map(int,input().split())
    rel[a][b] = True
    rel[b][a] = True

ans=0
def rec(l):
    global ans
    if(len(l)==n):
        ans+=1
    x = l[-1]
    for i in range(1,n+1):
        if(i in l):
            continue
        if(rel[x][i]):
            rec(l+[i])

rec([1])
print(ans)

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

perms = list(itertools.permutations( [_ for _ in range(n)]))

ans = 0
flg = 0
for _ in perms:
    if _[0] == 0:
        visited = [0 for _ in range(n)]
        visited[0] = 1
        for i in range(n-1):
            st = _[i]
            ed = _[i+1]
            if ed in lst[st] and visited[ed] == 0:
                visited[ed] = 1
            else:
                pass
        if sum(visited) == n:
            ans += 1
    else:
        pass          
print(ans)

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


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


def readint():
    return int(input())


def readnums():
    return map(int, input().split())


def readstrs():
    return input().split()


def main():
    N, M = readnums()
    ab = [list(readnums()) for _ in range(M)]
    l = range(2, N + 1)
    ans = 0
    for v in permutations(l):
        if [1, v[0]] in ab:
            flag = 1
            for i in range(N - 2):
                if [v[i], v[i + 1]] not in ab and [v[i + 1], v[i]] not in ab:
                    flag = 0

            if flag:
                ans += 1

    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
from itertools import permutations
def main():
    n, m = map(int, input().split())
    path = []
    for _ in range(m):
        path.append(tuple(map(int, input().split())))

    nodes = [i for i in range(2, n + 1)]
    routes = permutations(nodes, n-1)

    r = 0
    for route in routes:
        route = list(route)
        route.insert(0,1)
        for i1 in range(n-1):
            if (route[i1], route[i1+1]) not in path:
                if (route[i1+1], route[i1]) not in path:
                    break
        else:
            r += 1
    print(r)

if __name__ == '__main__':
    main()

Solution (Python):
import itertools

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

for i in itertools.permutations(range(n),n):
   if i[0] == 0:
     for j in range(n):
       if j==n-1:
         ans+=1
         break
       if not path[i[j]][i[j+1]]:
         break

print(ans)

Solution (Python):
import itertools

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

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

ans = 0


for i in itertools.permutations(range(n), n):
    
    if i[0] == 0:
        
        for j in range(n):
            
            if j == n - 1:
                ans += 1
                break
            
            if not path[i[j]][i[j + 1]]:
                break

print(ans)

Solution (Python):
N ,M = list(map(int, input().split()))
path = [[0]*N for i in range(N)]
visited = [0]*N
visited[0]=1
ans = 0
for i in range(M):
  a, b = list(map(int, input().split()))
  path[a-1][b-1]=1
  path[b-1][a-1]=1
  
def solve(i):
  global ans
  if not 0 in visited:
    ans += 1
    return
  else:
    for j in range(N):
      if path[i][j]==1 and visited[j] == 0:
        visited[j] = 1
        solve(j)
        visited[j] = 0
    return

solve(0)
print(ans)

Solution (Python):
from sys import stdin


def dfs(g, seen, n):
    all_seen = True

    for si in seen:
        if si == False:
            all_seen = False

    if all_seen:
        return 1

    ans = 0

    for m in g[n]:
        if seen[m]:
            continue

        seen[m] = True
        ans += dfs(g, seen, m)
        seen[m] = False

    return ans


def main():
    n, m = map(int, stdin.readline().split())
    ab = [map(int, stdin.readline().split()) for _ in range(m)]
    g = [[] for _ in range(n)]
    for abi in ab:
        a, b = abi
        g[a - 1].append(b - 1)
        g[b - 1].append(a - 1)
    seen = [False for _ in range(n)]
    seen[0] = True

    ans = dfs(g, seen, 0)

    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
def main():

    import itertools
    n, m = map(int,input().split())
    way_lis = []
    for _ in range(m):
        way_lis.append(list(map(int, input().split())))
    
    ans = 0

    point_lis = [x for x in range (1, n+1)]
    per_lis = list(itertools.permutations(point_lis))       
    per_1_lis = []
    for lis in per_lis:
        if lis[0] == 1:
            per_1_lis.append(lis)
    


    for town_set in per_1_lis:           
        cnt = 0
        for i in range(n-1):
            way_i = []
            
            way_i.append(town_set[i])
            way_i.append(town_set[i+1]) 
            way_i.sort()        
            
            for way in way_lis:
                
                if way_i == way:
                    cnt += 1
            if cnt == 0:
                break
            elif cnt == n-1:
                ans += 1
    print(ans)
                
            



if __name__ == "__main__":
    main()

Solution (Python):
import itertools

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

path = [[False] * N for i in range(N)]

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

count = 0
for i in itertools.permutations(list(range(N)),N):
    if i[0] == 0:
        for j in range(N):
            if j == N-1:
                count += 1
                break
            if not path[i[j]][i[j+1]]:
                break
    

print(count)

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

import itertools
T=[i+2 for i in range(N-1)]
PMT=list(itertools.permutations(T))



ans=0
for i in range(len(PMT)):
    t=[1]+list(PMT[i])
    flag=True
    for j in range(N-1):
        if t[j+1] not in MAP[t[j]]:
            flag=False
            break
    if flag:
        
        ans+=1

print(ans)

Solution (Python):

import itertools


N, M = [int(str) for str in input().strip().split()]
ab = [[int(str) - 1 for str in input().strip().split()] for _ in range(M)]


def solve():
    G = [[False] * N for _ in range(N)]
    for a, b in ab:
        G[a][b] = True
        G[b][a] = True
    ans = 0
    for p in itertools.permutations(range(1, N), N - 1):
        pp = [0] + list(p)
        ans += all([G[pp[i]][pp[i + 1]] for i in range(N - 1)])
    print(ans)

solve()

Solution (Python):
from itertools import permutations
import sys


sys.setrecursionlimit(10 ** 6)
INF = float("inf")
MOD = 10 ** 9 + 7


def input():
    return sys.stdin.readline().strip()


def main():
    N, M = map(int, input().split())
    perm = list(permutations(range(1, N)))
    edges = [[False] * N for _ in range(N)]
    for _ in range(M):
        a, b = map(int, input().split())
        a -= 1
        b -= 1
        edges[a][b] = True
        edges[b][a] = True

    ans = 0
    for P in perm:
        i = 0
        for j in P:
            if edges[i][j]:
                i = j
            else:
                break
        else:
            ans += 1

    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
import itertools
n,m=map(int,input().split())
edge=[list(map(int,input().split())) for i in range(m)]
ans=0
nums=[i for i in range(1,n+1)]
rout=itertools.permutations(nums,n)
for r in rout:
  if r[0]!=1:
    continue
  lim=0
  while lim<n-1:
    if [r[lim],r[lim+1]] in edge or [r[lim+1],r[lim]] in edge:
      lim+=1
    else:
      lim=0
      break
  if lim:
    ans+=1
print(ans)

Solution (Python):
n,m=map(int,input().split())
edge=[list(map(int,input().split())) for i in range(m)]
ans=0
rout=[[0 for i in range(n)]]
rout[0][0]=1
for i in range(2,n+1):
  rout2=[]
  for j in range(len(rout)):
    for k in range(n):
      if rout[j][k]==0:
        r=rout[j][:]
        r[k]=i
        rout2.append(r)
  rout=rout2
for r in rout:
  lim=0
  while lim<n-1:
    if [r[lim],r[lim+1]] in edge or [r[lim+1],r[lim]] in edge:
      lim+=1
    else:
      lim=0
      break
  if lim:
    ans+=1
print(ans)

Solution (Python):
from collections import deque
n , m = map(int, input().split())
r = [[0]*(9) for i in range(9)]
ans = 0
c = 0
for i in range(m):
    a , b = map(int, input().split())
    r[a][b]=1
    r[b][a]=1
d = deque([[1,[0,1,0,0,0,0,0,0,0]]])
while d:
    p=d.popleft()
    for i in range(1,n+1):
        if r[p[0]][i]==1 and p[1][i]==0:
            t=p[1].copy()
            t[i]=1
            if sum(t)==n:
                c+=1
            d.append([i,t])
            p[1][i]=0
print(c)

Solution (Python):
import itertools


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

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

    list = [x for x in range(2, n+1)]
    permutations_lis = itertools.permutations(list)

    count = 0
    for perlist in permutations_lis:
        
        i_current = 1
        i_already = {1}

        root = []

        countable = True
        for p in perlist:
            i_target = p

            found = False
            for ab in ablist:
                if ab in root:
                    continue
                if ab[0] == i_current and ab[1] == i_target:
                    root.append(ab)
                    i_current = ab[1]
                    found = True
                    break
                elif ab[1] == i_current and ab[0] == i_target:
                    root.append(ab)
                    i_current = ab[0]
                    found = True
                    break

            if not found:
                countable = False
                break

        if countable:
            count += 1

    print(count)


main()

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

graphs = list([list(map(int, input().split())) for x in range(m)])

def search_indecies(num, remainGraph, path):
    indecies = []
    for i, currentNode in enumerate(remainGraph):
        if currentNode[0] == num or currentNode[1] == num:
            others = get_other_num(currentNode, num)
            if all([x[0] != others and x[1] != others for x in path]):
                indecies.append(i)
    return indecies



def search_iterative(currentGraph, currentNodeNum, currentIndex, path):
    prev = currentNodeNum

    currentNode = currentGraph.pop(currentIndex)
    path.append(currentNode)
    if len(path) == n - 1:
        return [path]
    nextNum = get_other_num(currentNode, prev)

    nextCandidateIndecies = search_indecies(nextNum, currentGraph, path)

    pathList = []
    for nextIndex in nextCandidateIndecies:
        c = search_iterative(currentGraph[:], nextNum, nextIndex, path[:])
        pathList += c

    return pathList

def get_other_num(currentNode, prev):
    return currentNode[0] if currentNode[1] == prev else currentNode[1]


startIndecies = search_indecies(1, graphs, [])

resuts = []
for startIndex in startIndecies:
    path = []
    resuts += search_iterative(graphs[:], 1, startIndex, path)

allPaths = [r for r in resuts if len(r) > 0]
print(len(allPaths))

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

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

def dfs(v, seen):
    seen[v] = True
    if all(seen):
        return 1

    ans = 0
    for nextCandidate in graphs[v]:
        if seen[nextCandidate]:
            continue
        ret = dfs(nextCandidate, seen[:])
        ans += ret

    return ans


firstSeen = [False]*n

total = dfs(0, firstSeen)

print(total)

Solution (Python):
n,m=map(int,input().split())
ab=[set(map(int,input().split())) for _ in range(m)]
def dfs(v,visited):
  if v in visited:
    return 0
  if len(visited|{v})==n:
    return 1
  return sum(dfs(i,visited|{v}) for i in range(1,n+1) if {i,v} in ab)
print(dfs(1,set()))

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



import itertools
t = [i for i in range(N)]
l = list(itertools.permutations(t))

for i in range(len(l)):
    l[i] = list(l[i])

ans = 0
for i in range(len(l)):
    for j in range(N-1):
        if not l[i][j+1] in line[l[i][j]]:
            break
    else:
        if l[i][0] == 0:
            ans += 1

print(ans)

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

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

from itertools import permutations

ans = 0
for v in permutations([i+2 for i in range(N-1)], N-1):
    v = [1] + list(v)
    canmake = 1
    for j in range(N-1):
        if not vertex[v[j]][v[j+1]]:
            canmake = 0
            break
    if canmake:
        ans += 1
print(ans)

Solution (Python):
N,M = map(int,input().split())
vertex = [[0 for j in range(N+1)] for i in range(N+1)]
AB = [list(map(int,input().split())) for _ in range(M)]

for i in range(M):
    a,b = AB[i]
    vertex[a][b] = 1
    vertex[b][a] = 1

from itertools import permutations

ans = 0
for v in permutations([i+2 for i in range(N-1)], N-1):
    v = [1] + list(v)
    canmake = 1
    for j in range(N-1):
        if not vertex[v[j]][v[j+1]]:
            canmake = 0
            break
    if canmake:
        ans += 1
print(ans)

Solution (Python):
N,M = map(int,input().split())
vertex = [[0 for j in range(N+1)] for i in range(N+1)]
AB = [list(map(int,input().split())) for _ in range(M)]

for i in range(M):
    a,b = AB[i]
    vertex[a][b] = 1
    vertex[b][a] = 1

from itertools import permutations

ans = 0
for v in permutations([i+2 for i in range(N-1)], N-1):
    v = [1] + list(v)
    canmake = 1
    for j in range(N-1):
        if not vertex[v[j]][v[j+1]]:
            canmake = 0
            break
    if canmake:
        ans += 1
print(ans)