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
read = sys.stdin.readline


from itertools import permutations


def read_ints():
    return list(map(int, read().split()))


N, M = read_ints()
from collections import defaultdict
graph = defaultdict(lambda: [])
for m in range(M):
    a, b = read_ints()
    graph[a].append(b)
    graph[b].append(a)


def is_ok(p):  
    for now, nx in zip(p, p[1:]):
        if nx not in graph[now]:
            return 0
    return 1


ans = 0
for perm in permutations(range(2, N + 1)):
    perm = [1] + list(perm)
    ans += is_ok(perm)

print(ans)

Solution (Python):
from itertools import permutations

N,M = list(map(int, input().split()))
S = set([])
for _ in range(M):
    A,B = list(map(int, input().split()))
    S.add((A,B))
    S.add((B,A))
count = 0
node = [i for i in range(1,N+1)]
lis = list(permutations(node))

for v in lis:
    flag = 0
    if v[0] != 1:
        continue
    for i in range(N-1):
        if (v[i],v[i+1]) in S:
            continue
        else:
            flag += 1
    if flag == 0:
            count += 1

print(count)

Solution (Python):
from itertools import permutations
def solve(N,C):
    node = [i for i in range(1,N+1)]
    lis = list(permutations(node))
    ans = 0
    for v in lis:
        flag = 0
        if v[0] != 1:
            continue
        for i in range(N-1):
            if (v[i],v[i+1]) in C:
                continue
            else:
                flag += 1
        if flag == 0:
            ans += 1
    return ans


def main():
    N,M = map(int,input().split(" "))
    C = set([])
    for _ in range(M):
        a,b = map(int,input().split(" "))
        C.add((a,b))
        C.add((b,a))
    print(solve(N,C))

if __name__ == "__main__":
    main()

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

ans = 0
st = [[0, [False] * N]]
while len(st) > 0:
    _st = st.pop()
    v = _st[0]
    visited = copy(_st[1])
    if visited[v]:
        continue
    visited[v] = True
    adj_all_visit = True
    for adj in G[v]:
        if visited[adj]:
            continue
        st.append([adj, visited])
        adj_all_visit = False
    if adj_all_visit and all(visited):
        ans += 1
print(ans)

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

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

visited = [False] * (n+1)

stack = [(1, 1, visited)]

count = 0
while stack:
    now, dist, visited_ = stack.pop()
    visited = visited_.copy()
    visited[now] = True
    if dist == n:
        count += 1
    for neighbor in graph[now]:
        if not visited[neighbor]:
            stack.append((neighbor, dist + 1, visited))

print(count)

Solution (Python):
import numpy as np

N, M = map(int, input().split())
adj = np.zeros((N+1, N+1))
for m in range(M):
  a, b = map(int, input().split())
  adj[a, b] = 1
  adj[b, a] = 1

from itertools import permutations

nodes = [n for n in range(2, N+1)]
ans = 0

for case in permutations(nodes):
  success = True
  for i, nd in enumerate(case):
    if i == 0:
      f = 1
    else:
      f = case[i-1]

    t = case[i]

    if adj[f, t] != 1:
      success = False
      break

  if success:
    ans += 1

print(ans)

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

def go(curr, used, count):
  if count == 1:
    return 1
  tmp = used + [curr]
  return sum(go(node, tmp, count - 1) for node in g[curr] if node not in used)

print(go(0, [], n))

Solution (Python):
def f(i):
    global ans
    if i == n - 1:
        if G[0][s[0]] == 0:
            return
        t = sorted(s)
        for j in range(n - 2):
            if t[j] == t[j + 1]:
                return
        for j in range(n - 2):
            if G[s[j]][s[j + 1]] == 0:
                return
        ans += 1
        return
    for j in range(n - 1, 0, -1):
        f(i + 1)
        s[i] = j

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

Solution (Python):
from collections import defaultdict, deque

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

D = defaultdict(set)
for a, b in AB:
    D[a].add(b)
    D[b].add(a)

ans = 0
queue = deque([(1, {1})])
while queue:
    q = queue.popleft()
    for x in D[q[0]] - q[1]:
        s = q[1] | {x}
        if len(s) == N:
            ans += 1
        else:
            queue.append((x, s))
print(ans)

Solution (Python):
import sys

