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

from heapq import heappush, heappop, heapify
from collections import deque, defaultdict, Counter
import itertools
from itertools import permutations, combinations
import sys
import bisect
import string
import math
import time
from fractions import gcd



def I(): return int(input())


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


def LI(): return [int(i) for i in input().split()]


def LI_(): return [int(i)-1 for i in input().split()]


def StoI(): return [ord(i)-97 for i in input()]


def ItoS(nn): return chr(nn+97)


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


def show(*inp, end='\n'):
    if show_flg:
        print(*inp, end=end)


YN = ['Yes', 'No']
MOD = 10**9+7
inf = float('inf')
IINF = 10**19
l_alp = string.ascii_lowercase
u_alp = string.ascii_uppercase
ts = time.time()
sys.setrecursionlimit(10**6)



show_flg = True


def main():
    N, M = MI()
    graph = [[] for i in range(N+1)]
    ans = 0

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

    q = deque()
    q.append((1, set([1])))

    while len(q) != 0:
        edge, visited = q.popleft()
        nxt = graph[edge]

        if len(visited) == N:
            ans += 1

        for i, e in enumerate(nxt):
            if e not in visited:
                v = visited.copy()
                v.add(e)
                q.append((e, v))
            
            

    print(ans)


if __name__ == '__main__':
    main()

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())
    a -= 1
    b -= 1
    graph[a].append(b)
    graph[b].append(a)

memo = {}
all_use = (1 << N) - 1

def rec(v, use):
    if use == all_use:
        return 1

    key = (v, use)
    if key in memo:
        return memo[key]

    res = 0
    for u in graph[v]:
        if (use >> u) & 1 == 1:
            continue

        use ^= 1 << u
        res += rec(u, use)
        use ^= 1 << u

    memo[key] = res
    return res

print(rec(0, 1))

Solution (Python):
import itertools


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

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

    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
def solve():
    def dfs(node, path, rest):
        if rest == 0:
            nonlocal ans
            ans += 1
        for next_node in adj[node]:
            if next_node not in path:
                dfs(next_node, path + [next_node], rest - 1)
                
    
    from sys import stdin
    f_i = stdin
    
    N, M = map(int, f_i.readline().split())
    
    adj = [[] for i in range(N)]
    for i in range(M):
        a, b = map(int, f_i.readline().split())
        a -= 1
        b -= 1
        adj[a].append(b)
        adj[b].append(a)
    
    ans = 0
    dfs(0, [0], N - 1)
    
    print(ans)

solve()

Solution (Python):
import itertools
n,m = map(int,input().split())
s = set()
for i in range(m):
    a,b = map(int,input().split())
    s.add((a,b))
    s.add((b,a))
ans = 0

for i in itertools.permutations(range(2,n+1)):
    genzai = 1
    
    for j in range(len(i)):
        if (genzai,i[j]) not in s:
            break
        genzai = i[j]
    else:
        ans += 1
print(ans)

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



cho=[]
for i in range(n):
  temp=[]
  for x,y in li:
    if x==i+1:
      temp.append(y)
    if y==i+1:
      temp.append(x)
  cho.append(temp)



ans=0



zumi=[1]
queue=[[cho[0],0,len(cho[0])]]
dankai=0


while 1:
  
  if queue[dankai][1]<queue[dankai][2]:
    bango=queue[dankai][0][queue[dankai][1]]
    if bango not in zumi: 
      dankai+=1
      
      zumi.append(bango) 
      queue.append([cho[bango-1],0,len(cho[bango-1])])
      
      if dankai==n-1:
        ans+=1 
    else: 
      
      queue[dankai][1]+=1
  else:
    
    dankai-=1
    if dankai<0:
      break
    
    zumi.pop()
    queue.pop()
    queue[dankai][1]+=1
    
print(ans)

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):
    a,b = map(int, input().split())
    path_matrix[a-1][b-1] = True
    path_matrix[b-1][a-1] = True


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(N):
        if path_matrix[now][i]:
            total_path += dfs(i,depth+1)

    visited[now] = False

    return total_path


print(dfs(0,0))

Solution (Python):

import sys, math, itertools, collections, bisect
sys.setrecursionlimit(10**7)
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf')
ans = 0 ;count = 0 ;pro = 1

