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):
n, m = map(int, input().split())
g = [set() for _ in range(n)]

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


import itertools
ans = 0
for per in itertools.permutations(range(n)):
    if per[0] != 0:
        continue
    for i in range(n-1):
        if per[i+1]  not in g[per[i]]:
            break
    else:
        ans += 1
print(ans)

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


def isOK(seq):
    s = 1
    for t in seq:
        if t in edge[s]:
            s = t
        else:
            return False
    return True


ans = 0
for seq in itertools.permutations(range(2, N + 1)):
    if isOK(seq):
        ans += 1

print(ans)

Solution (Python):
import sys
from itertools import permutations

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

    count = 0
    for s in permutations(range(N), N):
        Visited = [False for _ in range(N)]
        for i, n in enumerate(s):
            if i == 0:
                if n != 0: break
                else: Visited[0] = True
            else:
                if n in Edge[s[i-1]]: Visited[n] = True
                else: break
        else: count += 1
    print(count)

    return 0

if __name__ == "__main__":
    solve()

Solution (Python):
import itertools

n,m=map(int,input().split())
g=[list(map(int,input().split())) for _ in range(m)]
v=list(itertools.permutations(range(1,n+1)))

ans=0

for x in v:
    tf=True
    if x[0]!=1:
        tf=False
    else:
        for i in range(n-1):
            if not ([x[i],x[i+1]] in g or [x[i+1],x[i]] in g):
                tf=False
                break
    if tf:
        ans+=1
print(ans)

Solution (Python):

from itertools import permutations

def main():
    n, m = map(int, input().split())
    edge = set()
    for _ in range(m):
        a, b = map(int, input().split())
        edge.add((a-1, b-1))
        edge.add((b-1, a-1))
    
    node = []
    for i in range(n):
        node.append(i)
    cnt = 0
    for p in permutations(node):
        if p[0] == 0:
            f = True
            for j in range(n-1): 
                if (p[j], p[j+1]) not in edge:
                    f = False
            if f:
                cnt += 1 
    print(cnt)
main()

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

n,w = map(int,readline().split()) 
g = [[] for i in range(n)] 
for i in range(w):
    x,y = map(int,readline().split())
    x,y = x-1,y-1
    g[x].append(y)
    g[y].append(x)

def dfs():
    ans = 0
    queue = deque([[0]]) 
    while queue:
        lst = queue.popleft()
        if len(lst)==n:
            ans += 1
            continue
        for i in g[lst[-1]]:
            if not i in lst:
                queue.append(lst+[i])
    
    return ans

print(dfs())

Solution (Python):
from itertools import permutations
n, m = map(int, input().split())
ab = [[] for i in range(n)]
for i in range(m):
    a, b = map(lambda x: int(x) - 1, input().split())
    ab[a].append(b)
    ab[b].append(a)
cnt = 0
if n == 2:
    if 1 in ab[0]:
        print(1)
    else:
        print(0)
    exit()
for p in permutations(range(1, n)):
    if p[0] in ab[0]:
        flag = True
        for i in range(n - 2):
            if p[i + 1] not in ab[p[i]]:
                flag = False
                break
        if flag:
            cnt += 1
print(cnt)

Solution (Python):
import itertools
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines

def main():
    N, M, *ab = map(int, read().split())
    E = [[] for _ in range(N+1)]

    for a, b in zip(*[iter(ab)] * 2):
        E[a].append(b)
        E[b].append(a)
    
    ans = 0
    fact_p = itertools.permutations(range(2,N+1))
    for p in fact_p:
        par = 1
        flag = True
        for i in p:
            if par not in E[i]:
                flag = False
                break
            par = i
            
        if flag:
            ans += 1
    
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
import itertools

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

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

cnt=0

for p in itertools.permutations(range(n),n):
    if p[0]>0:
        continue

    for i in range(n-1):
        a=p[i]
        b=p[i+1]

        if not (b in c[a]):
            break
    else:
        cnt+=1

print(cnt)

