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

Solution (Python):
import itertools
N, M = map(int, input().split())
edge = [[False]*N for _ in range(N)]
ans = 0
for _ in range(M):
  a, b = map(int, input().split())
  a -= 1
  b -= 1
  edge[a][b] = True
  edge[b][a] = True
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 edge[i[j]][i[j+1]]:
        break
print(ans)

Solution (Python):
visited, g = ([], [])

def dfs(i):
    visited[i] = True
    ans = 0
    if all(visited):
        visited[i] = False
        return 1
    for j, b in enumerate(g[i]):
        if b and not visited[j]:
            ans += dfs(j)
    visited[i] = False
    return ans


def main():
    global visited, g
    n, m = [int(i) for i in input().split()]
    visited = [False for i in range(n)]
    g = [[False for i in range(n)] for j in range(n)]
    for i in range(m):
        t, f = [int(j)-1 for j in input().split()]
        g[t][f] = True
        g[f][t] = True
    print(dfs(0))


if __name__ == '__main__':
    main()

Solution (Python):
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    n,m=map(int,input().split())
    E=[[] for _ in range(n)]
    for _ in range(m):
        a,b=map(lambda x:int(x)-1,input().split())
        E[a].append(b)
        E[b].append(a)
    def dfs(v,vis):
        vis[v]=1
        if all(vis): return 1
        res=0
        for u in E[v]:
            if vis[u]==0:
                nvis=vis[:]
                res+=dfs(u,nvis)
        return res
    print(dfs(0,[0]*n))
resolve()

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

s = [1]
count = 0
L = [[i for i in edgelist if (len(i&set([1]))!=0)]]
while s != []:
    if len(s) == N:
        count = count + 1
        L.pop()
        s.pop()
    elif L[-1] == []:
        L.pop()
        s.pop()
    else:
        p = L[-1].pop()
        r = list(p - set([s[-1]]))
        L.append([i for i in edgelist if (len(i&set(r))!=0)*(len(i&set(s))==0)])
        s.append(r[0])
print(count)

Solution (Python):

from itertools import permutations as perm


def main():
    N, M, *A = map(int, open(0).read().split())
    E = {(i, j) for i, j in zip(A[::2], A[1::2])}
    ans = 0
    for path in perm(range(2, N + 1), N - 1):  
        path = (1,) + path
        if all((i, j) in E or (j, i) in E for i, j in zip(path, path[1:])):
            ans += 1
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):

from itertools import permutations as perm


def main():
    N, M, *A = map(int, open(0).read().split())
    E = {(i, j) for i, j in zip(A[::2], A[1::2])}
    E |= {(j, i) for i, j in zip(A[::2], A[1::2])}  
    ans = 0
    for path in perm(range(2, N + 1), N - 1):  
        path = (1,) + path
        if all((i, j) in E for i, j in zip(path, path[1:])):
            ans += 1
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):




from itertools import permutations as perm


def main():
    N, M = tuple(map(int, input().split()))
    E = set(tuple(map(int, input().split())) for _ in range(M))  
    E |= {(j, i) for i, j in E}  
    ans = 0
    for path in perm(range(2, N + 1), N - 1):  
        path = (1,) + path
        if all((i, j) in E for i, j in zip(path, path[1:])):
            ans += 1
    print(ans)


if __name__ == "__main__":
    main()

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

import itertools

M = [[0] * (n+1) for i in range(n+1)]
for i in range(m):
    M[A[i][0]][A[i][1]] = 1
    M[A[i][1]][A[i][0]] = 1

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



ans = 0
for i in range(len(B)):
    pt = 0
    if M[1][B[i][0]] == 1:
        pt += 1
    else:
        continue

    for j in range(len(B[i])-1):
        if M[B[i][j]][B[i][j+1]] == 1:
            pt += 1
    
    if pt == n-1:
        ans += 1
print(ans)

Solution (Python):
import itertools

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

answer = 0
for i in itertools.permutations(range(2, N+1), N-1):
    l = [1] + list(i)
    answer += sum(1 for x in zip(l, l[1:]) if tuple(sorted(x)) in edges) == N-1
print(answer)

Solution (Python):
from itertools import permutations

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