n,m=map(int,input().split())
data=[[] for i in range(n)]
for i in range(m):
    a,b=map(int,input().split())
    a-=1;b-=1
    data[a].append(b)
    data[b].append(a)
def dfs(node,s):
    
    if len(s)==n:
        global count
        count+=1
    s=s.copy()
    for vi in data[node]:
        if vi not in s:
            dfs(vi,s|{vi})
dfs(0,{0})
print(count)

Solution (Python):
import itertools

def main():
    N, M = map(int, input().split())
    VE = tuple(tuple(map(lambda x: int(x)-1, input().split())) for _ in range(M))
    

    adj_mat = [[0 for _ in range(N)] for _ in range(N)]
    for ve in VE:
        adj_mat[ve[0]][ve[1]] = 1
        adj_mat[ve[1]][ve[0]] = 1
    
    

    ans = 0
    for perm in itertools.permutations([i for i in range(1, N)]):
        
        flag = True
        now_V = 0
        for next_V in perm:
            
            
            if not adj_mat[now_V][next_V]:
                flag = False
                break
            now_V = next_V
        if flag:
            ans += 1

    print(ans)

if __name__ == '__main__':
    main()

Solution (Python):
import itertools

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

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

if N == 1:
    print(1)
    exit()

for x in itertools.permutations(range(1, N), N-1):
    prev = 0
    for i in range(N-1):
        if G[prev][x[i]] == 0:
            break

        prev = x[i]

        if i == N-2:
            cnt += 1

print(cnt)

Solution (Python):
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
from pprint import pprint
from copy import deepcopy
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce
from pprint import pprint


sys.setrecursionlimit(2147483647)
INF = 10 ** 13
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)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 100000000

n, m = LI()
G = [[0] * n for _ in range(n)]
for u, v in LIR(m):
    G[u - 1][v - 1] = 1
    G[v - 1][u - 1] = 1


cnt = 0
for path in permutations(range(1, n)):
    for i in range(1, len(path)):
        if not G[path[i - 1]][path[i]]:
            break
    else:
        if G[0][path[0]]:
            cnt += 1

print(cnt)

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

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

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

graph=[[0]*8 for _ in range(8)]
def dfs(v,visited):
    if sum(visited) == N:
        return 1
    ret =0
    for i in range(N):
        if graph[v][i] == 1 and visited[i] == 0:
            visited[i]=1
            ret += dfs(i,visited)
            visited[i]=0
    return ret
def main():
    """code here"""

    for i in range(M):
        a=ab[i][0]
        b=ab[i][1]
        graph[a-1][b-1]=1
        graph[b-1][a-1]=1

    visited=[0]*N
    visited[0]=1
    print(dfs(0,visited))
    
if __name__ == '__main__':
    main()

Solution (Python):
import sys

n, m = map(int, sys.stdin.readline().split())
ab = map(int, sys.stdin.read().split())
ab = zip(*[ab] * 2)
graph = [[] for _ in range(n)]
for a, b in ab:
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)

def main():
    ramain = 2 ** n - 1
    cnt = 0
    stack = [(0, 0)]
    while stack:
        v, visited = stack.pop()
        visited ^= 2 ** v
        if not visited ^ ramain: 
            cnt += 1
            continue
        for u in graph[v]:
            if visited >> u & 1:
                continue
            stack.append((u, visited))

    return cnt

if __name__ == '__main__':
    ans = main()
    print(ans)

Solution (Python):
import sys

n, m = map(int, sys.stdin.readline().split())
ab = map(int, sys.stdin.read().split())
ab = zip(*[ab] * 2)
graph = [[] for _ in range(n)]
for a, b in ab:
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)

def main():

    cnt = 0
    stack = [(0, set())]
    while stack:
        v, visited = stack.pop()
        visited.add(v)
        if len(visited) == n: 
            cnt += 1
            continue
        for u in graph[v]:
            if u in visited:
                continue
            stack.append((u, visited.copy()))

    return cnt

if __name__ == '__main__':
    ans = main()
    print(ans)

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

def search(now, hist,cnt):
    for i in tree[now]:
        if i in hist:
            pass
        else:
            cnt = search(i, hist+[i],cnt)
    if len(hist)==n: 
        return cnt + 1
    else: 
        return cnt