Solution (Python):
def dfs(i):
  global count
  global seen
  global G

  end = True
  for n in range(N):
    if seen[n] == 0 and n != i:
      end = False

  if (end):
    count += 1
    return

  seen[i] = 1
  for g in G:
    if g[0] == i:
      if seen[g[1]] == 1:
        continue
      dfs(g[1])
  
    if g[1] == i:
      if seen[g[0]] == 1:
        continue
      dfs(g[0])

  seen[i] = 0

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

G = []

for i in li:
  G.append([i[0]-1, i[1]-1])

count = 0
seen = [0] * N
dfs(0)

print(count)

Solution (Python):






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

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


st=[[1,0]]

df={}
lp=[0]
ans=0
while st:
    
    tmptp=st.pop()
    
    tmp=tmptp[0]
    ptmp=tmptp[1]
    p=lp.pop()
    while p!=ptmp:
        del df[p]
        p=lp.pop()
    lp.append(p)
    lp.append(tmp)
    df[tmp]=1
    if len(df)==N:
        ans+=1
        
        
        
    for c in lc[tmp-1]:
        if not c in df:
            
            st.append([c,tmp])
            
print(ans)

Solution (Python):
n, m = map(int, input().split())
link = [[] for _ in range(n)]
for i in range(m):
    tmp = list(map(int,input().split()))
    link[tmp[0]-1].append(tmp[1]-1)
    link[tmp[1]-1].append(tmp[0]-1)
lis = list(range(1,n))
ans=0
from itertools import *
for perm in list(permutations(lis)):
    last=0
    ok=1
    for i in range(len(perm)):
        if perm[i] not in link[last]:
            ok=0
        last=perm[i]
    ans+=ok
print(ans)

Solution (Python):
n, m = map(int, input().split())
link = [[] for _ in range(n)]
for i in range(m):
    tmp = list(map(int,input().split()))
    link[tmp[0]-1].append(tmp[1]-1)
    link[tmp[1]-1].append(tmp[0]-1)

lis=[]
for i in range(1,n):
    lis.append(i)
ans=0
from itertools import *
for perm in list(permutations(lis)):
    last=0
    ok=True
    for i in range(len(perm)):
        if perm[i] not in link[last]:
            ok=False
            break
        last=perm[i]
    if ok:
        ans+=1
print(ans)

Solution (Python):
n, m = map(int, input().split())
link = [[] for _ in range(n)]
for i in range(m):
    tmp = list(map(int,input().split()))
    link[tmp[0]-1].append(tmp[1]-1)
    link[tmp[1]-1].append(tmp[0]-1)

from collections import deque
Q = deque()
Q.append([0,[0]]) 

import copy
ans=0
while Q:
    now,org_hist = Q.popleft()

    for nxt in link[now]:
        if nxt in org_hist:
            continue
        hist = copy.copy(org_hist)

        hist.append(nxt)
        if len(hist) >= n:
            ans+=1
        else:
            Q.append([nxt,hist])
print(ans)

Solution (Python):
import itertools

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

ans = 0
pattern = list(itertools.permutations(list(range(2, n+1))))
for i in pattern:
    li = list(i)
    li.insert(0, 1)
    pattern_check = True
    for j in range(0, n-1):
        path_check = False
        for k in range(m):
            if len({li[j], li[j+1]} & set(ab[k])) == 2:
                path_check = True
                break
        if not path_check:
            pattern_check = False
            break
    if pattern_check:
        
        ans += 1
print(ans)

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

path=[[] for _ in range(n)]
for a,b in AB:
  a,b=a-1,b-1
  path[a].append(b)
  path[b].append(a)
ans=0
for ptn in itertools.permutations(range(1,n)):
  s=0
  for nex in ptn:
    if s not in path[nex]: break
    s=nex
  else:
    ans+=1
print(ans)

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

visited = [False] * N
visited[0] = True
d = {}
for a, b in A:
    d.setdefault(b-1, []).append(a-1)
    d.setdefault(a-1, []).append(b-1)

