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

Solution (Python):
def saiki(arr_lst,count,path,N):
	if len(path) == N:
		count[0] += 1
	else:
		here = path[-1]
		arrival = arr_lst[here]
		for next in arrival:
			if not next in path:
				newpath = path[:]
				newpath.append(next)
				saiki(arr_lst,count,newpath,N)


if __name__ == '__main__':
	N, M = map(int, input().split())
	arr_lst = [[]]

	for i in range(1,N+1):
		arr_lst.append([])

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

	count = [0]

	saiki(arr_lst,count,[1],N)

	print(count[0])

Solution (Python):
import sys
import itertools

import time
import math
import heapq
from collections import defaultdict
sys.setrecursionlimit(10 ** 7)
 
INF = 10 ** 18
MOD = 10 ** 9 + 7
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines



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

dp = [[-1] * n for i in range(1<<n)]

def rec(s,v,dp):
    if dp[s][v] >= 0:
        return dp[s][v]
        
    if s == (1<<n)-1:
        dp[s][v] = 1
        return 1
    
    res = 0
    for u in range(n):
        if (s>>u&1) == 0 and d[v][u] == 1:
            res += rec(s|(1<<u),u,dp)
    dp[s][v] = res
    return res

print(rec(1,0,dp))

Solution (Python):
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


from collections import defaultdict
n,m = map(int, input().split())
ns = defaultdict(set)
for _ in range(m):
    u,v = map(int, input().split())
    u -= 1
    v -= 1
    ns[u].add(v)
    ns[v].add(u)
dp = [[0]*(1<<n) for _ in range(n)]
dp[0][1] = 1
for b in range(1, 1<<n):
    for u in range(n):
        for i in range(n):
            if not (b>>i&1) and i in ns[u]:
                dp[i][b+(1<<i)] += dp[u][b]
ans = sum(dp[u][(1<<n)-1] for u in range(n))
print(ans)

Solution (Python):


from collections import deque 
import itertools
import math 

import sys



sys.setrecursionlimit(10**7) 
inf = float('inf')

is_debug = False

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

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



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

if is_debug:
    for row in M:
        print(row)
    print('-----------')

def main():
    '''メイン処理'''

    ok_count = 0
    
    
    for permutation in itertools.permutations(range(1,n)):
        move_list = list(permutation)
        if is_debug:
            print(move_list)

        
        move_count = 0
        now_n = 0 
        for next_n in move_list:
            if next_n in M[now_n]:
                now_n = next_n
                move_count += 1
            else:
                break
        if move_count == len(move_list):
            ok_count += 1
    
    print(ok_count)
            

if __name__ == "__main__":
    
    main()

Solution (Python):
from itertools import permutations

N,M = list(map(int,input().split()))
P=[]
for m in range(M):
    P.append(list(map(int,input().split())))

ad={}
for _ in range(1,N+1):
    ad[_]=set()
    
for p in P:
    ad[p[0]].add(p[1])
    ad[p[1]].add(p[0])

ans=0
for p in permutations(range(2,N+1),N-1):
    ans_flag=True
    start=1
    for p_ in p:
        end=p_

        if end not in ad[start]:

            ans_flag=False
            break
        start=p_
        
    if ans_flag==True:
        ans+=1
        
print(ans)

Solution (Python):
import sys
from collections import defaultdict
from collections import deque
from copy import deepcopy

def perm(h,r):
    n=len(r)
    stack=[]
    if n==0:
        return [h]
    for i in range(n):
        nh=h+[r[i]]
        nr=r[:i]+r[i+1:]
        stack+=perm(nh,nr)
    return stack
        
def main():
    n,m=map(int,input().split())
    e=[tuple(map(int,input().split())) for _ in range(m)]
    gm=[[0]*n for _ in range(n)]
    for edge in e:
        gm[edge[0]-1][edge[1]-1]=1
        gm[edge[1]-1][edge[0]-1]=1
    l=perm([],list(range(2,n+1)))
    c=0
    for s in l:
        s=[1]+s
        f=1
        for i in range(n-1):
            if gm[s[i]-1][s[i+1]-1]==0:
                f=0
                break
        if f:
            c+=1
    print(c)