print(search(1,[1],0))

Solution (Python):
import itertools

n, m = map(int, list(input().split(' ')))
paths = {}
for i in range(m):
    a, b = map(int, list(input().split(' ')))
    if a in paths:
        paths[a].add(b)
    else:
        paths[a] = set([b])

ans = 0
for t in itertools.permutations(range(2, n+1), n - 1):
    arr = list(t)
    arr.insert(0, 1)
    for i in range(len(arr) - 1):
        a = arr[i]
        b = arr[i + 1]
        if a > b:
            tmp = a
            a = b
            b = tmp
        if not a in paths:
            break
        if not b in paths[a]:
            break
    else:
        ans += 1

print(ans)

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

Solution (Python):
import queue,sys,collections,math,random;sys.setrecursionlimit(10**7)
def Is(): return [int(x) for x in sys.stdin.readline().split()]
def Ss(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

N,M = Is()
mat = [[] for _ in range(N) ]
for _ in range(M):
    a,b = Is()
    a,b = a-1, b-1
    mat[a].append(b)
    mat[b].append(a)

c = 0
def dfs(visited,now):
    if len(visited) == N:
        global c
        c += 1
    else:
        q = mat[now]
        for e in q:
            if not e in visited:
                dfs(visited+[e],e)
dfs([0],0)
print(c)

Solution (Python):
import sys
if sys.platform == 'ios':
	sys.stdin = open('input.txt')
	
n,m = map(int,input().split())


path = {i+1:[] for i in range(n)}


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


chk = [i for i in range(2,n+1)]
ans = 0

import itertools



for way in itertools.permutations(chk):
	
	now = 1
	f = 0
	
	for j in way:
		if j in path[now]:
			f = f + 1
			now = j
		else:
			break
		
	if f + 1 == n: 
		ans = ans + 1

print(ans)

Solution (Python):
from sys import stdin
from itertools import permutations
inf = 10**10
n,m = [int(x) for x in stdin.readline().rstrip().split()]
li = [list(map(int,stdin.readline().rstrip().split())) for _ in range(m)]
lin = [[0 for i in range(n)]for j in range(n)]
for i in li:
    lin[i[0]-1][i[1]-1] = 1
    lin[i[1]-1][i[0]-1] = 1
def all_pairs_shortest_paths(W):
    n = len(W)
    res = [[0] * n for i in range(n)]
    for i in range(n):
        for j in range(i, n):
            if i == j:
                val = 0
            elif W[i][j]:
                val = W[i][j]
            else:
                val = inf
            res[i][j] = res[j][i] = val
    for k in range(n):
        for u in range(n):
            for v in range(n):
                res[u][v] = min(res[u][v], res[u][k] + res[k][v])
    return res
lis = all_pairs_shortest_paths(lin)
liv = [i+1 for i in range(n-1)]
liv = list(permutations(liv))
count = 0
for i in liv:
    keiro = list(i)
    flag = 0
    now = 0
    for j in keiro:
        if lis[now][j] == inf or lis[now][j] != 1:
            flag = 1
        now = j
    if flag == 0:
        count += 1
print(count)

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):
import itertools as it

N, M = map(int, input().split())
graph = [[] for i in range(N)]
for i in range(M):
    a, b = map(int, input().split())
    a, b = a - 1, b - 1
    graph[a].append(b)
    graph[b].append(a)
ans = 0
for path in it.permutations(range(N)):
    if path[0] != 0:
        break
    is_connected = True
    for ith_edge in range(len(path) - 1):
        if path[ith_edge + 1] not in graph[path[ith_edge]]:
            is_connected = False
            break
    if is_connected:
        ans += 1
print(ans)

Solution (Python):
import itertools as it

N, M = map(int, input().split())
graph = [[] for i in range(N)]
for i in range(M):
    a, b = map(int, input().split())
    a, b = a - 1, b - 1
    graph[a].append(b)
    graph[b].append(a)
ans = 0
for path in it.permutations(range(N)):
    if path[0] != 0:
        continue
    is_connected = True
    for ith_edge in range(len(path) - 1):
        if path[ith_edge + 1] not in graph[path[ith_edge]]:
            is_connected = False
            break
    if is_connected:
        ans += 1