l = sorted(d.items())

def dfs(v, seen):
    if False not in seen: return 1
    
    c = 0
    for i in d[v]:
        if (seen[i]): continue
        seen[i] = True
        c += dfs(i, seen)
        seen[i] = False
    return c
    
print(dfs(0, visited))

Solution (Python):
N, M = map(int, input().split())
g = [[] for _ in range(N + 1)]
for _ in range(M):
    x, y = map(int, input().split())
    g[x].append(y)
    g[y].append(x)

ans = 0
todo = [(1, list(range(2, N + 1)))]
while todo:
    p, r = todo.pop()
    for np in g[p]:
        if np in r:
            if len(r) == 1:
                ans += 1
            else:
                nr = r[:]
                nr.remove(np)
                todo.append((np, nr))
print(ans)

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

N, M = [int(x) for x in input().split()]
G = [[] for _ in range(N + 1)]

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

import itertools
l = [x for x in range(2, N + 1)]
per = list(itertools.permutations(l))

cnt = 0

for i in range(len(per)):
    route = [1] + list(per[i])
    flag = 1
    for k in range(len(route) - 1):
        if route[k + 1] not in G[route[k]]:
            flag = 0
            break
    cnt += flag

print(cnt)

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 main():
    N,M=MI()
    edge_matrix = [[False]*N for _ in range(N)]
    for _ in range(M):
        a,b = MI_()
        edge_matrix[a][b] = True
        edge_matrix[b][a] = True
    ans = 0
    for it in permutations([i for i in range(N)]):
        path = [i for i in it]
        if path[0]!=0:
            continue
        ok = True
        for i in range(N-1):
            from_ = path[i]
            to_ = path[i+1]
            if not edge_matrix[from_][to_]:
                ok = False
                break
        if ok:
            ans += 1
    print(ans)
if __name__ == '__main__':
    main()

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 main():
    N,M=MI()
    edge_matrix = [[False]*N for _ in range(N)]
    for _ in range(M):
        a,b = MI_()
        edge_matrix[a][b] = True
        edge_matrix[b][a] = True
    ans = 0
    for it in permutations([i for i in range(N)]):
        path = [i for i in it]
        if path[0]!=0:
            continue
        ok = True
        for i in range(N-1):
            from_ = path[i]
            to_ = path[i+1]
            if not edge_matrix[from_][to_]:
                ok = False
                break
        if ok:
            ans += 1
    print(ans)
if __name__ == '__main__':
    main()

Solution (Python):

import sys
import itertools


def solve(N: int, M: int, a: "List[int]", b: "List[int]"):

    paths = list(zip(a, b))

    permutations = []
    for permutation in itertools.permutations(range(1, N + 1)):
        if permutation[0] == 1:
            permutations.append(permutation)
        else:
            break
    
    result = 0
    for permutation in permutations:
        able = True
        for i in range(N - 1):
            if (
                permutation[i : i + 1 + 1] in paths
                or tuple(reversed(list(permutation[i : i + 1 + 1]))) in paths
            ):
                pass
            else:
                able = False
                break

        if able:
            result += 1

    print(result)

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

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

dp = [[0 for _ in range(N)] for _ in range(1 << N)]
dp[1][0] = 1

for bit in range(1 << N):
    for v in range(N):

        if bit & (1 << v) is False:
            continue

        sub = bit ^ (1 << v)

        for u in range(N):
            if (v in g[u]) and (sub & (1 << u)):
                dp[bit][v] += dp[sub][u]

print(sum(dp[-1]))

Solution (Python):
N,M = map(int,input().split())
G = [[]for i in range(N)]
for i in range(M):
    a,b = map(lambda x:int(x)-1,input().split())
    G[a].append(b)
    G[b].append(a)
ans = 0
H = [[0]]
while H:
    h = H.pop()
    if len(h)==N:
        ans+=1
        continue
    p = h[-1]
    for v in G[p]:
        if not(v in h):
            H.append(h+[v])