count = 0
for p in permutations(range(1, N)):
    s = 0
    for i in p:
        if G[s][i] == 0:
            break
        else:
            s = i
    else:
        count += 1

print(count)

Solution (Python):
from itertools import permutations
n,m = map(int,input().split())
e = [tuple(sorted(map(int,input().split()))) for _ in range(m)]

ans = 0
for i in permutations(range(2, n+1), n-1):
  l = [1] + list(i)
  ans += sum(1 for j in zip(l, l[1:]) if tuple(sorted(j)) in e) == n-1

print(ans)

Solution (Python):
import copy

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

def search(s, V):
    ans = 0
    if s in V:
        return 0
    Vc = copy.copy(V)
    Vc.add(s)
    if Vc == set(list(range(1, N+1))):
        return 1
    for v in T[s]:
        ans += search(v, Vc)
    return ans

print(search(1, set()))

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(i, visited):
    if all(visited):
        return 1
    total = 0
    for j in graph[i]:
        if not visited[j]:
            nvisited = visited[:]
            nvisited[j] = True
            total += dfs(j, nvisited)
    return total

def main():
    """ main """
    visited = [False] * N
    visited[0] = True
    print(dfs(0, visited))

if __name__ == '__main__':
    main()

Solution (Python):
import itertools

N, M = map(int, input().split())
edges = {tuple(sorted(map(int, input().split()))) for _ in range(M)}

answer = 0
for i in itertools.permutations(range(2, N+1), N-1):
    l = [1] + list(i)
    answer += sum(1 for edge in zip(l, l[1:]) if tuple(sorted(edge)) in edges) == N-1
print(answer)

Solution (Python):
from itertools import permutations

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

E = []
for i in range(M):
    E.append(tuple(map(int, input().split())))

P = []
for p in permutations(range(2, N+1)):
    tmp = [1]
    tmp.extend(list(p))
    P.append(tmp)

ans = 0
for p in P:
    for i in range(1, N):
        exist = False
        for e in E:
            if set(e) == {p[i-1], p[i]}:
                exist = True
                break
        if exist is False:
            break
    else:
        if exist is False:
            break
    if exist:
        ans += 1

print(ans)

Solution (Python):
from itertools import permutations
n,m=map(int,input().split())
con=[[0]*n for _ in range(n)]
for _ in range(m):
	a,b=map(int,input().split())
	con[a-1][b-1]=con[b-1][a-1]=1
ans=0
for p in permutations(range(n)):
	if p[0]!=0:
		continue
	if all(con[x][y] for x,y in zip(p,p[1:])):
		ans+=1
print(ans)

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

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

    for i in range(M):
        a, b = map(int, input().split())
        link[a-1][b-1] = True
        link[b-1][a-1] = True
    
    ans = 0
    path = [i for i in range(1, N)]
    for p in permutations(path):
        if link[0][p[0]]:
            ok = True
            for i in range(N-2):
                if not link[p[i]][p[i+1]]:
                    ok = False
                    break
            if ok:
                ans += 1
    print(ans)

if __name__ == "__main__":
    main()

Solution (Python):
import itertools

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

ans = 0
for r in itertools.permutations(range(2,N+1)):
    Rlist = list(r)
    a = 1
    b = Rlist[0]
    if Data[a][b] == 0:
        continue
    else:
        flag = True 
        for i in range(len(Rlist)-1):
            a = Rlist[i]
            b = Rlist[i+1]
            if Data[a][b] == 0:
                flag = False
                break
        if flag:
            ans += 1

print(ans)

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




INF = float('inf')
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


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



cnt = 0

for l in list(permutations(range(n), n)):
    if l[0]:
        continue
    for i in range(n-1):
        if not l[i+1] in graph[l[i]]:
            break
    else:
        cnt += 1



print(cnt)

Solution (Python):
import sys
from bisect import *
from collections import *
from copy import deepcopy
from heapq import *
from itertools import *
from math import *
from operator import *
from pprint import *

sys.setrecursionlimit(10**8)

input = sys.stdin.readline

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(i, visited):
    if all(visited):
        return 1
    total = 0
    for ni in graph[i]:
        if not visited[ni]:
            nvisited = visited[:]
            nvisited[ni] = True
            total += dfs(ni,nvisited)
    return total


