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):
l = input().split()
N = int(l[0])
M = int(l[1])

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

for i in range(M):
    l = input().split()
    a = int(l[0]) - 1
    b = int(l[1]) - 1
    C[a].append(b)
    C[b].append(a)



def visit(cur, visited, ans, depth):
    depth += 1
    
    
    visited.append(cur)
    if len(visited) == N:
        
        return ans + 1
    for n in C[cur]:
        
        if n not in visited:
            v = [x for x in visited]
            ans = visit(n, v, ans, depth)
    return ans

ans = 0
for n in C[0]:
    visited = [0]
    ans += visit(n, visited, 0, 0)

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):
    line = map(int, input().split())
    paths = [x - 1 for x in line]
    path_matrix[paths[0]][paths[1]] = True
    path_matrix[paths[1]][paths[0]] = True


visited = [False] * N


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

    return total_paths

print(dfs(0, 0))

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


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

checked = [False for _ in range(n)]


def solve(i, c):
  c[i] = True

  global ans
  if c.count(False) == 0:
    ans += 1
    return
  else:
    for j in paths[i]:
      if c[j] == False: 
        solve(j, copy.deepcopy(c))
        
      

        
solve(0, copy.deepcopy(checked))
print(ans)

Solution (Python):
import itertools

N,M=map(int,input().split())
route=[list(map(int,input().split())) for _ in range(M)]
candidate=list(itertools.permutations(range(1,N+1)))

ans=0
for c in candidate:
  if c[0]==1:
    for i in range(N-1):
      l=sorted([c[i], c[i+1]])
      if l not in route:
         break
    else:
      ans+=1
print(ans)

Solution (Python):



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


def dfs(p, visited):
  if len(visited) == N:
    return 1
  else:
    ret = 0
    for q in graph[p]:
      if q not in visited:
        ret += dfs(q, visited+[q])
    return ret

print(dfs(0,[0]))

Solution (Python):



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

ans = 0

def dfs(p, visited):
  global ans
  if len(visited) == N:
    ans += 1
  else:
    for q in graph[p]:
      if q not in visited:
        dfs(q, visited+[q])

dfs(0,[0])
print(ans)

Solution (Python):

import sys


def solve(N: int, M: int, a: "List[int]", b: "List[int]"):
    vertex = [[0] * N for i in range(N)]

    for i in range(M):
        vertex[a[i]-1][b[i]-1] += 1
        vertex[b[i]-1][a[i]-1] += 1

    import itertools
    ans = 0
    for x in itertools.permutations(range(N)):
        if(x[0] != 0):
            break
        plus = 1
        for i in range(N-1):
            plus = plus * vertex[x[i]][x[i+1]]

        ans += plus
             
    print(ans)
    return
    return



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):
N, M = map(int, input().split())
grp = []
for i in range(0, N):
	lst = []
	for j in range(0, N):
		lst.append(False)
	grp.append(lst)
for i in range(0, M):
	a, b = map(int, input().split())
	grp[a-1][b-1] = True
	grp[b-1][a-1] = True
memo = [False]
goal = [False]
for i in range(1, N):
	memo.append(True)
	goal.append(False)
queue = [[0, memo]]
cnt = 0
while queue != []:
	now = queue.pop(0)
	if now[1] == goal: cnt += 1
	else:
		for i in range(0, N):
			if grp[now[0]][i] and now[1][i]:
				newmemo = []
				for j in range(0, N):
					if i == j: newmemo.append(False)
					else: newmemo.append(now[1][j])
				queue.append([i, newmemo])
print(cnt)

Solution (Python):
def dp(d,i):
    if sum(d)==n-1:return 1
    x=0
    for j in l[i]:
        if d[j-2]==1:continue
        di=d[:]
        di[j-2]=1
        x+=dp(di,j)
    return x
        
n,m=map(int,input().split())
l=[[] for _ in range(n+1)]
for i in range(m):
    a,b=map(int,input().split())
    if b!=1:l[a].append(b)
    if a!=1:l[b].append(a)
print(dp([0]*(n-1),1))

Solution (Python):

import copy