print(ans)

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

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


def advance(v, passed):

    global n_path
    passed.append(v)
    if len(passed) == N:
        n_path += 1

    for n in g[v]:
        if n not in passed:
            advance(n, passed)

    passed.remove(v)


advance(0, [])
print(n_path)

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

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

ans=0
for ptn in itertools.permutations(range(1,n)):
  start=0
  for nex in ptn:
    if start not in path[nex]: break
    start=nex
  else:
    ans+=1
print(ans)

Solution (Python):
N, M = map(int, input().split())
G = [[] 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)
cnt = [0]
def dfs(V, s):
    V[s] = 1
    if sum(V) == N:
        cnt[0] += 1                    
    else:
        for adj in G[s]:
            if V[adj] == 0:             
                dfs(V[:adj] + [1] + V[adj + 1:], adj)  
dfs([0] * N, 0)
print(cnt[0])

Solution (Python):
import numpy as np
def DFS(answer,matrix,color,N,i):
    if not 0 in color:
        answer[0]+=1
    for j in range(N):
        if color[j]==0 and matrix[i][j]==1:
            color[j] = 1
            DFS(answer,matrix,color,N,j)
            color[j] = 0
    
def main():
    N,M = map(int,input().split())
    S = [list(map(int,input().split())) for _ in range(M)]
    matrix = np.zeros([N,N],dtype=np.int32)
    for s in S:
        matrix[s[0]-1][s[1]-1]=1
        matrix[s[1]-1][s[0]-1]=1
    color = [0]*N
    color[0] = 1
    answer = [0]
    DFS(answer,matrix,color,N,0)
    print(answer[0])
    

if __name__=='__main__':
    main()

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

for i in range(n):
    paths.append([0]*n)

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

def dfs(now,depth):
    if visited[now]==1:
        return 0
    elif depth==n-1:
        return 1
    else:
        visited[now]=1
        total=0
        for i in range(n):
            if paths[now][i]==1:
                total+=dfs(i,depth+1)
        visited[now]=0
        return total
print(dfs(0,0))

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

from collections import defaultdict
d = defaultdict(list)
for _ in range(m):
    a, b = map(int, input().split())
    d[a].append(b)
    d[b].append(a)

from itertools import permutations
C = permutations(range(2, n+1))
C = list(map(lambda x: [1]+list(x), C))

ans = 0
for c in C:
    for i in range(n-1):
        if c[i+1] not in d[c[i]]:
            break
    else:
        ans += 1
print(ans)

Solution (Python):
import itertools
import copy

n, m = map(int, input().split())
List = [list(map(int, input().split())) for i in range(m)]
check = [0 for _ in range(n)]
res = 0

def all_1(res_list):
    leng = len(res_list)
    for i in range(leng):
        if res_list[i] == 0:
            return False
    return True

def coo(i, check):
    global res
    b = copy.deepcopy(check)
    if b[i-1] == 0:
        b[i-1] = 1
        if all_1(b):
            res += 1
        length = len(List)
        for j in range(length):
            if List[j][0] == i:
                coo(List[j][1], b)
        for j in range(length):
            if List[j][1] == i:
                coo(List[j][0], b)
        
        
coo(1, check)
print(res)

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 func(path,p,count):
  if len(path) == n:
    return count + 1
  for i in graph[p]:
    if i in path:
      continue
    count = func(path+[i],i,count)
  return count
print(func([1],1,0))

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 func(path,p,count):
  if len(path) == n:
    return count + 1
  for i in graph[p]:
    if i in path:
      continue
    count = func(path+[i],i,count)
  return count
print(func([1],1,0))

Solution (Python):
import itertools
N, M = [int(x) for x in input().split()]
lst = [[int(x) for x in input().split()] for i in range(M)]
N_lst = list(range(1, N + 1))
per = []

def check(tup):
    for i in range(N - 1):
        x = tup[i]
        y = tup[i + 1]
        if x > y:
            x, y = y, x
        if not [x, y] in lst:
            return False
    return True