def main():
    """ main """
    visited = [False]*N
    visited[0] = True
    print(dfs(0, visited))

if __name__ == '__main__':
    main()

Solution (Python):
def tami(x, vis, cnt):
  global ans
  if cnt == N:
    ans += 1
    
    return
  for i in root[x]:
    if i not in vis:
      tami(i, vis+[i], cnt+1)

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

root = [[] for _ in range(N+2)]
for a,b in ab:
  root[a].append(b)
  root[b].append(a)

visited = []
ans = 0
tami(1, visited+[1], 1)
print(ans)

Solution (Python):
N,M=map(int,input().split());L=[[]for _ in range(N+1)]
for _ in range(M):a,b=map(int,input().split());L[a]+=[b];L[b]+=[a]
def s(n,v):
 if n in v:return 0
 if len(v)==N-1:return 1
 return sum(s(i,v|{n})for i in L[n])
print(s(1,set()))

Solution (Python):
import itertools
n,m=map(int,input().split())
graph=[[False for h in range(n)] for i in range(n)]
for i in range(m):
    a,b=map(int,input().split())
    a-=1;b-=1
    graph[a][b]=True
    graph[b][a]=True
l=[i for i in range(1,n)]
ans=0
if n==2:
    print(m)
    exit()
for v in itertools.permutations(l):
    flag=1
    if graph[0][v[0]]==False:continue
    else:
        c=v[0]
        for j in v[1:]:
            if graph[c][j]==False:
                flag=0
                break
            c=j
        ans+=flag
print(ans)

Solution (Python):
import sys
from pprint import pprint

import itertools

n, m = map(int, sys.stdin.readline().strip().split(" "))

edges = set()
for _ in range(m):
    a, b = map(int, sys.stdin.readline().strip().split(" "))
    edges.add((a, b))
    edges.add((b, a))

ans = 0
for seq in itertools.permutations([i for i in range(1,n+1)]):
    
    flag = True
    for i in range(n-1):
        
        if i == 0 and seq[i] != 1:
            
            flag = False
            break
        if (seq[i], seq[i+1]) not in edges:
            
            flag = False
            break
    if flag:
        ans += 1

print(ans)

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


ans=0
q=[]
s=1

def func(s,Q,r):
    global ans
    for q ,P in Q:
        if r==N-1:
            ans+=1
        n_s=[i for i in q if i!=s][0]
        n_q=[]
        for p in P:
            if n_s in p:
                n_q.append([p, [_p for _p in P if n_s not in _p]])
        if len(n_q)==0:
            continue
        else:
            func(n_s, n_q, r+1)


for p in P:
    if s in p:
        q.append([p, [_p for _p in P if s not in _p]])
func(s,q,1)
print(ans)

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

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

def dfs(visited, now):
    tv = copy.copy(visited)
    tv[now-1] = 1
    if all(tv) == 1:
        return 1

    count = 0
    for i in graph[now]:
        if tv[i-1] == 0:
            count += dfs(tv, i)
    return count

print(dfs([0] * n, 1))

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

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

print(a)

Solution (Python):
import itertools
import collections

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

a = [list(sorted(map(int, input().split()))) for i in range(m)]
a.sort()

cnt = 0


for i in itertools.permutations(range(2, n + 1), (n - 1)):
    li = [1] + list(i)
    
    if sum(list(sorted(edge)) in a for edge in zip(li, li[1:])) == n - 1:
        cnt += 1

print(cnt)

Solution (Python):
import itertools

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
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):
from itertools import permutations
from copy import deepcopy

N,M = [int(i) for i in input().split()]
links  = set([input().strip() for _ in range(M)])

ans = 0

for path in permutations(range(2,N+1)):
    l = deepcopy(links)
    p_node = 1
    for n_node in path:
        e_l = " ".join([str(s) for s in sorted([p_node,n_node])])
        if e_l in l:
            l.remove(e_l)
            p_node = n_node
            continue
        else:
            break
    else:
        ans += 1 

print(ans)

Solution (Python):
from itertools import permutations
from copy import deepcopy

N,M = [int(i) for i in input().split()]
links  = [[int(i) for i in input().split()] for _ in range(M)]