import numpy as np
import math, string, itertools, fractions, heapq, collections, re, array, bisect, copy, functools, random
from collections import deque, defaultdict, Counter
from heapq import heappush, heappop
from itertools import permutations, combinations, product, accumulate, groupby
from bisect import bisect_left, bisect_right, insort_left, insort_right
from operator import itemgetter as ig
sys.setrecursionlimit(10 ** 7)
inf = 10 ** 20
INF = float("INF")
mod = 10 ** 9 + 7
"""dd = [(-1, 0), (0, 1), (1, 0), (0, -1)];
ddn = dd + [(-1, 1), (1, 1), (1, -1), (-1, -1)];
ddn9 = ddn + [(0, 0)]
for dx, dy in dd:
        nx = j + dx; ny = i + dy
            if 0 <= nx < w and 0 <= ny < h:"""

def wi(): return list(map(int, sys.stdin.readline().split()))
def wip(): return [int(x) - 1 for x in sys.stdin.readline().split()]  
def ws(): return sys.stdin.readline().split()
def si(): return int(sys.stdin.readline())  
def ss(): return input()
def hi(n): return [si() for _ in range(n)]
def hs(n): return [ss() for _ in range(n)]  
def s_list(): return list(input())
def mi(n): return [wi() for _ in range(n)]  
def mip(n): return [wip() for _ in range(n)]
def ms(n): return [ws() for _ in range(n)]
def num_grid(n): return [[int(i) for i in sys.stdin.readline().split()[0]] for _ in range(n)]  
def grid(n): return [s_list() for _ in range(n)]


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

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

    
    
    stack = [(1, [1])]
    ans = 0
    
    while stack:
        
        x, visited = stack.pop()

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

        
        for v in G[x]:
            if v in visited:
                continue
            stack.append((v, visited + [v]))

    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
N, M = map(int, input().split())
dict = {i+1:[] for i in range(N)}
for _ in range(M):
    a, b = map(int, input().split())
    dict[a].append(b)
    dict[b].append(a)
    
def DFS(visited, sight, cnt):
    if(len(visited) == N):
        return cnt+1
    for num in dict[sight]:
        if num in visited:
            continue
        cnt = DFS(visited+[num], num, cnt)
    return cnt

print(DFS([1], 1, 0))

Solution (Python):
import sys
from math import *
from collections import deque, Counter, defaultdict
from fractions import gcd
from itertools import permutations
input = lambda: sys.stdin.readline().rstrip()

def eprint(s):
    sys.stderr.write('DEBUG: {}'.format(s))
    return


def main():
    n,m = map(int, input().split())
    graph = [[0 for _ in range(n)] for _ in range(n)]
    for i in range(m):
        a,b = map(int, input().split())
        graph[a-1][b-1] = 1
        graph[b-1][a-1] = 1
    
    
   
    a = [i+1 for i in range(n)]
    p = permutations(a)

    def check(x):
        
        for i in range(n-1):
            if not graph[x[i]-1][x[i+1]-1]:
                return False
        return True
    cnt = 0
    for x in p:
        if x[0] != 1:
            continue
        if check(x):
            cnt += 1       
    print(cnt)
    return

if __name__ == '__main__':
    main()

Solution (Python):
from collections import deque, defaultdict

N, M = map(int, input().split())
nodes = defaultdict(set)
for _ in range(M):
    u, v = map(int, input().split())
    nodes[u].add(v)
    nodes[v].add(u)

visited = [False]*N

def dfs(x, visited, st):
    res = 0
    v = visited.copy()
    v[x-1] = True
    if st == N:
        return 1

    for node in nodes[x]:
        if not v[node-1]:
            res += dfs(node, v, st+1)
    return res

print(dfs(1, visited, 1))

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

def my_permutations(nums, t, path):
    if len(nums) == 0:
        path.append(t)
        return
    for i in range(len(nums)):
        my_permutations(nums[:i] + nums[i + 1:], t + [nums[i]], path)

def dfs(graph, permu, n):
    visited = [False] * (n + 1)
    next_nodes = set([1])
    for p in permu:
        if visited[p]:
            return False
        if p not in next_nodes:
            return False
        visited[p] = True
        next_nodes = set(graph[p])
    return True

path = []
my_permutations([i for i in range(1, n + 1)], [], path)
ans = 0
for permu in path:
    if permu[0] != 1:
        continue
    if dfs(graph, permu, n):
        ans += 1
print(ans)

Solution (Python):

import sys