for v in itertools.permutations(N_lst):
    if v[0] == 1:
        per.append(v)
cnt = 0
for p in per:
    if check(p): cnt += 1
print(cnt)

Solution (Python):
import numpy as np
nmax = 8
graph = np.array([[False]*nmax]*nmax)
 
n, m = map(int, input().split())
for i in range(m):
    a, b = map(int, input().split())
    graph[a-1][b-1] = graph[b-1][a-1] = True
    
visited = [False]*nmax
visited[0] = True
 
def dfs(v, n, visited): 
    all_visited = True
    for i in range(n):
        if visited[i] == False:
            all_visited = False
 
    if all_visited:
        return 1 
    
    ret = 0 
    
    for i in range(n):
        if graph[v][i] == False: 
            continue
        if visited[i]: 
            continue
        
        visited[i] = True 
        ret += dfs(i, n, visited) 
        visited[i] = False 
        
    return ret
  
print(dfs(0, n, visited))

Solution (Python):
import itertools

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

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

ans = 0

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

print(ans)

Solution (Python):
import itertools

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

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

ans = 0

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

print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(10 ** 6)
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())
  a-=1; b-=1
  g[a].append(b)
  g[b].append(a)

def dfs(x,visited):
  global ans
  
  for p in g[x]:
    if visited[p]==0:
      visited[p]=1
      if visited.count(1)==n:
        ans+=1
        
      else: 
        dfs(p,visited)
      visited[p]=0
v=[0]*n
v[0]=1
dfs(0,v)
print(ans)

Solution (Python):
from collections import defaultdict
from itertools import permutations
N, M = map(int, input().split())
dic = defaultdict(list)
for i in range(M):
  a, b = map(int, input().split())
  dic[a-1] += [b-1]
  dic[b-1] += [a-1]

ans = 0
ls = permutations(range(1,N))
for l in ls:
  l = [0]+list(l)
  for i in range(N-1):
    if not l[i+1] in dic[l[i]]:
      break
    if i==N-2:
      ans += 1
print(ans)

Solution (Python):
N,M=map(int,input().split())
A=[list(map(int,input().split())) for _ in range(M)]
D=[[]for i in range(N)]
for u,v in A:
  D[u-1].append(v-1)
  D[v-1].append(u-1)

def dfs(x,used):
  if len(used)==N:
    return 1
  ans=0
  for i in D[x]:
    if i not in used:
      ans+=dfs(i,used+[i])
  return ans
print(dfs(0,[0]))

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

def dfs(i, used):
    if len(used) == N:
        return 1
    ans = 0
    for j in edges[i]:
        if j not in used:
            ans += dfs(j, used+[j])
    return ans
print(dfs(0, [0]))

Solution (Python):
import itertools

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

count = 0
for path in itertools.permutations([i for i in range(2, N+1)], N-1):
  flag = True
  if [1, path[0]] in ab or [path[0], 1] in ab:
    pass
  else:
    flag = False
    continue
  for i in range(1, N):
    if flag:
      if i == N-1:
        count += 1
        continue
      if [path[i-1], path[i]] in ab or [path[i], path[i-1]] in ab:
        continue
      else:
        flag = False
print(count)

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

sum_n = sum([i for i in range(n + 1)])

all_route = []
def dfs(i, r, o):
  route = r
  o_v = o
  route.append(i)
  o_v.append(i)
  v_num = [v[1] for v in a if v[0] == i and v[1] not in o_v]
  v_num += [v[0] for v in a if v[1] == i and v[0] not in o_v]
  if len(v_num) == 0:
    all_route.append(route[:])
    
  else:
    for v in v_num:
      dfs(v, route[:],o_v[:])    

dfs(1, [], [])
all_route_scores = [sum(route) for route in all_route]
r = all_route_scores.count(sum_n)

print(r)

Solution (Python):
import itertools


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