def solve():
    N, M = list(map(int, input().split()))
    A, B = [], []
    edge = {}  

    """方針
    Nは高々8なので全探索してみる
    """
    for i in range(M):
        a, b = list(map(int, input().split()))
        
        if not a-1 in edge:
            edge[a-1] = []
        edge[a-1].append(b-1)
        if not b-1 in edge:
            edge[b-1] = []
        edge[b-1].append(a-1)

    rest_list = [i for i in range(N)]  
    rest_list.remove(0)  
    now_v = 0  

    def dfs(now_v, rest_list):
        if len(rest_list) == 0:
            
            return 1
        ans = 0  
        for u in rest_list:
            if not u in edge[now_v]: continue  
            tmp_rest_list = copy.deepcopy(rest_list)
            tmp_rest_list.remove(u)
            ans += dfs(u, tmp_rest_list)
        return ans

    ans = dfs(0, rest_list)
    print(ans)


if __name__ == "__main__":
    solve()

Solution (Python):
from collections import defaultdict
import itertools

n, m = map(int, input().split())
connected_dict = defaultdict(lambda: [])

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

count = 0
for permutation in list(itertools.permutations(range(2, n + 1))):
    flag = True
    pre_num = 1
    for num in permutation:
        if num not in connected_dict[pre_num]:
            flag = False
            break
        pre_num = num
    if flag:
        count += 1
print(count)

Solution (Python):

import sys
import collections
import itertools


def solve(N: int, M: int, a: "List[int]", b: "List[int]"):
    graph = collections.defaultdict(list)
    for aa,bb in zip(a,b):
        graph[aa].append(bb)
        graph[bb].append(aa)

    res = 0
    for seq in itertools.permutations(range(1,N+1)):
        if seq[0] != 1:
            continue
        bOK = True
        for i in range(len(seq)-1):
            if seq[i+1] not in graph[seq[i]]:
                bOK = False
                break
        if bOK:
            res += 1

    print(res)






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):
N, M = map(int, input().split())
edges = [list(map(int, input().split())) for _ in range(M)]

graph = [[None] * N for _ in range(N)]
for x, y in edges:
    graph[x - 1][y - 1] = True
    graph[y - 1][x - 1] = True
    
def dfs(v):    
    if all(visited):
        return 1
    
    ret = 0
    for i in range(N):
        if not graph[v][i]:
            continue
        if visited[i]:
            continue
            
        visited[i] = True
        ret += dfs(i)
        visited[i] = False
        
    return ret

visited = [True] + [False] * (N - 1)
print(dfs(0))

Solution (Python):

import numpy as np

n,m = map(int, input().split())
graph = [[0 for i in range(n)] for j in range(n)]
graph = np.array(graph)

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

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

def DFS(v,used):
    if all(used):
        return 1
    ans = 0
    for i in range(n):
        if used[i]:
            continue
        if graph[i,v] == 0:
            continue
        used[i] = True
        ans += DFS(i,used)
        used[i] = False
    return ans
  
print(DFS(0,used))

Solution (Python):

import numpy as np

n,m = map(int, input().split())
graph = [[0 for i in range(n)] for j in range(n)]
graph = np.array(graph)

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

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

def DFS(v,used):
    global ans
    if all(used):
        ans += 1
        return 
    for i in range(n):
        if used[i]:
            continue
        if graph[i,v] == 0:
            continue
        used[i] = True
        DFS(i,used)
        used[i] = False
    return

ans = 0
DFS(0,used)

print(ans)

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

for i in range(m):
    a, b = map(lambda x: int(x)-1, input().split())
    p[a].append(b)
    p[b].append(a)
ans = 0


def s(d, l):
    global ans
    
    if d == n:
        ans += 1
        return
    for i in p[l[-1]]:
        if i in l:
            continue
        s(d+1, l+[i])
    return


s(1, [0])
print(ans)

Solution (Python):

import copy
import random
import bisect 
import fractions 
import math
import sys

mod = 10**9+7
sys.setrecursionlimit(mod) 

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


def dfs(node,p,passed):
    
    if len(passed) == N:
        return 1
    cnt = 0
    for new_node in tree[node]:
        if new_node == p:
            continue
        if not new_node in passed:
            passed2 = copy.deepcopy(passed)
            passed2 += [new_node]
            cnt += dfs(new_node,node,passed2)
    return cnt

ans = dfs(0,-1,[0])
print(ans)

Solution (Python):
import itertools

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

count = 0
for p in itertools.permutations(range(1, N+1)):
    if p[0] != 1:
        continue

    flag = True
    for i in range(N - 1):
        if not {p[i], p[i+1]} in Lines:
            flag = False
            break

    if flag:
        count += 1

print(count)

Solution (Python):

"""
C - One-stroke Path
https://atcoder.jp/contests/abc054/tasks/abc054_c

"""
import sys