ans = 0

for path in permutations(range(2,N+1)):
    l = deepcopy(links)
    p_node = 1
    for n_node in path:
        if sorted([p_node,n_node]) in l:
            l.pop(l.index(sorted([p_node,n_node])))
            p_node = n_node
            continue
        else:
            break
    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 itertools
N,M=map(int,input().split())
edges={tuple(sorted(map(int,input().split()))) for i in range(M)}
ans=0

for i in itertools.permutations(range(2,N+1)):
    l= [1]+ list(i)
    counte = 0
    for edge in zip(l,l[1:]):
        if tuple(sorted(edge)) in edges:
            counte += 1
    if counte == N-1:
        ans+=1

print(ans)

Solution (Python):
import itertools
N,M=map(int,input().split())
edges={tuple(sorted(map(int,input().split()))) for i in range(M)}
ans=0
for i in itertools.permutations(range(2,N+1),N-1):
    l=[1]+list(i)
    ans+=sum(1 for edge in zip(l,l[1:]) if tuple(sorted(edge)) in edges)==N-1
print(ans)

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

dic = {}
for i in range(1, n+1):
  dic[i] = []
for i in range(m):
  a1, a2 = map(int, input().split())
  dic[a1] += [a2]
  dic[a2] += [a1]

def next_position(position, history, dic):
  next_you_can_move = list(set(dic[position]) - set(history))
  return next_you_can_move

def serch(position, history, dic):
  counter = 0
  if len(history) == n:
    return 1
  else:
    next_you_can_move = next_position(position, history, dic)
    if next_you_can_move == []:
      return 0
    for cand in next_you_can_move:
      new_history = history + [cand]
      counter += serch(cand, new_history, dic)
    return counter
count = serch(1, [1], dic)
print(count)

Solution (Python):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

N, M = map(int, input().split())
tLst = [[] for _ in range(N)]
vLst = [0] * N

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

def dfs(n, index, v, ans):
    vLst[index] = 1
    if n == N - 1:
        ans += 1
        return ans
    for i in tLst[index]:
        if v == i:
            continue
        elif vLst[i] == 1:
            continue
        ans = dfs(n + 1, i, index, ans)
        vLst[i] = 0
    return ans
print(dfs(0, 0, 0, 0))

Solution (Python):
from collections import deque

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

q = deque()
q.append((0, set(), -1))
ans = 0
while len(q):
    a, s, p = q.pop()
    s.add(a)
    if len(s) == N:
        ans += 1
        continue
    for b in to[a]:
        if b not in s:
            q.append((b, s | {b}, a))
print(ans)

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

from itertools import permutations

cnt=0
for i in permutations(range(1,n)):
    i=(0,)+i
    for j in range(n-1):
        if i[j+1] not in g[i[j]]:
            break
    else:
        cnt+=1
print(cnt)

Solution (Python):
N, M = map(int,input().split(" "))
nm = [[0 for i in range(N)] for j in range(N)]
for i in range(M):
  x,y = (map(int,input().split(" ")))
  nm[x-1][y-1]=1
  nm[y-1][x-1]=1

cnt = [0]
def dfs(V, s):
  V[s]=1
  if sum(V)==N:
    cnt[0] += 1
  for i in range(N):
    if nm[i][s]==1 and V[i]==0:
      dfs(V,i)
  V[s]=0
  
dfs([0]*N,0)
print(cnt[0])

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

for _ in range(n):
    conn.append([False]*n)

visited = [False] * n

v = []

for _ in range(m):
    line = map(int, input().split())
    v.append([x-1 for x in line])

for start, end in v:
    conn[start][end] = conn[end][start] = True

def dfs(now, depth):
    if visited[now] : return 0
    if depth == n - 1: return 1

    visited[now] = True
    ret = 0

    for i in range(n):
        if conn[now][i]: ret += dfs(i, depth+1)

    visited[now] = False
    return ret

print(dfs(0, 0))

Solution (Python):
import itertools
N,M=map(int,input().split())
l=list(itertools.permutations(range(N-1)))
h=[set(map(int, input().split())) for i in range(M)]
a=0
for i in range(len(l)):
    for k in range(M):
        if {1,l[i][0]+2}==h[k]:
            break
    else:
        continue
    for j in range(1,N-1):
        for k in range(M):
            if {l[i][j-1]+2,l[i][j]+2}==h[k]:
                break
        else:
            break
    else:
        a+=1