N,M=[int(i) for i in input().rstrip().split()]
ab_list=[[int(j) for j in input().split()] for i in range(M)]


vertex_dic={}  

for va,vb in ab_list:
    vertex_dic.setdefault(va,set())
    vertex_dic[va].add(vb)
    vertex_dic.setdefault(vb,set())
    vertex_dic[vb].add(va)


def check(vertex_dic :dict, passed :set, start :int):
    if len(vertex_dic) == len(passed):
        return 1
    
    next_set = vertex_dic[start] - passed 
    
    ans=0
    for i_next in next_set:
        next_passed = passed | {i_next}
        ans += check(vertex_dic, next_passed, i_next)
    
    return ans
    

result=check(vertex_dic, {1}, 1 )
print(result)

Solution (Python):

import sys


N,M=[int(i) for i in input().rstrip().split()]
ab_list=[[int(j) for j in input().split()] for i in range(M)]


vertex_dic={}  

for va,vb in ab_list:
    vertex_dic.setdefault(va,set())
    vertex_dic[va].add(vb)
    vertex_dic.setdefault(vb,set())
    vertex_dic[vb].add(va)


def check(vertex_dic :dict, passed :set, start :int, cnt :int):
    if cnt >= len(vertex_dic) and len(vertex_dic) == len(passed):
        return 1
    
    next_set = vertex_dic[start] - passed 
    cnt += 1
    
    ans=0
    for i_next in next_set:
        next_passed = passed | {i_next}
        ans += check(vertex_dic, next_passed, i_next, cnt)
    
    return ans
    
result=check(vertex_dic, {1}, 1 ,1 )
print(result)

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

Solution (Python):
import sys
sys.setrecursionlimit(10**6)
from math import floor,ceil,sqrt,factorial,log
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from operator import itemgetter
from fractions import gcd
mod = 10 ** 9 + 7
inf = float('inf')
ninf = -float('inf')
 

def ii(): return int(sys.stdin.readline().rstrip()) 
def mii(): return map(int,sys.stdin.readline().rstrip().split())
def limii(): return list(mii()) 
def lin(n:int): return [ii() for _ in range(n)]
def llint(n: int): return [limii() for _ in range(n)]

def ss(): return sys.stdin.readline().rstrip() 
def mss(): return sys.stdin.readline().rstrip().split()
def limss(): return list(mss()) 
def lst(n:int): return [ss() for _ in range(n)]
def llstr(n: int): return [limss() for _ in range(n)]





n,m=mii()
gra=[[] for _ in range(n)]
for i in range(m):
    a,b=mii()
    a-=1
    b-=1
    gra[a].append(b)
    gra[b].append(a)

ans=0
for i in permutations(range(1,n)):
    i=[0]+list(i)
    cnt=1
    for j in range(n-1):
        
        if i[j+1] in gra[i[j]]:
            cnt+=1

    if cnt==n:
        ans+=1

print(ans)

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

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

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

count = 0
for route in all_routes:
  cur_path = path.copy()
  current = 1
  valid = True
  for next_pos in route:
    if ([current, next_pos] in cur_path):
      cur_path.remove([current, next_pos])
      current = next_pos
      continue
    elif ([next_pos, current] in cur_path):
      cur_path.remove([next_pos, current])
      current = next_pos
      continue
    else:
      valid = False
      break
  
  if(valid == True):
    count += 1

print(count)

Solution (Python):

from itertools import permutations
n,m=map(int,input().split())
edges=[[False for _ in range(n)] for _ in range(n)]
for _ in range(m):
    a,b=map(int,input().split())
    a,b=a-1,b-1
    edges[a][b]=edges[b][a]=True

ans=0
for l in permutations(range(1,n),n-1):
    l=[0]+list(l)
    if all(edges[l[i]][l[i+1]] for i in range(n-1)):
        ans+=1
print(ans)

Solution (Python):
import sys 
sys.setrecursionlimit(1000000)
N, M = map(int, input().split())
ab = [list(map(lambda x:int(x)-1, input().split())) for _ in range(M)]
adlist = [[] for _ in range(N)]
for a, b in ab:
  adlist[a] += [b] 
  adlist[b] += [a] 


used = [0]*N 
global ans 
ans = 0
def dfs(v):
  global ans 
  used[v] = 1 
  if sum(used) == N:
    ans += 1 
    return 

  for u in adlist[v]:
    if used[u] == 0:
      used[u] = 1 
      dfs(u)
      used[u] = 0  

  return 