if __name__=='__main__':
    main()

Solution (Python):
import itertools

N,M = map(int, input().split())
g = [[0 for i in range(N)] for j in range(N)]

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

  
jr = list(itertools.permutations(range(2,N+1),N-1))
js = []

for i in jr:
  j = list(i)
  j.insert(0,1)
  js.append(j)

ans = 0
  
for i in range(len(js)):
  hantei = True
  for j in range(N-1):
    a = js[i][j]
    
    b = js[i][j+1]
    
    if g[a-1][b-1] == 0:
      hantei = False
  if hantei:
    ans += 1

print(ans)

Solution (Python):
from itertools import *
N,M = map(int,input().split())
S = [list(map(int,input().split())) for m in range(M)]
a = 0

for p in permutations(range(1,N+1)):
  f = True
  if p[0]==1:
    for n in range(N-1):
      if sorted([p[n],p[n+1]]) not in S:
        f = False
    if f:
      a+=1

print(a)

Solution (Python):
N,M = map(int,input().split())
intx = lambda x:int(x)-1

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


visited = [False]*N
def dfs(loc,depth):
    if visited[loc]:
        return 0
    if depth == N-1:
        return 1
        
    visited[loc] = True
    path = 0
    for i in range(N):
        if adj[loc][i]:
            path+=dfs(i,depth+1)
    
    visited[loc] = False
    
    return path
    
print(dfs(0,0))

Solution (Python):
def dfs(v,visited):
  if all(visited):
    return 1
  res=0
  for nv in G[v]:
    if visited[nv]:
      continue
    visited[nv]=1
    res+=dfs(nv,visited)
    visited[nv]=0
  return res
 
n,m=map(int, input().split())
G=[[] for _ in range(n)]
visited=[0]*n
res=0
 
for i in range(m):
  a,b=map(int, input().split())
  G[a-1].append(b-1)
  G[b-1].append(a-1)

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

Solution (Python):
N, M = map(int, input().split())
L = [tuple(map(int, input().split())) for _ in range(M)]
import itertools
l = [i for i in range(2, N+1)]
Ps = itertools.permutations(l, N-1)
c = 0
for P in Ps:
  T = 1
  for p in P:
    if (T, p) in L or (p, T) in L:
      T = p
    else:
      break
  else:
    c += 1
print(c)

Solution (Python):



def dfs(now_p, visited, comb_p, p_num):
    
    if len(visited) == p_num:
        return 1

    ans = 0

    
    for tmp_p in comb_p:
        if tmp_p[0] == now_p and tmp_p[1] not in visited:
            
            tmp_visited = visited[:]
            tmp_visited.append(tmp_p[1])
            
            
            next_p = tmp_p[1]
            
            
            tmp_comb = comb_p[:]
            tmp_comb.remove(tmp_p)
            
            tmp_p_r = [tmp_p[1], tmp_p[0]]
            tmp_comb.remove(tmp_p_r)
            
            
            ans += dfs(next_p, tmp_visited, tmp_comb, p_num)

    return ans


N, M = map(int, input().split())
a_b = []
tmp = []
tmp_r = []


for i in range(M):
    tmp = list(map(int, input().split()))
    tmp_r = [tmp[1], tmp[0]]
    a_b.append(tmp)
    a_b.append(tmp_r)

visited = [1]


pass_num = dfs(1, visited, a_b, N)
print(pass_num)

Solution (Python):
import sys
sys.setrecursionlimit(10**8)
n, m = map(int, input().split())
g = [[] for i in range(n)]
for  i in range(m):
    a, b = map(int, input().split())
    a-=1; b-=1
    g[a].append(b)
    g[b].append(a)

used = [False] * n
ans = 0
def dfs(i, depth=1):
    ret = 0
    if depth==n:
        return 1
    else:
        for e in g[i]:
            if used[e]:
                continue
            used[e] = True
            ret+=dfs(e, depth+1)
            used[e] = False
    return ret