print(a)

Solution (Python):
import itertools
N, M = map(int, input().split())
edges = {tuple(sorted(map(int, input().split()))) for _ in range(M)}
answer = 0
for pattern in itertools.permutations(range(2, N+1), N-1):
    l = [1] + list(pattern)
    answer += sum(1 for edge in zip(l, l[1:]) if tuple(sorted(edge)) in edges)==N-1
print(answer)

Solution (Python):
import sys
import copy
import string
import  math
from _bisect import *
from collections import *
from operator import itemgetter
from math import factorial
"""
from fractions import gcd
def lcm(x, y):
    return (x * y) // gcd(x, y)
"""
stdin = sys.stdin
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline()

def dfs(v):
    flag = True
    for i in range(n):
        if not visit[i]:
            flag = False
    if flag:
        return 1

    ret = 0

    for i in range(n):
        if not g[v][i]:
            continue
        if visit[i]:
            continue

        visit[i] = True
        ret += dfs(i)
        visit[i] = False

    return ret


    for next in g[v]:
        if visit[next]:
            continue
        else:
            visit[next] = True
            dfs(next)


n, m = na()
g = [[0] * n for _ in range(n)]
for i in range(m):
    a, b = na()
    a -= 1
    b -= 1
    g[a][b] = g[b][a] = True

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

Solution (Python):
N,M=map(int,input().split())
L=[[] for _ in range(N)]
visited=[True]+[False]*(N-1)
for _ in range(M):
    a,b=map(int,input().split())
    L[a-1].append(b-1)
    L[b-1].append(a-1)
def dfs(now,cnt):
    ans=0
    if cnt==N:
        return 1
    for nxt in L[now]:
        if visited[nxt]:
            continue
        visited[nxt]=True
        ans+=dfs(nxt,cnt+1)
        visited[nxt]=False
    return ans
print(dfs(0,1))

Solution (Python):
import itertools
N,M=map(int,input().split())
L=[[] for _ in range(N)]
for _ in range(M):
    a,b=map(int,input().split())
    L[a-1].append(b-1)
    L[b-1].append(a-1)
cnt=0
for i in itertools.permutations(range(N),N):
    if i[0]==0:
        for j in range(N):
            if j==N-1:
                cnt+=1
                break
            if not (i[j+1] in L[i[j]]):
                break
print(cnt)

Solution (Python):
n,m = map(int,input().split())
e = [[False]*n for _ in range(n)]
visited = [False]*n
for _ in range(m):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    e[a][b] = True
    e[b][a] = True

def traverse(t,d):
    
    visited[t] = True

    ans = 0
    is_end = True

    for i in range(n):
        if e[t][i] and not visited[i]:
            is_end = False
            ans += traverse(i, d+1)


    visited[t] = False
    if is_end:
        if d != n-1:
            return 0
        else:
            return 1
    
    return ans

print(traverse(0, 0))

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

Map = [[] for _ in range(N)]
reached = [False]*N

for _ in range(M):
    aa, bb = map(int, input().split())
    Map[aa-1].append(bb-1)
    Map[bb-1].append(aa-1)

cnt = 0

def DFS(x):
    global cnt
    global reached

    reached[x] = True

    if all(reached):
        cnt += 1
        reached[x] = False

        return

    for i in Map[x]:
        if reached[i]:
            continue

        else:
            DFS(i)

    reached[x] = False


DFS(0)
print(cnt)

Solution (Python):
import sys
sys.setrecursionlimit(10000000)
import copy

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

ans = 0

def dfs(visited, now):
    tv = copy.copy(visited)
    tv[now-1] = True
    
    if all(tv):
        return 1

    temp = 0
    for i in graph[now]:
        if tv[i-1] != 1:
            temp += dfs(tv, i)
    return temp

ans = dfs([False] * n, 1)
print(ans)

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

used = [0 for i in range(n)]
ans = 0