ans = 0
node = list(range(1, N+1))
for x in itertools.permutations(node):
    if x[0] == 1:
        for i in range(N-1):
            if not edge[x[i]][x[i+1]]:
                break
        else:
            ans += 1

print(ans)

Solution (Python):


import math,itertools,fractions,heapq,bisect,sys,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

nmax=8
graph=[[False]*nmax for _ in range(nmax)]

def dfs(n,v,visited):
  all_visited=True
  for i in range(n):
    if visited[i]==False:
      all_visited=False
  if all_visited:
    return 1

  ret=0
  for i in range(n):
    if visited[i]:
      continue
    if graph[i][v]==False:
      continue
    visited[i]=True
    ret+=dfs(n,i,visited)
    visited[i]=False

  return ret

def main():
  n,m=LI()
  for _ in range(m):
    a,b=LI()
    a-=1
    b-=1
    graph[a][b]=True
    graph[b][a]=True

  visited=[False]*n
  visited[0]=True
  return dfs(n,0,visited)


print(main())

Solution (Python):
import math
import fractions
import bisect
import collections
import itertools
import heapq
import string
import sys
import copy
from collections import deque
sys.setrecursionlimit(10**7)
MOD = 10**9+7
def gcd(a,b):return fractions.gcd(a,b) 
def lcm(a,b):return (a*b) // fractions.gcd(a,b) 
def iin(): return int(input()) 
def ifn(): return float(input()) 
def isn(): return input().split() 
def imn(): return map(int, input().split()) 
def fmn(): return map(float, input().split()) 
def iln(): return list(map(int, input().split())) 
def iln_s(): return sorted(iln()) 
def iln_r(): return sorted(iln(), reverse=True) 
def fln(): return list(map(float, input().split())) 
def join(l, s=''): return s.join(l) 
def perm(l, n): return itertools.permutations(l, n) 
def perm_count(n, r): return math.factorial(n) // math.factorial(n-r) 
def comb(l, n): return itertools.combinations(l, n) 
def comb_count(n, r): return math.factorial(n) // (math.factorial(n-r) * math.factorial(r)) 
def two_distance(a, b, c, d): return ((c-a)**2 + (d-b)**2)**.5 
def m_add(a,b): return (a+b) % MOD

N,M = imn()

graph = [[False for _ in range(N)] for _ in range(N)]
for i in range(M):
    A,B = map(lambda x:int(x)-1, input().split())
    graph[A][B] = True
    graph[B][A] = True

def dfs(v, visited):

    all_visited=True

    for i in range(N):
        if not visited[i]: all_visited=False
    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, copy.deepcopy(visited))
        visited[i] = False

    return ret

visited = [False for _ in range(N)]
visited[0] = True

print(dfs(0, visited))

Solution (Python):
from collections import defaultdict, deque
import sys, heapq, bisect, math, itertools, string, queue, copy, time
from fractions import gcd
import numpy as np
sys.setrecursionlimit(10**8)
INF = float('inf')
MOD = 10**9+7
EPS = 10**-7
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())


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

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


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

print(ans)

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

edges = [[] for _ in range(n)]
for _ in range(m):
    a, b = map(int, input().split())
    edges[a - 1].append(b - 1)
    edges[b - 1].append(a - 1)
cnt = 0
for path in itertools.permutations(range(1, n)):
    
    path = [0] + list(path)
    flg = True
    for i in range(1, n):
        if path[i] not in edges[path[i-1]]:
            flg = False
            break
    if flg:
        cnt += 1

print(cnt)

Solution (Python):
from itertools import permutations
n,m = map(int, input().split())
d = {}
for _ in range(m):
    a,b = map(int, input().split())
    a -= 1
    b -= 1
    if a not in d:
        d[a] = {}
    if b not in d:
        d[b] = {}
    d[a][b] = d[b][a] = 1

ans = 0
for route in permutations(range(1,n)):
    if route[0] not in d[0]:
        continue
    for j in range(n-2):
        if route[j+1] not in d[route[j]]:
            break
    else:
        ans += 1

print(ans)