print(ans)

Solution (Python):
import itertools

n,m = map(int, input().split())
edge_set = {tuple(map(int, input().split())) for _ in range(m)}
counter = 0

for i in itertools.permutations(range(2, n+1), n-1):
  path = [1] + list(i)
  path_set = {tuple(sorted(edge)) for edge in zip(path, path[1:])}
  
  if path_set <= edge_set:
    counter += 1
 
  
print(counter)

Solution (Python):
from itertools import permutations
n,m=map(int,input().split())
A=[list(map(int, input().split())) for i in range(m)]
N=list(permutations([i+2 for i in range(n-1)]))
count=0
for k in range(len(N)):
    flag=0
    for i in range(n-1):
        if i ==0:
            for j in range(m):
                if set([N[k][0],1])== set(A[j]):
                    flag+=1
            if flag==n-1:
                count+=1
        else:
            for j in range(m):
                if set([N[k][i],N[k][i-1]])== set(A[j]):
                    flag+=1
            if flag==n-1:
                count+=1
print(count)

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

ans = 0

def dfs(n, visited):
    global ans
    visited.append(n)
    if len(visited) == N:
        ans += 1
    else:
        for i in l[n-1]:
            if i not in visited:
                dfs(i, visited)
    visited.remove(n)

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

dfs(1, [])
print(ans)

Solution (Python):

import sys
sys.setrecursionlimit(10**5)

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

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

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


def solve(visited, node):
    visited[node] = True
    if all(visited):
        return 1

    cnt = 0
    for b in es[node]:
        if not visited[b]:
            cnt += solve(visited[:], b)

    return cnt


vis = [False] * N
ans = solve(vis, 0)
print(ans)

Solution (Python):
import itertools

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

for p in itertools.permutations(range(1, N + 1)):
    if p[0] == 1:
        ans += 1
        for i in range(N - 1):
            if not (min(p[i], p[i + 1]), max(p[i], p[i + 1])) in AB:
                ans -= 1
                break

print(ans)

Solution (Python):
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
mod2 = 998244353
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpln(n): return list(int(sys.stdin.readline()) for i in range(n))

n,m = inpl()
g = [[] for i in range(n)]
for i in range(m):
    a,b = inpl()
    a -= 1
    b -= 1
    g[a].append(b)
    g[b].append(a)
res = 0
seen = [False] * n
seen[0] = True
def dfs(node,seen):
    global res
    if sum(seen) == n:
        res += 1
        return 0
    for now in g[node]:
        if not seen[now]:
            seen[now] = True
            dfs(now,seen)
            seen[now] = False
dfs(0,seen)
print(res)

Solution (Python):
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
mod2 = 998244353
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpln(n): return list(int(sys.stdin.readline()) for i in range(n))

n,m = inpl()
g = [[] for i in range(n)]
for i in range(m):
    a,b = inpl()
    a -= 1
    b -= 1
    g[a].append(b)
    g[b].append(a)
res = 0
seen = [False] * n
def dfs(node,seen):
    global res
    seen[node] = True
    if sum(seen) == n:
        res += 1
    for now in g[node]:
        if not seen[now]:
          dfs(now,seen)  
    seen[node] = False
dfs(0,seen)
print(res)

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

seen = [False] * N

def dfs(node, seen, ans):
    seen[node] = True
    
    if seen.count(True) == N:
        ans += 1
        seen[node] = False
        return ans

    for todo in edge[node]:
        if not seen[todo]:
            ans = dfs(todo, seen, ans)

    seen[node] = False
    return ans

print(dfs(0, seen, 0))

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

from collections import defaultdict
graph = defaultdict(list)
for i in range(m):
    a = ab[i][0] - 1
    b = ab[i][1] - 1
    graph[a].append(b)
    graph[b].append(a)

ans = 0
import itertools
for orders in itertools.permutations(list(range(n))):
    if orders[0] != 0:
        continue

    
    f = True
    for j in range(len(orders) - 1):
        if orders[j+1] not in graph[orders[j]]:
            f = False
    if f:
        ans += 1
        

print(ans)

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

def dfs(now):
    ans = 0
    visited[now] = True
    
    if all(visited):
        visited[now] = False
        return 1

    for next_node in graph[now]:
        if visited[next_node]:
            continue
        ans += dfs(next_node)
    visited[now] = False
    return ans