from itertools import permutations

def solve(N, M, path):
    ans = 0
    for p in permutations(range(2, N+1)):
        p = [1] + list(p)
        for f, t in zip(p, p[1:]):
            if not [f, t] in path and not [t, f] in path:
                break
        else:
            ans += 1
    return ans


def main(args):
    N, M = map(int, input().split())
    path = [[int(i) for i in input().split()] for _ in range(M)]
    ans = solve(N, M, path)
    print(ans)


if __name__ == '__main__':
    main(sys.argv[1:])

Solution (Python):
import itertools
n,m=map(int,input().split())
A=[]
for i in range(m):
  a,b=map(int,input().split())
  A.append([a,b])
N=[int(i+2) for i in range(n-1)]
def f(list,n):
  path=0
  if [1,list[0]] in A:
    path+=1
  for i in range(1,n-1):
    if [list[i],list[i-1]] in A or [list[i-1],list[i]] in A:
      path+=1
  if path==n-1:
    return 1
  else:
    return 0  
ans=0
for p in itertools.permutations(N,n-1):
  ans+=f(list(p),n)
print(ans)

Solution (Python):
import copy
n, m = map(int,input().split())
graph = []
num = 1
for i in range(m):
    graph.append(list(map(int, input().split())))
pathes = [[[1],graph]]
count = 0
while pathes:
    path_lines = pathes.pop()
    path, lines = path_lines
    if len(path) == n:
        count += 1
    else:
        for line in lines:
            if path[-1] in line:
                new_path = copy.copy(path)
                new_lines = copy.copy(lines)
                new_lines.remove(line)
                new_line = copy.copy(line)
                new_line.remove(new_path[-1])
                
                if new_line[0] in new_path:
                    continue
                new_path.append(new_line[0])
                pathes.append([new_path, new_lines])
print(count)

Solution (Python):
N,M = [int(i) for i in input().split()]
p = {}

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

cnt = 0

def func(q,l,n):
    if n == N:
        global cnt
        cnt += 1
    for i in p[q]:
        if i not in l:
            func(i, l+[i], n+1)

func(1, [1], 1)
print(cnt)

Solution (Python):
N, M = map(int, input().split())
p = {} 
for _ in range(M):
    a, b = map(int, input().split())
    if a in p:
        p[a].append(b)
    else:
        p[a] = [b]
    if b in p:
        p[b].append(a)
    else:
        p[b] = [a]
cnt = 0 
def func(q, l, n): 
    if n == N:
        global cnt
        cnt += 1
    for i in p[q]:
        if i not in l: 
            func(i, l+[i], n+1)
func(1, [1], 1)
print(cnt)

Solution (Python):
N, M = map(int, input().split())
p = {}
for _ in range(M):
    a, b = map(int, input().split())
    if a in p:
        p[a].append(b)
    else:
        p[a] = [b]
    if b in p:
        p[b].append(a)
    else:
        p[b] = [a]
cnt = 0
def func(q, l, n):
    if n == N:
        global cnt
        cnt += 1
    for i in p[q]:
        if i not in l:
            func(i, l+[i], n+1)
func(1, [1], 1)
print(cnt)

Solution (Python):
from itertools import permutations
from heapq import *
from collections import defaultdict
from math import log
from itertools import accumulate
from collections import deque

import sys
sys.setrecursionlimit(100100)

import math
from math import ceil
from copy import deepcopy


N,M=map(int,input().split())
T=[[] for i in range(N)]
for i in range(M):
    u,v=map(int,input().split())
    u,v=u-1,v-1
    T[u].append(v)
    T[v].append(u)
list=list(range(1,N))
ans=0
for l in permutations(list):
    t=True
    for i in range(N-1):
        if i==0:
            if not l[0] in T[0]:
                t=False
                break
        else:
            if not l[i] in T[l[i-1]]:
                t=False
                break
    if t:
        ans+=1
print(ans)

Solution (Python):
import itertools
N,M=map(int,input().split())
ab=list(list(map(int,input().split())) for _ in range(M))
l=list(l for l in range(1,N+1))
numlist=list(itertools.permutations(l))
ans=0
for I in numlist:
    if I[0]==1 and all(sorted([I[j],I[j+1]]) in ab for j in range(N-1)):
        ans+=1
print(ans)

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

def search(x):
    a = 0
    E[x] = 1
    if 0 not in E:
        a += 1
    for g in G[x]:
        if E[g] == 0:
            a += search(g)
    E[x] = 0
    return a