dfs(0)
print(ans)

Solution (Python):
res = 0
def main():
    import sys
    
    sys.setrecursionlimit(10000000)
    from collections import Counter, deque
    
    from itertools import combinations
    
    from math import floor, ceil

    


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

    visited = [0]*N

    def dfs(node):
        global res
        visited[node]=1
        if all(visited):
            res += 1
            return
        for n_node in g[node]:
                if not visited[n_node]:
                    dfs(n_node)
                    visited[n_node] = 0
    dfs(0)
    print(res)

if __name__ == '__main__':
    main()

Solution (Python):
'''
頂点1から全頂点通る一筆書きが何個あるか
頂点数(N)は最大で8なので道順を全列挙して調べてもいける
'''
def main():
    import sys
    
    sys.setrecursionlimit(10000000)
    from collections import Counter, deque
    
    from itertools import combinations
    
    from math import floor, ceil

    


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

    res = []
    visited = [0]*N

    def dfs(node):
        visited[node]=1
        if sum(visited)==N:
            res.append(1)
            return
        for n_node in g[node]:
                if not visited[n_node]:
                    dfs(n_node)
                    visited[n_node] = 0
    dfs(0)
    print(len(res))


    
    
    
    
    

    
    
    
    
    
    
    
    
    
    
    
    
    
    

    
    
    
    
    
    
    
    
    

if __name__ == '__main__':
    main()

Solution (Python):
def main():
    import sys
    
    sys.setrecursionlimit(10000000)
    from collections import Counter, deque
    
    from itertools import combinations
    
    from math import floor, ceil

    

    n,m = map(int, input().split())
    edge = [list(map(int, input().split())) for _ in range(m)]
    res = []
    visited = [0]*n

    def dfs(node):
        visited[node-1]=1
        if sum(visited)==n:
            res.append(1)
            return
        for x,y in edge:
            if x == node:
                if not visited[y-1]:
                    dfs(y)
                    visited[y-1] = 0
            if y == node:
                if not visited[x-1]:
                    dfs(x)
                    visited[x-1] = 0

    for a,b in edge:
        if a==1:
            dfs(a)
            print(len(res))
            exit()

if __name__ == '__main__':
    main()

Solution (Python):

from itertools import permutations
import sys
try:
    from typing import List
except ImportError:
    pass


def solve(N: int, M: int, a: "List[int]", b: "List[int]"):
    e = set(zip(a, b))
    print(sum(
        1 for p in permutations(range(2, N + 1))
        if all((n1, n2) in e or (n2, n1) in e for n1, n2 in zip((1,) + p, p))
    ))


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  
    M = int(next(tokens))  
    a = [int()] * (M)  
    b = [int()] * (M)  
    for i in range(M):
        a[i] = int(next(tokens))
        b[i] = int(next(tokens))
    solve(N, M, a, b)


if __name__ == '__main__':
    main()

Solution (Python):
from collections import deque
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 in l:
    graph[i[0]][i[1]] = True
    graph[i[1]][i[0]] = True

cnt = 0

for i in permutations(range(1,N+1)):
    if i[0] != 1:
        continue
    isJoin = True
    for j in range(1,N):
        if not graph[i[j-1]][i[j]]:
            isJoin = False
            break
    if isJoin:
        cnt += 1
print(cnt)

Solution (Python):
from collections import deque
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 in l:
    graph[i[0]][i[1]] = True
    graph[i[1]][i[0]] = True

cnt = 0

for i in permutations(range(1,N+1)):
    if i[0] != 1:
        continue
    isJoin = True
    for j in range(1,N):
        if not graph[i[j-1]][i[j]]:
            isJoin = False
            break
    if isJoin:
        cnt += 1
print(cnt)

Solution (Python):
N, M = map(int, input().split())
graph ={i+1:[] for i in range(N)}
for _ in range(M):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)
    
def dfs(path, n, cnt):
    if(len(path) == N):
        return cnt+1
    for j in graph[n]:
        if(j in path):
            continue
        cnt = dfs(path+[j], j, cnt)
    return cnt
print(dfs([1], 1, 0))

Solution (Python):

import sys
import math
from bisect import bisect_left
from bisect import bisect_right
import collections
import copy
import heapq
from collections import defaultdict
from heapq import heappop, heappush
import itertools
input = sys.stdin.readline

