print(dfs(0))

Solution (Python):
import itertools

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

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

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

for i in range(len(l)):
	count = 0
	for j in range(len(l[i])-1):
		tmp = [l[i][j],l[i][j+1]]
		if j == 0:
			if tmp[0] != 1:
				break
		tmp.sort()
		if tmp not in ab:
			break
		count += 1
		if count == n-1:
			ans += 1

print(ans)

Solution (Python):
from itertools import permutations

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

print(sum(all(({0, per[i]} if not i else {per[i - 1], per[i]}) in graph for i in range(n - 1)) for per in permutations(i for i in range(1, n))))

Solution (Python):
from itertools import permutations

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

per_list = permutations(i for i in range(1, n))

ans = 0

for per in per_list:
    for i in range(n - 1):
        target = {0, per[i]} if not i else {per[i - 1], per[i]}
        if target not in graph:
            break
    else:
        ans += 1

print(ans)

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())
    a -=1
    b-=1
    graph[a].append(b)
    graph[b].append(a)
def all_visited(l):
    a = 0
    for i in range(n):
        if l[i]:
            a+=1
    if a == n:
        return 1
    else: return 0
def dfs(now):

    ans = 0
    visited[now] = 1
  
    if all_visited(visited):
        
        return 1
    for next in graph[now]:
        if visited[next]:continue
        ans += dfs(next)
        visited[next] =0
    return ans
visited = [0]*n
print(dfs(0))

Solution (Python):

def search(N,adj):
    visited={1:[1]}
    S=[[1]]
    paths=[]
    while len(S)!=0:
        p=S.pop()
        if len(p)==N:
            paths.append(p)
        else:
            for w in adj[p[-1]]:
                if w not in p:
                    S.append(p+[w])
    return paths


if __name__ == '__main__':
    N,M=list(map(int,input().split()))
    ad={x:[] for x in range(1,N+1)}
    for i in range(M):
        a,b=list(map(int,input().split()))
        ad[a].append(b)
        ad[b].append(a)
    print(len(search(N,ad)))

Solution (Python):
import sys
n, m = [int(i) for i in sys.stdin.readline().split()]
graph = {i : [] for i in range(n)}
INF = 10 ** 18
for i in range(m):
    a, b = [int(i) for i in sys.stdin.readline().split()]
    a -= 1
    b -= 1
    graph[a].append(b)
    graph[b].append(a)


memo_ls = [[-1 for j in range(n)] for i in range(1 << n)]

def bit_dp(s, v):
    if memo_ls[s][v] >= 0:
        return memo_ls[s][v]
    if s == (1 << n) - 1:
        return 1
    res = 0
    for i in graph[v]:
        already = s >> i
        if not (already & 1):
            res += bit_dp((s | (1 << i)), i)
    memo_ls[s][v] = res
    return res

res = bit_dp(1, 0)
print(res)

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

for i in range(M):
  a, b=map(int, input().split())
  a-=1
  b-=1
  net[a][b]=1
  net[b][a]=1
  
def f(N):
  nums=[i for i in range(1, N)]
  out=g([0], nums)
  return out

def g(order, nums):
  k=len(nums)
  if k==1:
    return [order+nums]
  else:
    out=[]
    for i in range(k-1):
      temp=g(order+[nums[i]], nums[:i]+nums[i+1:])
      out+=temp
    temp=g(order+[nums[-1]], nums[:-1])
    out+=temp
    return out
  
orderlists=f(N)
counter=0
for orderlist in orderlists:
  k=0
  for i in range(N-1):
    k+=net[orderlist[i]][orderlist[i+1]]
  if k==N-1:
    counter+=1
    
print(counter)

Solution (Python):
N, M = map(int, input().split())
Bs = [[] for _ in range(N + 1)]
for _ in range(M):
    a, b = map(int, input().split())
    Bs[a].append(b)
    Bs[b].append(a)
import heapq
import copy

st = []
ap = [{1: True}]
heapq.heappush(st, (1, 0))
c = 0
while len(st) > 0:
    (node, log) = heapq.heappop(st)
    for b in Bs[node]:
        if b in ap[log]:
            continue
        elif len(ap[log]) == N - 1:
            c += 1
        else:
            heapq.heappush(st, (b, len(ap)))
            newlog = copy.copy(ap[log])
            newlog[b] = True
            ap.append(newlog)