print(search(0))

Solution (Python):
N, M = list(map(int, input().split()))
data = [[] for _ in range(N+1)]

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

def dfs(x, been):
    ans = 0
    if len(been) == N:
        return 1
    else:
        for i in data[x]:
            if been.count(str(i)) == 0:
                been += str(i)
                ans += dfs(i, been)
                been = been[:-1]

    return ans

been = '1'
print(dfs(1, been))

Solution (Python):
n,m = map(int,input().split())
path = [input().split() for x in range(m)]

table = [[] for x in range(n)]
for x in path:
    table[int(x[0])-1].append(int(x[1])-1)
    table[int(x[1])-1].append(int(x[0])-1)
    
import itertools
count = 0
for z in itertools.permutations(range(0,n)):
    if z[0] == 0:
        for y in range(len(z)-1):
            if z[y+1] in table[z[y]]:
                continue
            else:
                count -= 1
                break
        count += 1
print(count)

Solution (Python):
from itertools import permutations

n,m=map(int,input().split())
path=set()
for _ in range(m):
    u,v=map(int,input().split())
    path|={(u-1,v-1),(v-1,u-1)}
s = 0
for i in permutations(range(n)):
    if i[0] ==0:

        s+=(all((h,j) in path for h,j in zip(i[1:],i)))


print(s)

Solution (Python):


from itertools import permutations

n,m=map(int,input().split())
path=set()
for _ in range(m):
    u,v=map(int,input().split())
    path|={(u-1,v-1),(v-1,u-1)}

print(sum(all((u,v) in path for u,v in zip(p,p[1:]))
          for p in permutations(range(n)) if p[0]==0))

Solution (Python):
def dfs(graph, start):
    ans = 0
    stack = [[start, 2**start]]
    visited = {}
    while stack:
        d = stack.pop()
        if d[1] == 2 ** N - 1:
            ans += 1
            continue
        for node in graph[d[0]]:
            if not (d[1] & 2 ** node):
                stack.append([node, d[1] | 2 ** node])
    return ans


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

Solution (Python):
N, M = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(M)]
X = [[0] * N for _ in range(N)]
for i in range(M):
  X[ab[i][0]-1][ab[i][1]-1] = 1
  X[ab[i][1]-1][ab[i][0]-1] = 1

def dfs(u):
  c = 0
  if len(u) == N:
    return 1
  for i in range(len(X[u[-1]])):
    if X[u[-1]][i] == 1 and i not in u:
      c += dfs(u + [i])
  return c

print(dfs([0]))

Solution (Python):
import numpy as np
N, M = map(int, input().split())
 
Adj_matrix = np.zeros((N, N))
for _ in range(M):
    a, b = map(int, input().split())
    Adj_matrix[a - 1, b - 1] += 1
    Adj_matrix[b - 1, a - 1] += 1
    
def initialize():
    explored_list = np.zeros((N, 1))
    return explored_list
  
def is_move(vertex, explored_list, Adj_martrix):
    for i in range(len(explored_list)):
        if explored_list[i] == 0 and Adj_martrix[vertex - 1, i] == 1:
            return True
    return False
  
import copy
 
g_count = 0
 
def graph_exp(vertex, explored_list, Adj_matrix):
    global g_count
    
    explored_list[vertex - 1] += 1
    
    
    if not is_move(vertex, explored_list, Adj_matrix):
        g_count += all(explored_list)
        return 0
    
    
    for i in range(len(explored_list)):
        if explored_list[i] == 0 and Adj_matrix[vertex - 1, i] == 1:
            graph_exp(i + 1, copy.copy(explored_list), Adj_matrix)
    
explored_list = initialize()
 
graph_exp(1, explored_list, Adj_matrix)
 
print(g_count)

Solution (Python):
import sys
sys.setrecursionlimit(10**9)

def dfs(s,check):
  if len(check)==n:
    if len(set(check))==n:
      return 1
    else:
      return 0
  ans=0
  for i in edge[s]:
    ans+=dfs(i,check+[i])
  return ans

n,m=map(int,input().split())
edge=[[] for _ in range(n+1)]
for i in range(m):
  s,t=map(int,input().split())
  edge[s].append(t)
  edge[t].append(s)
print(dfs(1,[1]))