def inputInt(): return int(input())
def inputMap(): return map(int, input().split())
def inputList(): return list(map(int, input().split()))

inf = float('inf')
mod = 1000000007




def main():
	N,M = inputMap()
	ck = {}
	for i in range(M):
		a,b = inputMap()
		if a in ck:
			ck[a].append(b)
		else:
			ck[a] = [b]
		if b in ck:
			ck[b].append(a)
		else:
			ck[b] = [a]

	tmp = [i for i in range(2,N+1)]
	ans = 0
	for v in itertools.permutations(tmp, N-1):
		ato = list(v)
		saki = [1]
		saki += ato
		flg = True
		for i,val in enumerate(saki):
			if i == 0:
				continue
			if val in ck[saki[i-1]]:
				pass
			else:
				flg = False
				break
		if flg == True:
			ans += 1

	print(ans)








def combination(n, r, mod=10**9+7):
    r = min(r, n-r)
    res = 1
    for i in range(r):
        res = res * (n - i) * modinv(i+1, mod) % mod
    return res


def modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod)

def egcd(a, b):
    if a == 0:
        return b, 0, 1
    else:
        g, y, x = egcd(b % a, a)
        return g, x - (b // a) * y, y



def H(n, r, mod=10**9+7):
	
	
    return combination(n+r-1, r, mod)

class Combination:
    """
    O(n)の前計算を1回行うことで，O(1)でnCr mod mを求められる
    n_max = 10**6のとき前処理は約950ms (PyPyなら約340ms, 10**7で約1800ms)
    使用例：
    comb = Combination(1000000)
    print(comb(5, 3))  
    """
    def __init__(self, n_max, mod=10**9+7):
        self.mod = mod
        self.modinv = self.make_modinv_list(n_max)
        self.fac, self.facinv = self.make_factorial_list(n_max)

    def __call__(self, n, r):
        return self.fac[n] * self.facinv[r] % self.mod * self.facinv[n-r] % self.mod

    def make_factorial_list(self, n):
        
        
        fac = [1]
        facinv = [1]
        for i in range(1, n+1):
            fac.append(fac[i-1] * i % self.mod)
            facinv.append(facinv[i-1] * self.modinv[i] % self.mod)
        return fac, facinv

    def make_modinv_list(self, n):
        
        modinv = [0] * (n+1)
        modinv[1] = 1
        for i in range(2, n+1):
            modinv[i] = self.mod - self.mod//i * modinv[self.mod%i] % self.mod
        return modinv

if __name__ == "__main__":
	main()

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

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


def solve(n, visit):
    if all(visit):
        return 1
    c = 0
    for i in range(N):
        b = ab[n][i]
        if b and not visit[i]:
            visit[i] = True
            c += solve(i, visit)
            visit[i] = False
    return c


print(solve(0, [True]+[False]*(N-1)))

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


def dfs(root):
    now = root[-1]
    ret = []
    for i in graph[now]:
        if i in root:
            pass
        else:
            ret.append(dfs(root + [i]))
    if not ret:
        if len(root) == n:
            return 1
        return 0

    return sum(ret)


print(dfs([1]))

Solution (Python):
from itertools import permutations

N, M = list(map(int, input().split()))
G = [[0 for _ in range(N + 1)] for _ in range(N + 1)]
for _ in range(M):
    ai, bi = list(map(int, input().split()))
    G[ai][bi] = 1
    G[bi][ai] = 1

count = 0
for idx, perm in enumerate(permutations(range(1, N+1))):
    if perm[0] != 1:
        continue

    flag = True
    for i in range(len(perm) - 1):
        if G[perm[i]][perm[i + 1]] == 0:
            flag = False
            break
    if flag:
        count += 1

print(count)

Solution (Python):
import itertools

n, m = map(int, input().split())
am = [[False]*n for _ in range(n)]

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

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

    isok = True
    for i in range(len(p)-1):
        if not am[p[i]][p[i+1]]:
            isok = False
            break

    if isok:
        ans += 1

print(ans)

Solution (Python):
from itertools import permutations

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

    g[a][b] = 1
    g[b][a] = 1

check = set()

path = list(permutations(range(N)))

for t in path:
    if t[0] != 0:
        continue
    flag = True
    for i in range(N - 1):
        if g[t[i]][t[i + 1]] != 1:
            flag = False
            break
    if flag:
        check.add(t)


print(len(check))

Solution (Python):
from collections import defaultdict
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def MI1(): return map(int1, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

def main():
    def dfs(u=0,cnt=1):
        if cnt==n:return 1
        res=0
        for cu in to[u]:
            if vis[cu]:continue
            vis[cu]=True
            res+=dfs(cu,cnt+1)
            vis[cu]=False
        return res

    n,m=MI()
    to=defaultdict(list)
    for _ in range(m):
        a,b=MI1()
        to[a].append(b)
        to[b].append(a)
    vis=[False]*n
    vis[0]=True
    print(dfs())

main()

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

data = [i for i in range(2, n+1)]

ans = 0
for a in itertools.permutations(data, n-1):
    a = [1] + list(a)
    flag = True
    for i in range(1, len(a)):
        if not ([a[i-1], a[i]] in ab or [a[i], a[i-1]] in ab):
            flag = False
            break
    if flag:
        ans += 1
print(ans)

Solution (Python):
N,M = map(int, input().split())
path = [[] for i in range(N)] 
for i in range(M):
    nums = list(map(int, input().split()))
    path[nums[0]-1].append(nums[1]-1)
    path[nums[1]-1].append(nums[0]-1)

memo = [] 
def search(idx, memo_str):
    if len(memo_str) == N and memo_str not in memo:
        memo.append(memo_str)
        return
    
    if str(idx) in memo_str:
        return
    
    tmp_memo = memo_str + str(idx)
    
    for num in path[idx]:
        search(num, tmp_memo)

search(0, '')

print(len(memo))

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


def dfs(v):
    visited[v] = True
    if all(visited):
        visited[v] = False
        return 1
    ret = 0
    for u in range(N):
        if v == u or visited[u] or G[v][u] == 0:
            continue
        ret += dfs(u)
    visited[v] = False
    return ret


print(dfs(0))

Solution (Python):
import itertools
N, M = map(int, input().split())
G = [[False]*10 for _ in range(10)]
for i in range(M):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    G[a][b] = G[b][a] = True

res = 0
L = list(itertools.permutations(range(N)))

for l in L:
    if l[0] != 0:
        break
    ok = True
    for i in range(N-1):
        from_ = l[i]
        to_ = l[i+1]
        if not G[from_][to_]:
            ok = False
    if ok:
        res += 1
print(res)

Solution (Python):

N, M = map(int,input().split())
graph = [[] for j 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)
judge = [False]*N
judge[0] = True

def dfs(v,judge):
  if all(judge):
    return 1
  res = 0
  for nv in graph[v]:
    if judge[nv]:
      continue 
    judge[nv] = True
    res += dfs(nv,judge)
    judge[nv] = False
  return res
print(dfs(0,judge))

Solution (Python):











import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,sqrt,factorial,hypot,log 
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from fractions import gcd
from random import randint
def ceil(a,b): return (a+b-1)//b
inf=float('inf')
mod = 10**9+7
def pprint(*A): 
    for a in A:     print(*a,sep='\n')
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def lcm(a,b):
    return a*b//gcd(a,b)
def main():
    N,M=MI()
    edge = [[0]*N for _ in range(N)]
    for _ in range(M):
        a,b = MI_()
        edge[a][b] = 1
        edge[b][a] = 1
    
    ans = 0
    for it in permutations([i for i in range(N)]):
        l  =  [i for i in it]
        ok = True
        if l[0]!=0:
            continue
        for i in range(N-1):
            if not edge[l[i]][l[i+1]]:
                ok = False
        ans += ok
    print(ans)
    
if __name__ == '__main__':
    main()

Solution (Python):
from itertools import permutations

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

ans = 0
for path in permutations(range(n)):
        if path[0]: continue
        can = 1
        for i in range(n-1):
                if links[path[i]][path[i+1]]==0: can = 0
        ans += can
print(ans)

Solution (Python):
def main():
    N, M = (int(i) for i in input().split())
    G = [[] for i in range(N)]
    for i in range(M):
        x, y = (int(i)-1 for i in input().split())
        G[x].append(y)
        G[y].append(x)
    ans = 0
    from itertools import permutations
    for p in permutations(range(1, N)):
        j = 0
        
        for i in range(N-1):
            if p[i] in G[j]:
                j = p[i]
            else:
                break
        else:
            ans += 1
    print(ans)


if __name__ == '__main__':
    main()