used[0] = True
print(dfs(0, 1))

Solution (Python):
import sys
sys.setrecursionlimit(10**8)
n, m = map(int, input().split())
g = [[] for i in range(n)]
for  i in range(m):
    a, b = map(int, input().split())
    a-=1; b-=1
    g[a].append(b)
    g[b].append(a)

used = [False] * n
ans = 0
def dfs(itr, n, cnt=0):
    ans = 0
    if len(itr)==n:
        return 1
    else:
        ans = cnt
        for e in g[itr[-1]]:
            if used[e]:
                continue
            used[e] = True
            ans+=dfs(itr+[e], n)
            used[e] = False
    return ans

used[0] = True
print(dfs([0], n, 0))

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

from itertools import permutations
ans=0
p=list(permutations([x for x in range(1,n)]))
for pp in p:
  ok=True
  t=[0]+list(pp)
  for i in range(1,n):
    if G[t[i-1]][t[i]]==0:
      ok=False
  if ok:ans+=1
print(ans)

Solution (Python):
from itertools import permutations
n,m=map(int,input().split())
lst=[[] for _ in range(n)]
for i in range(m):
    a,b=map(int,input().split())
    lst[a-1].append(b-1)
    lst[b-1].append(a-1)
kumi=list(permutations(range(1,n)))
ans=0
for i in kumi:
    switch=1
    prev=0
    for j in range(n-1):
        if not i[j] in lst[prev]:
            switch=0
            break
        prev=i[j]
    if switch==1:
        ans+=1
print(ans)

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)

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

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

Solution (Python):
import sys
from itertools import permutations

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    """
    順列を全部試す。計算量O(N!)
    """
    n, m = map(int, input().split())
    tree = [[] for _ in range(n)]
    for _ in range(m):
        a, b = map(int, input().split())
        tree[a - 1].append(b - 1)
        tree[b - 1].append(a - 1)

    res = 0
    for pattern in permutations(range(n)):
        if pattern[0] == 0:
            for i in range(n - 1):
                if pattern[i + 1] not in tree[pattern[i]]:
                    break
            else:
                res += 1
    print(res)


def resolve2():
    """
    bit DP。計算量O(2^N*N^2)
    """
    n, m = map(int, input().split())
    edge = [[f_inf] * n for _ in range(n)]
    for _ in range(m):
        a, b = map(int, input().split())
        edge[a - 1][b - 1] = 1
        edge[b - 1][a - 1] = 1

    dp = [[f_inf] * n for _ in range(1 << n)]
    dp[0][0] = 0
    cnt = [[0] * n for _ in range(1 << n)]
    cnt[0][0] = 1
    for S in range(1 << n):
        for v in range(n):
            for u in range(n):
                if v == u or S & (1 << v) or edge[u][v] == f_inf:
                    continue
                if dp[S | (1 << v)][v] > dp[S][u] + edge[u][v]:
                    dp[S | (1 << v)][v] = dp[S][u] + edge[u][v]
                    cnt[S | (1 << v)][v] = cnt[S][u]
                elif dp[S | (1 << v)][v] == dp[S][u] + edge[u][v]:
                    cnt[S | (1 << v)][v] += cnt[S][u]

    mi = min(dp[-2])
    idx = []
    for i in range(n):
        if dp[-2][i] == mi:
            idx.append(i)

    res = 0
    for j in idx:
        res += cnt[-2][j]
    print(res)