def dfs(now, prev):
    global ans

    if sum(used) == n:
        
        ans += 1

    for i in link[now]:
        
        if i != now and used[i] == 0:
            used[i] = 1
            
            dfs(i, now)
            
            used[i] = 0
            

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

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

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



visited = [0] * n

def dfs(current, prev):

    if sum(visited) == n:
        return 1

    res = 0

    for next in edge[current]:
        if next != prev and visited[next] == 0:
            visited[next] = 1
            res += dfs(next, current)
            visited[next] = 0
    
    return res

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

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

visited = [0]*n
ans = 0

def dfs(now, prev):
    global ans

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

    for i in link[now]:
        if i != now and visited[i] == 0:
            visited[i] = 1
            dfs(i, now)
            visited[i] = 0

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

Solution (Python):
n, m = map(int, input().split())
g = [[] for i in range(n)]
for i in range(m):
    u,v = map(int, input().split())
    g[u-1].append(v-1)
    g[v-1].append(u-1)

visited = [0] * n

def dfs(now, pre):
    if sum(visited) == n:
        return 1
    
    res = 0
    
    for i in g[now]:
        if i != pre and visited[i] == 0:
            visited[i] = 1
            res = res + dfs(i, now)
            visited[i] = 0
    
    return res

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

Solution (Python):
from collections import defaultdict, deque

def dfs(graph, start_node):
  queue = deque()
  queue.append([start_node,1,[0]])
  ans = 0
  while len(queue) > 0:
    prv_node, node_num, done = queue.pop()
    for node in graph[prv_node]:
      if node not in done:
        if node_num+1 == N:ans += 1
        else:queue.append([node,node_num+1,done+[node]]) 
  return ans

N,M=map(int,input().split())
graph = defaultdict(list)

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

Solution (Python):
import copy

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



def dfs(flg, E, i):
	q = []
	for e in E:
		if e[0] == i:
			if flg[e[1]-1] == 0:
				q.append(e[1])
		if e[1] == i:
			if flg[e[0]-1] == 0:
				q.append(e[0])
	if len(q) == 0:
		if flg.count(0) == 0:
			return 1
		else:
			return 0

	ans = 0
	for n in q:
		temp = copy.deepcopy(flg)
		temp[n-1] = 1
		ans += dfs(temp, E, n)

	return ans

flg = [0 for _ in range(N)]
flg[0] = 1
print(dfs(flg, E, 1))

Solution (Python):
import sys
import itertools

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

nextList = [set() for _ in range(n+1)]
for _ in range(m):
    a, b = map(int, sys.stdin.readline().split())
    nextList[a].add(b)
    nextList[b].add(a)

count = 0

nodes = range(2, n+1)
for v in itertools.permutations(nodes, n-1):
    now = 1
    error = False
    for i in v:
        if not i in nextList[now]:
            error = True
            break
        now = i
    if error != True:
        count += 1

print(count)

Solution (Python):
import itertools
N,M=map(int,input().split())
edges={tuple(sorted(map(int,input().split()))) for i in range(M)}
ans=0
for i in itertools.permutations(range(2,N+1),N-1):
    l=[1]+list(i)
    ans+=sum(1 for edge in zip(l,l[1:]) if tuple(sorted(edge)) in edges)==N-1
print(ans)

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

visited = [0] * n
def dfs(v, p):
    if sum(visited) == n:
        return 1
    res = 0
    for u in edge[v]:
        if u != p and visited[u] == 0:
            visited[u] = 1
            res += dfs(u, v)
            visited[u] = 0
    return res

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

print(ans)

Solution (Python):
N, M = [int(x) for x in input().split()]
P = [[False] * N for m in range(N)]
dict={}
for m in range(M):
  a, b = [int(x) for x in input().split()]
  P[a-1][b-1] = True
  P[b-1][a-1] = True

def dp(x, past):
  past[x] = True
  if (x, tuple(past)) in dict:
    return dict[(x, tuple(past))]
  if False not in past:
    return 1
  ret = 0
  for i,p in enumerate(P[x]):
    if not p or x == i or past[i]:
      continue
    else:
      ret += dp(i, past[:])
  dict[(x, tuple(past))] = ret
  return ret

if M < N - 1:
  print(0)
else:
  print(dp(0, [False] * N))