Solution (Python):
import itertools
N,M = map(int,input().split())
ab = [list(map(int,input().split())) for _ in [0]*M]
connect = [[] for _ in [0]*N]
for a,b in ab:
    connect[a-1].append(b-1)
    connect[b-1].append(a-1)
ans = 0
for a in itertools.permutations(range(1,N)):
    a = (0,) + a
    for i in range(N-1):
        if not a[i+1] in connect[a[i]]:
            break
    else:
        ans+=1
print(ans)

Solution (Python):
ans = 0
def dfs(v, visiteNode, graph):
  visiteNode[v] = 1
  if all(visiteNode):
    global ans
    ans += 1
    return
  for node in graph[v]:
    if visiteNode[node]:
      continue
    else:
      dfs(node, visiteNode[:], graph)

N,M = map(int, input().split())
v = 0
visiteNode = [0] * N

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

Solution (Python):
from itertools import permutations
n, m = map(int,input().split())
dist =[[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
    dist[a][b] = 1
    dist[b][a] = 1
ans = 0
for p in permutations([i for i in range(1,n)]):
    t = True
    for i in range(n-2):
        if i == 0:
            if dist[0][p[0]] == 0:
                t = False
                break
        if dist[p[i]][p[i+1]] == 0:
            t = False
            break
    if t:
        ans += 1
        

print(ans)

Solution (Python):
import itertools
n, m = map(int,input().split())
D = {tuple(sorted(map(int,input().split()))) for i in range(m)}

cnt = 0
for i in itertools.permutations(range(2,n+1),n-1):
  li = [1] + list(i)
  
  cnt += sum(1 for j in zip(li,li[1:]) if tuple(sorted(j)) in D) == n-1
print(cnt)

Solution (Python):
import itertools


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

graph = [[] for _ in range(N)]
for p in path:
    graph[p[0]-1].append(p[1]-1)
    graph[p[1]-1].append(p[0]-1)


arr = [i for i in range(1,N)]
perms = [v for v in  itertools.permutations(arr, len(arr))]


solved = 0
for perm in perms:
    now = 0
    res = True

    for v in perm:
        if v in graph[now]:
            now = v
        else:
            res = False
            break
    if res:
        solved += 1

print(solved)

Solution (Python):
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

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

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

print(dfs(0, used))

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

visited = [False] * (N + 1)

def dfs(src, count):
    if count == N:
        return 1

    visited[src] = True
    result = 0
    for dst in E[src]:
        if not visited[dst]:
            result += dfs(dst, count + 1)
    visited[src] = False

    return result

print(dfs(1, 1))

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

visited = [False] * (N + 1)
visited[1] = True

def dfs(src, count):
    if count == N:
        return 1
    result = 0
    for dst in E[src]:
        if not visited[dst]:
            visited[dst] = True
            result += dfs(dst, count + 1)
            visited[dst] = False

    return result

print(dfs(1, 1))

Solution (Python):
ans = 0

def dfs(v, visited, d):
    visited[v] = 1
    if all(visited):
        global ans
        ans += 1
        return
    for node in d[v]:
        if visited[node]:
            continue
        else:
            dfs(node, visited[:], d)

n, m = map(int, input().split())
d = [[] for _ in range(n)]
for _ in range(m):
    a, b = map(int, input().split())
    a = a - 1
    b = b - 1
    d[a].append(b)
    d[b].append(a)
v = 0
visited = [0] * n
dfs(v, visited, d)
print(ans)

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

c = 0
rel = {}

for n in range(1, N + 1):
	rel[n] = []

for a, b in AB:
	rel[a] += [b]
	rel[b] += [a]

def trase(r):
	global c
	
	if N == len(r):
		c += 1
		return
	for n in rel[r[-1]]:
		if n in r:
			continue
		trase(r + [n])

for n in rel[1]:
	trase([1] + [n])

print(c)

Solution (Python):
import itertools

n, m = [int(x) for x in input().split()]
edges = set(tuple(int(x) for x in input().split()) for _ in range(m))
print(sum(1 if all(p in edges or tuple(reversed(p)) in edges for p in [(1, path[0])] + list(zip(path, path[1:]))) else 0 for path in itertools.permutations(range(2, n + 1))))

Solution (Python):
N,M = map(int,input().split())
branch_list = []
for i in range(M):
    branch_list.append(list(map(int,input().split())))

visited = [1]

def dfs(now):
    global cnt
    if len(visited) == N:
        cnt += 1
        return cnt
    for br in branch_list:
        if now in br:
            next_node = br[1-br.index(now)]
            if not next_node in visited:
                visited.append(next_node)
                dfs(next_node)
                visited.remove(next_node)
    return cnt
cnt = 0
dfs(1)
print(cnt)

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

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

cnt = 0
def func(position, hist):
    global cnt
    hist = hist[:]
    if len(hist) == N:
        cnt += 1
    for ab in ab_list:
        if position in ab:
            next_position = [x for x in ab if x != position][0]
            if next_position not in hist:
                func(next_position, hist+[position])

func(1,[0])
print(cnt)

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


g = [["
for p in ab:
    g[p[0]-1][p[1]-1] = "-"
    g[p[1]-1][p[0]-1] = "-"

import itertools


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


ans = 0
for p in itertools.permutations(n, len(n)):
    flag = 1
    if p[0] != 0: 
        continue
    for i in range(N-1):
        if g[p[i]][p[i+1]] != "-":
            flag = 0
            break
    if flag:
        ans += 1
print(ans)

Solution (Python):

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


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

def next_permutation(L): 
    i = N - 2
    while i >= 0 and L[i] > L[i+1]:
        i -= 1

    if i == -1:
        return False

    j = i + 1
    while j < N and L[i] < L[j]:
        j += 1
    j -= 1

    L[i], L[j] = L[j], L[i]

    left = i + 1
    right = N - 1

    while left < right:
        L[left], L[right] = L[right], L[left]
        left += 1
        right -= 1

    return True


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


def judge(L): 
    for i in range(N-1):
        if not L[i:i+2] in lst:

            return False
    return True


def roop(L): 
    count = 0
    while True:
        


        if L[0] != 1: 
            print (count)
            break
        if judge(L):
            count += 1
        if not next_permutation(L):
            print (count)
            break
    return 'error'

roop(L)

Solution (Python):
import itertools

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

v = list(range(1,n+1))

edge = []
for i in range(m):
    a,b = map(int,input().split())
    edge.append((a,b))
    edge.append((b,a))
res = 0
for s in itertools.permutations(v):
    if s[0]!=1:
        continue
    flag = True
    for i in range(1,len(s)):
        if (s[i-1],s[i]) not in edge:
            flag =False
    if flag:
        res+=1   
print(res)

Solution (Python):
import sys
sys.setrecursionlimit(10**9)


def search(cr_node, cr_depth, is_visited, edges, max_depth):
    if cr_node in is_visited:
        return 0
    elif cr_depth == max_depth:
        return 1
    else:
        count = 0

        if edges[cr_node]:
            is_visited.add(cr_node)
            for edge in edges[cr_node]:
                count += search(edge, cr_depth + 1,
                                is_visited, edges, max_depth)
            is_visited.remove(cr_node)

        return count


def main():
    N, M = map(int, input().split())
    edges = dict()
    for i in range(N):
        edges[i] = []

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

    print(search(0, 1, set(), edges, N))


if __name__ == '__main__':
    main()

Solution (Python):
import sys

input_int = lambda:int(input())
input_ints = lambda:map(int,input().split())
input_ints_list = lambda:list(input_ints())
input_str = lambda:input()
input_strs = lambda:input().split()
input_lines = lambda n,f:[f() for _ in range(n)]

import functools,fractions
gcd = lambda a:functools.reduce(fractions.gcd,a) 
lcm_base = lambda a,b:(a*b)//fractions.gcd(a,b) 
lcm = lambda a:functools.reduce(lcm_base,a,1) 

import itertools
permutations = lambda a,n:itertools.permutations(a,n) 
combinations = lambda a,n:itertools.combinations(a,n) 
product = lambda a,b:itertools.product(a,b) 

init_array_1dim = lambda v,n:[v for _ in range(n)]
init_array_2dim = lambda v,n,m:[[v for _ in range(n)] for _ in range(m)]

import math

ceil = lambda a:math.ceil(a) 
floor = lambda a:math.floor(a) 

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

def init_graph(n,a,directed=False):
    visited = init_array_1dim(False,n)
    graph = init_array_2dim(False,n,n)
    for e in a:
        graph[e[0]-1][e[1]-1] = True
        if not directed:graph[e[1]-1][e[0]-1] = True 
    return visited,graph

def solution():
    N,M = input_ints()
    ab = input_lines(M,input_ints_list)
    visited,graph = init_graph(N,ab)
    visited[0] = True
    print(dfs_graph(0,N,graph,visited))

if __name__ == '__main__':
    solution()