if __name__ == '__main__':
    resolve2()

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    n, m = map(int, input().split())
    edge = [[f_inf] * n for _ in range(n)]
    for _ in range(m):
        a, b = map(int, input().split())
        edge[a - 1][b - 1] = 1
        edge[b - 1][a - 1] = 1

    dp = [[f_inf] * n for _ in range(1 << n)]
    dp[0][0] = 0
    cnt = [[0] * n for _ in range(1 << n)]
    cnt[0][0] = 1
    for S in range(1 << n):
        for v in range(n):
            for u in range(n):
                if v == u or S & (1 << v) or edge[u][v] == f_inf:
                    continue
                if dp[S | (1 << v)][v] > dp[S][u] + edge[u][v]:
                    dp[S | (1 << v)][v] = dp[S][u] + edge[u][v]
                    cnt[S | (1 << v)][v] = cnt[S][u]
                elif dp[S | (1 << v)][v] == dp[S][u] + edge[u][v]:
                    cnt[S | (1 << v)][v] += cnt[S][u]

    mi = min(dp[-2])
    idx = []
    for i in range(n):
        if dp[-2][i] == mi:
            idx.append(i)

    res = 0
    for j in idx:
        res += cnt[-2][j]
    print(res)


if __name__ == '__main__':
    resolve()

Solution (Python):
from itertools import permutations
N,M=map(int,input().split())
G=[[] for _ 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)            
  
P=permutations(range(0,N),N)      
ans=0

for A in P:
  if A[0]!=0:                     
    continue
  for i in range(N-1):
    if not (A[i+1]  in G[A[i]]):
      break
  else:
    ans += 1
print(ans)

Solution (Python):
N,M=map(int,input().split())
G=[[] for _ 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)

from itertools import permutations

P=permutations(range(1,N),N-1)

cnt=0
for r in P:
    now=0
    F=True
    for x in r:
        if x in G[now]:
            now=x
        else:
            F=False
    if F:
        cnt+=1
print(cnt)

Solution (Python):
from itertools import permutations
def main():
    n, m = list(map(int, input().split()))
    G = [set() for _ in range(n)]
    for _ in range(m):
        a, b = list(map(lambda x:int(x) - 1, input().split()))
        G[a].add(b)
        G[b].add(a)
    ans = 0
    for P in permutations(range(1, n)):
        pre = 0
        for p in P:
            if p not in G[pre]:
                break
            pre = p
        else:
            ans += 1
    print(ans)

if __name__ == '__main__':
    main()

Solution (Python):
N,M=map(int,input().split())
G=[[] for _ 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)

seen=[0]*N
ans=[]

def DFS(x,n):
    if len(n)==N:
        return True
    for a in G[x]:
        if seen[a]==0:
            seen[a]=1
            if DFS(a,n+str(a)):ans.append(n+str(a))
            seen[a]=0
seen[0]=1
DFS(0,"0")

print(len(ans))

Solution (Python):
from itertools import permutations
N,M = map(int,input().split())
cc = [list(map(int,input().split())) for i in range(M)]
count = 0
for i in permutations([i+1 for i in range(N)],N):
  bb = 0
  if i[0] == 1:
    for j in range(N-1):
      aa = [i[j],i[j+1]]
      if aa in cc or aa[::-1] in cc:
        bb += 1
        if bb == N-1:
          count += 1
        continue
      else:
        break
print(count)

Solution (Python):
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10 ** 8)
from itertools import accumulate
from itertools import permutations
from itertools import combinations
from collections import defaultdict
from collections import Counter
import fractions
import math
from collections import deque
from bisect import bisect_left
from bisect import bisect_right
from bisect import insort_left
import itertools
from heapq import heapify
from heapq import heappop
from heapq import heappush
import heapq
from copy import deepcopy
from decimal import Decimal
alf = list("abcdefghijklmnopqrstuvwxyz")
ALF = list("ABCDEFGHIJKLMNOPQRSTUVWXYZ")

INF = float("inf")


N,M = map(int,input().split())
P = [[] for _ in range(N)]
for i in range(M):
    a,b = map(int,input().split())
    a,b = a-1,b-1
    P[a].append(b)
    P[b].append(a)
ans = 0
def dfs(cur,d,num):
    global ans
    if num == N:
        ans += 1
        return
    else:
        li = P[cur]
        for chi in li:
            if d[chi] == 1:
                continue
            c = deepcopy(d)
            c[chi] += 1
            dfs(chi,c,num+1)
        return
d = defaultdict(int)
d[0] += 1
dfs(0,d,1)
print(ans)