print(c)

Solution (Python):
import copy
n, m = map(int, input().split())
adjacent_list = [[] for i in range(n+1)]
for i in range(m):
    a, b = map(int, input().split())
    adjacent_list[a].append(b)
    adjacent_list[b].append(a)
ans = 0

def dfs(node, finished):
    
    finished.add(node)
    global ans
    if len(finished) == n:
        ans += 1
    else:
        for i in adjacent_list[node]:
            if i not in finished: 
                passed = copy.deepcopy(finished)
                dfs(i, passed)
dfs(1,set([1]))
print(ans)

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

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


def dfs(node, track):
    if len(track) == N:
        global res
        res += 1
    else:
        for dst in [x for x in edges[node] if x not in track]:
            dfs(dst, track + tuple([dst]))


res = 0
dfs(0, tuple([0]))
print(res)

Solution (Python):
from copy import deepcopy

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

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

path = [0]*n
path[0] = 1



def func(i,path,ans):
    
    if path.count(1) == n:
        return ans+1
    flag = 1
    for g in graph[i]:
        if path[g] == 0:
            flag = 0
            next_path = deepcopy(path)
            next_path[g] = 1
            ans = func(g,next_path,ans)
    return ans
ans = func(0,path,0)
print(ans)

Solution (Python):
from itertools import permutations as P
N, M = map(int, input().split())

web = [set() for _ in range(N)]
for _ in range(M):
	a, b = map(int, input().split())
	web[a-1].add(b-1)
	web[b-1].add(a-1)
way = list(P(range(1, N), N-1))
res = 0
for i in range(len(way)):
	if way[i][0] in web[0]:
		flag = True
		for j in range(1, N-1):
			if way[i][j] not in web[way[i][j-1]]:
				flag = False
				break
		if flag: res += 1

print(res)

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

graph = [[0] * N for _ in range(N)]

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

count = 0
i = 0
memo = []
def DepthFirstSearch(i):
    global count
    memo.append(i + 1)
    if len(memo) == N:
        count += 1
        return
    for j in range(N):
        if graph[i][j] == 1:
            if j+1 in memo:
                continue
            DepthFirstSearch(j)
            memo.pop()
    return count

print(DepthFirstSearch(i))

Solution (Python):
from itertools import permutations
N, M = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(M)]

P = list(permutations([i for i in range(2, N + 1)]))
ans = 0
for p in P:
    flag = True
    for j in range(len(p) - 1):
        if j == 0:
            a = 1
            b = p[j]
            if [a, b] not in ab:
                flag = False
        a = min(p[j], p[j + 1])
        b = max(p[j], p[j + 1])
        if [a, b] not in ab:
            flag = False
    if flag:
        ans += 1
print(ans)

Solution (Python):
from itertools import product, permutations,combinations

N, M = map(int, input().split())
rel = [tuple(map(int, input().split())) for i in range(M)]
memo = [[0]*N for i in range(N)]
for r in rel:
        memo[r[0]-1][r[1]-1] = 1
        memo[r[1]-1][r[0]-1] = 1

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

cnt = 0
for i in permutations(V, N):
    if i[0] > 1:
        break
        
    for j in range(N-1):
        if memo[i[j]-1][i[j+1]-1] == 0:
            break
    else:
        cnt+=1

print(cnt)

Solution (Python):
import itertools
n,m=map(int,input().split())
p=[[False]*n for i in range(n)]

for i in range(m):
    a,b=map(int,input().split())
    a-=1
    b-=1
    p[a][b]=True
    p[b][a]=True
ans=0
for i in itertools.permutations(range(1,n),n-1):
    list=[0]+[k for k in i]
    if all(p[list[j]][list[j+1]]==True for j in range(n-1)):
        ans+=1
print(ans)

Solution (Python):
import itertools
n,m=map(int,input().split())
p=[[False]*n for i in range(n)]

for i in range(m):
    a,b=map(int,input().split())
    a-=1
    b-=1
    p[a][b]=True
    p[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 p[i[j]][i[j+1]]:
                break
print(ans)