Solution (Python):
import itertools

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

nodes = [i for i in range(n)]
ls = list(itertools.permutations(nodes))

ans = 0
for root in ls:
    if root[0] != 0:
        continue
    ok = 1
    for i in range(n-1):
        if list(root[i:i+2]) not in ab and list(reversed(list(root[i:i+2]))) not in ab:
            ok = 0
    if ok:
        ans += 1

print(ans)

Solution (Python):
import sys
import math
import itertools
import statistics
n,m=map(int,input().split())
side=[]
for _ in range(m):
    side.append(tuple(map(int,input().split())))
per_lis =[i for i in list(itertools.permutations(list(range(1,n+1)))) if i[0]==1]
ans=0
for one_case in per_lis:
    tmp=0
    for i in range(n-1):
        if ((one_case[i],one_case[i+1]) in side) or ((one_case[i+1],one_case[i]) in side):
            tmp+=1
    if tmp==n-1:
        ans+=1
print(ans)

Solution (Python):
import sys

def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())

n,m = LI()

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

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

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

Solution (Python):

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

def DFS(v,visited):
    
    if all(visited):
        return 1
    ans = 0
    for i in G[v]:
        if visited[i]:
            continue
        visited[i] = True
        ans += DFS(i,visited)
        visited[i] = False
    return ans

print(DFS(0,visited))

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)

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

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

Solution (Python):
from collections import deque

def dfs(G, visited, s, n, ans):
  
  if all(visited) :
    ans += 1
    return ans
  
  for i in G[s] :
    if visited[i] == False :
      visited[i] = True
      ans = dfs(G, visited, i, n, ans)
      visited[i] = False
  return ans


n,m = map(int,input().split())
G = [[] for j 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)
  

visited = [False for i in range(n)]
visited[0] = True
ans = 0
print(dfs(G, visited, 0, n, 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(v,N,visited):
    if all(visited):
        return 1
    
    ret=0
    for new_v in graph[v]:
        if visited[new_v]:
            continue
        
        visited[new_v]=True
        ret+=dfs(new_v,N,visited)
        visited[new_v]=False
    
    return ret

print(dfs(0,N,visited))

Solution (Python):
import math

import itertools
import queue
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit


ipt = stdin.readline
setrecursionlimit(10**7)

def main():
    n,m = map(int,ipt().split())
    way = [[] for i in range(n+1)]
    ans = 0
    for i in range(m):
        a,b = map(int,ipt().split())
        way[a].append(b)
        way[b].append(a)
    for i in itertools.permutations(list(range(2,n+1))):
        p = 1
        f = True
        for j in i:
            if not j in way[p]:
                f = False
                break
            else:
                p = j
        if f:
            ans += 1
    print(ans)

    return None

if __name__ == '__main__':
    main()

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)

def dfs(v, seen):
    if all(seen):
        return 1
    ans=0
    for vv in graph[v]:
        if seen[vv]:
            continue
        seen[vv]=True
        ans+=dfs(vv, seen)
        seen[vv]=False
    return ans

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

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

def dfs(v, seen):
    if all(seen):
        return 1
    ans=0
    for i in graph[v]:
        if seen[i]:
            continue
        seen[i]=True
        
        ans+=dfs(i, seen)
        seen[i]=False
    return ans

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

Solution (Python):
from itertools import permutations
import math
n,m = map(int,input().split())
G = [[] for i in range(n)]
ans = 0
for i in range(m):
  a,b = map(int,input().split())
  G[a-1].append(b-1)
  G[b-1].append(a-1)
for per in permutations(range(n)):
  if per[0] != 0:
    continue
  for i in range(n-1):
    if not (per[i+1]  in G[per[i]]):
      break
  else:
    ans += 1
print(ans)

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

ans = 0
def dfs(x, visited):
    global ans
    if len(visited) == N:
        ans += 1
        return

    for b in ab[x]:
        if b not in visited:
            dfs(b, visited + [b])
    return

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

Solution (Python):
import itertools

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

ans = 0
for v in itertools.permutations(range(1, N)):
    ok = True
    a = 0
    for b in v:
        if {a, b} not in ab:
            ok = False
            break
        a = b
    if ok:
        ans += 1

print(ans)

Solution (Python):
import itertools

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

seq = list(range(2, n+1))
ptr = list(itertools.permutations(seq, n-1))

ans = 0
for i in ptr:
    flag2 = True
    for j in range(n-1):
        flag = False
        if j == 0:
            for a,b in ab:
                if (a,b) == (1,i[j]) or (a,b) == (i[j],1):
                    flag = True
                    break
        else:
            for a,b in ab:
                if (a,b) == (i[j], i[j-1]) or (a,b) == (i[j-1], i[j]):
                    flag = True
                    break
        if not flag:
            flag2 = False
            break
    if flag2:
        ans += 1

print(ans)

Solution (Python):
(n,m), *ab = [list(map(int, s.split())) for s in open(0)]

from collections import defaultdict

d = defaultdict(list)

for a,b in ab:
    d[a] += [b]
    d[b] += [a]

def count_paths(passed, cur, d, n):

    if len(passed) == n-1:
        return 1
    ans = 0
    for nx in d[cur]:
        if nx not in passed:
            ans += count_paths(passed+[cur], nx, d, n)
    return ans

print(count_paths([],1,d,n))

Solution (Python):
from itertools import permutations
N,M = map(int,input().split())
G = {i:[] for i in range(1,N+1)}
for _ in range(M):
    a,b = map(int,input().split())
    G[a].append(b)
    G[b].append(a)
cnt = 0
for x in permutations(range(2,N+1),N-1):
    flag = 0
    for i in range(N-1):
        if i==0:
            if x[0] in G[1]:continue
            else:
                flag = 1
                break
        if x[i] in G[x[i-1]]:continue
        else:
            flag = 1
            break
    if flag==0:
        cnt += 1
print(cnt)

Solution (Python):
from itertools import *
N,M=map(int,input().split())
X=list(permutations(list(range(2,N+1))))
P=0
a,b=0,0
S=set()
for i in range(M):
  a,b=map(int,input().split())
  S.add((a,b))
  S.add((b,a))
for i in range(len(X)):
  for j in range(N-1):
    if not(((1 if j==0 else X[i][j-1]),X[i][j]) in S):
      break
    if j==N-2:
      P+=1
print(P)

Solution (Python):
from itertools import permutations

n, m = map(int, input().split())
G = [set() for _ in range(n)]
for _ in range(m):
  a, b = map(int, input().split())
  a -= 1
  b -= 1
  G[a].add(b)
  G[b].add(a)
ans = 0
for l in permutations(range(n)):
  if l[0] != 0:
    continue
  for i in range(n-1):
    if l[i+1] not in G[l[i]]:
      break
  else:
    ans += 1
print(ans)

Solution (Python):
from itertools import permutations


N, M = [int(i) for i in input().split()]
D = [[False] * N for _ in range(N)]
for _ in range(M):
    a, b = [int(i) for i in input().split()]
    D[a - 1][b - 1] = True
    D[b - 1][a - 1] = True
perm = [[0] + list(p) for p in list(permutations(range(1, N)))]

cnt = 0
for p in perm:
    flg = True
    for i in range(N - 1):
        if not D[p[i]][p[i + 1]]:
            flg = False
            break
    if flg:
        cnt += 1
print(cnt)

Solution (Python):
(n, m) = tuple(map(int, input().split()))
(a, b) = zip(*list([input().split() for _ in range(m)]))

pt_c_ns = {}
for i in range(1, n + 1):
    pt_c_ns[str(i)] = []
for i in range(m):
    pt_c_ns[a[i]].append(b[i])
    pt_c_ns[b[i]].append(a[i])

paths_c = ["1"]
for _ in range(n - 1):
    paths_n = []
    for path in paths_c:
        pt_c = path[-1]
        pt_ns = pt_c_ns[pt_c]
        for pt_n in pt_ns:
            if pt_n not in path:
                paths_n.append(path + pt_n)
    paths_c = paths_n[:]

print(len(paths_c))

Solution (Python):
import itertools
N,M = list(map(int,input().split()))
lis = []
for i in range(N):
    lis.append([i+1])
for i in range(M):
    a,b = list(map(int,input().split()))
    lis[a-1].append(b)
    lis[b-1].append(a)
pemls = [i for i in range(2,N+1)]
lis_root = list(itertools.permutations(pemls,N-1))

counter = 0
for i in range(len(lis_root)):
    now = 1
    step = [1]
    flag = 1
    for j in range(len(lis_root[i])):
        
        if lis_root[i][j] in lis[now-1]:
            now = lis_root[i][j]
            step.append(now)
        else:
            flag = 0
            break
        if len(step) == N:
            break
    if flag ==1:
        counter += 1
        
print(counter)

Solution (Python):
from itertools import permutations
n, m = map(int, input().split())
g = [[] for _ in range(n)]
for _ in range(m):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    g[a].append(b)
    g[b].append(a)
ans = 0
for order in permutations(range(1, n), n-1):
    seen = [False] * n
    seen[0] = True
    pre = 0
    for v in order:
        if v not in g[pre] or seen[v]:
            break
        pre = v
        seen[v] = True
    else:
        ans += 1
print(ans)

Solution (Python):
import sys


def resolve():
    import itertools
    readline = sys.stdin.readline    

    N, M = map(int, readline().split())
    lst = [set(map(int, readline().split())) for _ in [0] * M]
    d = []
    ans = 0
    
    
    for i in itertools.permutations(range(2, N + 1), N - 1):
        cnt = 0
        if {1, i[0]} in lst:
            cnt += 1
            for j in range(N - 2):
                if {i[j], i[j + 1]} in lst:
                    cnt += 1
                    pass
                else:
                    break
        if cnt == N - 1:
            ans += 1
    print(ans)
    

if __name__ == "__main__":
    resolve()

Solution (Python):
def resolve():
    import sys
    import itertools
    readline = sys.stdin.readline    

    N, M = map(int, readline().split())
    lst = [set(map(int, readline().split())) for _ in [0] * M]
    d = []
    ans = 0
    for i in range(2, N + 1):
        d.append(i)
    for i in itertools.permutations(d, N - 1):
        cnt = 0
        if {1, i[0]} in lst:
            cnt += 1
            for j in range(N - 2):
                if {i[j], i[j + 1]} in lst:
                    cnt += 1
                    pass
                else:
                    break
        if cnt == N - 1:
            ans += 1
    print(ans)
    

if __name__ == "__main__":
    resolve()

Solution (Python):
from itertools import permutations
import sys


def input(): return sys.stdin.readline().strip()
def I(): return int(input())
def LI(): return list(map(int, input().split()))
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 S(): return input()
def LS(): return input().split()


INF = float('inf')
n, m = LI()
edges = [[False] * n for _ in range(n)]  
for _ in range(m):
    a, b = LI()
    a -= 1
    b -= 1
    edges[a][b] = True
    edges[b][a] = True






permu = list(permutations(range(1, n)))

ans = 0
for p in permu:
    now = 0  
    is_ok = True  
    for j in p:
        if edges[now][j]:
            now = j
        else:
            is_ok = False
            break
    if is_ok:
        ans += 1


print(ans)

Solution (Python):
from itertools import permutations
n, m = map(int, input().split())
path = []
for i in range(m):
    a, b = map(int, input().split())
    path.append([a,b])
    path.append([b,a])
import itertools
per = [i for i in range(2,n+1)]
data = list(itertools.permutations(per, n-1))  
flg = 0
for k in range(len(data)):
    tmp = [[1, data[k][0]]]
    for i in range(n-2):
        tmp.append([data[k][i],data[k][i+1]])
    cnt = 0
    for var in tmp:
        if var in path:
            cnt += 1
    if cnt == len(tmp):
        flg += 1
print(flg)