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 getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
from heapq import heapify, heappop, heappush
import math
import random
import string
from copy import deepcopy
from itertools import combinations, permutations, product
from operator import mul, itemgetter
from functools import reduce
from bisect import bisect_left, bisect_right

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





"""
全ての場所を一度だけ通り巡回する通りの数
bit(1 << N)を小さい順から探索する
①bit & (1 << 0)
最初に0を踏んでないということだから飛ばす
②現在の場所sを探すためN個探索する
③次の場所tを探すためN個探索する
④渡すdpする
"""

N, M = getNM()
G = [[0] * N for i in range(N)]
for i in range(M):
    a, b = getNM()
    G[a - 1][b - 1] = 1 
    G[b - 1][a - 1] = 1




def counter(sta):
    
    dp = [[0] * N for i in range(1 << N)]
    dp[1 << sta][sta] = 1

    for bit in range(1, 1 << N):
        if not bit & (1 << sta):
            continue
        
        for s in range(N):
            
            if not bit & (1 << s):
                continue
            
            for t in range(N):
                
                if (bit & (1 << t)) == 0 and G[s][t]:
                    dp[bit|(1 << t)][t] += dp[bit][s]

    return sum(dp[(1 << N) - 1])

print(counter(0))

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

path = [[0]*(N+1) for _ in range(N+1)]

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

visited = [0]*(N+1)

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

print(dfs(1,1))

Solution (Python):



import itertools

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

graph= [[False]*N for i 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

lst = [i-1 for i in range(N)]
cnt = 0

for v in itertools.permutations(lst, N):
    if v[0] != 0:
        continue
    for i in range(N-1):
        if graph[v[i]][v[i+1]] == False:
            break
        if i == N-2:
            cnt += 1

print(cnt)

Solution (Python):
import itertools

n,m=map(int,input().split())
emp=[[] for i in range(n)]
count=0

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

nlis=[i for i in range(n)]
perm=list(itertools.permutations(nlis))

for one_case in perm:
    if one_case[0]==0:
        cou=0
        for i in range(n-1):
            if one_case[i+1] in emp[one_case[i]]:
                cou+=1
            
            if cou==n-1:
                count+=1
print(count)

Solution (Python):
from itertools import permutations

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

for i in range(M):
  ab = list(map(int,input().split()))
  AB[i] = ab

count = 0
nums = [i for i in range(1,N+1)]
pers =permutations(nums,N)
for i in pers:
  if i[0] == 1:
    flag1 = 0
    for j in range(N-1):
      flag2 = False
      for k in range(M):
        if (i[j] == AB[k][0] and i[j+1] == AB[k][1]) or (i[j] == AB[k][1] and i[j+1] == AB[k][0]):
          flag2 = True
          
      if flag2:
        flag1 += 1
    if flag1 == N-1:
      
      count += 1
print(count)

Solution (Python):
import math
import itertools


def calc_digit_sum(num):
    digits = sums = 0
    while num > 0:
        digits += 1
        sums += num % 10
        num //= 10
    return digits, sums


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


answer = 0
routes = [c for c in itertools.permutations(range(0, n), n) if c[0] == 0]
for route in routes:
    seen = set()

    is_one_stroke = True
    for index in range(len(route) - 1):
        node = route[index]

        seen.add(node)
        next_node = route[index+1]
        if not graph[node] or next_node not in graph[node] or next_node in seen:
            is_one_stroke = False
            break

    if is_one_stroke:
        answer += 1

print(answer)

Solution (Python):
import itertools
N, M = map(int, input().split())
p=[[0]*N for i in range(N)]
for i in range(M):
    a,b=map(int,input().split())
    p[a-1][b-1]=1
    p[b-1][a-1]=1
cnt=0
a=[i for i in range(N)]

for i in itertools.permutations(a):
    flag=0
    if i[0]==0:
        for j in range(1,N):
            if p[i[j]][i[j-1]]!=1:
                flag=1
        if flag==0:
            cnt+=1
    
print(cnt)

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



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



def dfs(list):
    
  if len(list) == N:
    return 1
  else:
    a = list[-1]
    
    
    next = [n for n in edges[a] if n not in list]
    
    if len(next) == 0:
      return 0

    total = 0
    
    for n in next:
      total += dfs(list + [n])

    return total


ans = dfs([1])

print(ans)

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



edges = {i:[] for i in range(1,N+1)}
for i in range(M):
  a,b = [int(a) for a in input().split()]
  edges[a].append(b)
  edges[b].append(a)



def dfs(list):
    
  if len(list) == N:
    return 1
  else:
    a = list[-1]
    
    
    next = [n for n in edges[a] if n not in list]
    
    if len(next) == 0:
      return 0

    total = 0
    
    for n in next:
      total += dfs(list + [n])

    return total


ans = dfs([1])

print(ans)

Solution (Python):
N,M = [int(a) for a in input().split()]



edges = {i:[] for i in range(1,N+1)}
for i in range(M):
  a,b = [int(a) for a in input().split()]
  edges[a].append(b)
  edges[b].append(a)



def dfs(list):
    
  if len(list) == N:
    return 1
  else:
    a = list[-1]
    
    
    next = [n for n in edges[a] if n not in list]
    
    if len(next) == 0:
      return 0

    total = 0
    
    for n in next:
      total += dfs(list + [n])

    return total


ans = dfs([1])

print(ans)

Solution (Python):
N,M = [int(a) for a in input().split()]



edges = {i:[] for i in range(1,N+1)}
for i in range(M):
  a,b = [int(a) for a in input().split()]
  edges[a].append(b)
  edges[b].append(a)



def search(lst):
    
  if len(lst) == N:
    return 1
  else:
    a = lst[-1]
    
    
    next = [n for n in edges[a] if n not in lst]
    
    if len(next) == 0:
      return 0

    tot = 0
    
    for n in next:
      tot += search(lst + [n])

    return tot


ans = search([1])

print(ans)

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

def search(lst):
  if len(lst) == N:
    return 1
  else:
    a = lst[-1]
    next = [n for n in edges[a] if n not in lst]
    if len(next) == 0:
      return 0

    tot = 0
    for n in next:
      tot += search(lst + [n])
    
    return tot


ans = search([1])

print(ans)

Solution (Python):
import itertools
n,m=map(int,input().split())
tbl=[[0]*n for _ in range(n)]
for _ in range(m):
    a,b=map(int,input().split())
    tbl[a-1][b-1]=1
    tbl[b-1][a-1]=1
ans=0
l=[i+1 for i in range(n-1)]
for p in itertools.permutations(l,n-1):
    flag=True
    p=[0]+list(p)
    for i in range(n-1):
        if tbl[p[i]][p[i+1]]==0:
            flag=False
            break
    if flag:
      ans+=1
print(ans)

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

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


def dfs(v, seen):
    if seen == [1] * N:
        return 1
    
    res = 0
    for nv in to[v]:
        if not seen[nv]:
            seen[nv] = 1
            res += dfs(nv, seen)
            seen[nv] = 0
    return res


def main():
    seen = [0] * N
    seen[0] = 1
    print(dfs(0, seen))    


if __name__ == "__main__":
    main()

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

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


res = 0
def dfs(v, seen):
    global res
    if seen == [1] * N:
        res += 1
        return
    for nv in to[v]:
        if not seen[nv]:
            seen[nv] = 1
            dfs(nv, seen)
            seen[nv] = 0


def main():
    seen = [0] * N
    seen[0] = 1
    dfs(0, seen)
    print(res)


if __name__ == "__main__":
    main()

Solution (Python):
import copy
from collections import deque

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

e = [[] for i in range(n)]
for i in range(m):
    a, b = map(int,input().split())
    a -= 1
    b -= 1
    e[a].append(b)
    e[b].append(a)
visited = [False]*n
visited[0] = True
d = deque([[0, visited]])

cnt = 0
while d:
    f, visited = d.pop()
    for t in e[f]:
        v = copy.deepcopy(visited)
        if not v[t]:
            v[t] = True
            if False in v:
                d.append([t, v])
            else:
                cnt += 1
print(cnt)

Solution (Python):
import copy
from collections import deque

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

e = [[] for i in range(n)]
for i in range(m):
    a, b = map(int,input().split())
    a -= 1
    b -= 1
    e[a].append(b)
    e[b].append(a)
visited = [False]*n
visited[0] = True
d = deque([[0, visited]])

cnt = 0
while d:
    f, visited = d.pop()
    for t in e[f]:
        v = copy.deepcopy(visited)
        if not v[t]:
            v[t] = True
            if False in v:
                d.append([t, v])
            else:
                cnt += 1
print(cnt)

Solution (Python):
from itertools import permutations

n,m = map(int,input().split())
v = [set() for _ in range(n)]
for i in range(m):
    ai,bi = map(int,input().split())
    v[ai-1].add(bi-1)
    v[bi-1].add(ai-1)

ans = 0
for ci in permutations(range(n)):
    if not ci[0]:
        for i in range(n-1):
            if not (ci[i+1] in v[ci[i]]):
                break
        else:
            ans += 1
print(ans)

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 P in permutations(range(n),n):
  f=1
  if P[0]!=0:
    continue
  for i in range(n-1):
    if  P[i+1] in G[P[i]]:
      f*=1
    else:
      f*=0
  if f==1:
    ans+=1
print(ans)

Solution (Python):
from itertools import permutations

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

ans = 0
for r in permutations(range(N)):
    if r[0] != 0: break
    factor = 1
    for i in range(len(r)-1):
        factor *= root[r[i]][r[i+1]]
    ans += factor
print(ans)

Solution (Python):
from itertools import permutations
n,m=map(int,input().split())
lis=[i for i in range(1,n+1)]
nm=[[] for _ in range(n+1)]
for _ in range(m):
    a,b=map(int,input().split())
    nm[a].append(b)
    nm[b].append(a)
count=0
for i in permutations(lis):
    if i[0]==1:
        temp=nm[1]
        for j in range(n-1):
            if not i[j+1] in set(temp):
                break
            temp=nm[i[j+1]]
        else:
            count+=1
print(count)

Solution (Python):
from collections import defaultdict
from itertools import permutations
N,M=map(int,input().split())
mat = [[0]*(1+N) for _ in range(1+N)]
for _ in range(M):
    a,b = map(int,input().split())
    mat[a][b] = 1
    mat[b][a] = 1
ans = 0
for tpl in permutations(range(2, 1+N), N-1):
    is_ok = 1
    tpl = [1] + list(tpl)
    for i in range(N-1):
        if mat[tpl[i]][tpl[i+1]] == 0:
            is_ok = 0
            break
    
    if is_ok:
        ans += 1
print(ans)

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

N, M = map(int, input().split())
graph = [[] for _ in range(N)]
for i in range(M):
    a, b = map(lambda x: int(x) - 1, input().split())
    graph[a].append(b)
    graph[b].append(a)
def dfs(cur, visited):
    if visited == (1 << N) - 1:
        return 1
    res = 0
    for to in graph[cur]:
        if not visited & (1 << to):
            res += dfs(to, visited | (1 << to))
    return res
print(dfs(0, 1))

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

N, M = map(int, input().split())
graph = [[] for _ in range(N)]
for i in range(M):
    a, b = map(lambda x: int(x) - 1, input().split())
    graph[a].append(b)
    graph[b].append(a)
def dfs(cur, visited):
    if visited == (1 << N) - 1:
        return 1
    res = 0
    for to in graph[cur]:
        if not (visited >> to) & 1:
            res += dfs(to, visited | (1 << to))
    return res
print(dfs(0, 1))

Solution (Python):
import itertools

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


a_list = []
for j in range(m) :
    a = list(map(int, input().split()))
    a_list.append(a)
a_list.sort()


b_list = [k for k in itertools.permutations([l for l in range(1, n + 1)]) if k[0] == 1]


cnt = 0
for x in b_list :
    tf_list = []
    for y in range(n - 1) :
        tf_list.append([x[y], x[y + 1]] in a_list or [x[y + 1], x[y]] in a_list)
    
    if all(tf_list) == True :
        cnt += 1

print(cnt)

Solution (Python):
from typing import List, Tuple


def main():
    n, m = map(int, input().split())
    g = []
    for _ in range(m):
        a, b = map(int, input().split())
        g.append((a, b))
    print(osp(n, g))


def osp(n: int, g: List[Tuple[int, int]]) -> int:
    v = [False] * n
    g = set(g)

    return dfs(0, v, n, g)


def dfs(i, v, n, g):
    v[i] = True
    if all(v):
        v[i] = False
        return 1

    cnt = 0
    for j in range(n):
        if v[j]:
            continue
        if not ((i + 1, j + 1) in g or (j + 1, i + 1) in g):
            continue
        cnt += dfs(j, v, n, g)

    v[i] = False
    return cnt


if __name__ == '__main__':
    main()

Solution (Python):
from typing import List, Tuple


def main():
    n, m = map(int, input().split())
    g = []
    for _ in range(m):
        a, b = map(int, input().split())
        g.append((a, b))
    print(osp(n, g))


def osp(n: int, g: List[Tuple[int, int]]) -> int:
    v = [False] * n

    return dfs(0, v, n, g)


def dfs(i, v, n, g):
    v[i] = True
    if all(v):
        v[i] = False
        return 1

    cnt = 0
    for j in range(n):
        if v[j]:
            continue
        if not ((i + 1, j + 1) in g or (j + 1, i + 1) in g):
            continue
        cnt += dfs(j, v, n, g)

    v[i] = False
    return cnt


if __name__ == '__main__':
    main()

Solution (Python):
from typing import List, Tuple


def main():
    n, m = map(int, input().split())
    g = []
    for _ in range(m):
        a, b = map(int, input().split())
        g.append((a, b))
    print(osp(n, g))


def osp(n: int, g: List[Tuple[int, int]]) -> int:
    graph = [[False] * n for _ in range(n)]
    for a, b in g:
        graph[a - 1][b - 1] = True
        graph[b - 1][a - 1] = True
    v = [False] * n

    return dfs(0, v, n, graph)


def dfs(i, v, n, graph):
    v[i] = True
    if all(v):
        v[i] = False
        return 1

    cnt = 0
    for j in range(n):
        if v[j]:
            continue
        if not graph[i][j]:
            continue
        cnt += dfs(j, v, n, graph)

    v[i] = False
    return cnt


if __name__ == '__main__':
    main()

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

Graph = [[] for _ in range(N)]
for a,b in Edge:
    Graph[a-1].append(b-1)
    Graph[b-1].append(a-1)

seen = set()
def dfs(v):
    seen.add(v)
    if len(seen) == N:
        seen.remove(v)
        return 1
    Res = [dfs(nv) for nv in Graph[v] if not nv in seen]
    seen.remove(v)
    return sum(Res)

print(dfs(0))

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

Graph = [[] for _ in range(N)]
for a,b in Edge:
    Graph[a-1].append(b-1)
    Graph[b-1].append(a-1)

seen = set()
def dfs(v):
    global Graph, seen
    seen.add(v)
    if len(seen) == N:
        seen.remove(v)
        return 1
    Res = [dfs(nv) for nv in Graph[v] if not nv in seen]
    seen.remove(v)
    return sum(Res)

print(dfs(0))

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

Graph = [[] for _ in range(N)]
for a,b in Edge:
    Graph[a-1].append(b-1)
    Graph[b-1].append(a-1)


def dfs(v, seen):
    global Graph
    seen.add(v)
    if len(seen) == N:
        seen.remove(v)
        return 1
    Res = [dfs(nv, seen) for nv in Graph[v] if not nv in seen]
    seen.remove(v)
    return sum(Res)

print(dfs(0, set()))

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

for i in range(M):
    x,y=map(int,input().split())
    A[x-1].append(y)
    A[y-1].append(x)

color=["W" for i in range(N)]

clear=["B" for i in range(N)]

def path(x,d):
    if color[x-1]=="B":
        return False
        
    color[x-1]="B"

    if color==clear:
        color[x-1]="W"
        return True
    
    ans=0
    for i in range(len(A[x-1])):
        ans+=int(path(A[x-1][i],d+1))

    color[x-1]="W"
    return ans

print(path(1,0))

Solution (Python):

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

for i in range(M):
    a,b=map(int,input().split())
    path_matrix[a-1][b-1]=True
    path_matrix[b-1][a-1]=True
view=[False]*N

def path(x,depth):
    if view[x-1]:
        return False
    
    if depth==N-1:
        return True

    view[x-1]=True
    total_ans=0
    for i in range(N):
        if path_matrix[x-1][i]:
            total_ans+=int(path(i+1,depth+1))
    
    view[x-1]=False

    return total_ans

print(path(1,0))

Solution (Python):
import itertools

n,m=map(int,input().split())
rin=[[]for _ in range(n)]
for _ in range(m):
  a,b=map(int,input().split())
  rin[a-1].append(b-1)
  rin[b-1].append(a-1)
  
li=[ i for i in range(2,n+1)]

ans=0

for v in itertools.permutations(li):
  pas=0
  ch=0
  st=1
  for x in range(n-1):
    if v[x]-1 not in rin[st-1]:
      ch+=1
      break
    else:
      st=v[x]
  if ch==0:
    ans+=1
    
print(ans)

Solution (Python):
import itertools

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

graph=[[] for i 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)

for lst in itertools.permutations([j for j in range(1,n)],n-1):
  now=0
  flag=True
  for i in range(n-1):
      if lst[i] not in graph[now]:
          flag=False
          break
      
      else:
          now=lst[i]

  if flag:
          ans+=1


print(ans)

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

G = [list() for _ in range(n + 1)]
for a, b in edges:
    G[a].append(b)
    G[b].append(a)

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

ans = 0

def dfs(v):
    global ans
    if all(checked):
        ans += 1
        return
    for u in G[v]:
        if not checked[u - 1]:
            checked[u - 1] = True
            dfs(u)
            checked[u - 1] = False
    return

checked[0] = True
dfs(1)
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 itertools

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

LIS = [i for i in range(2, n + 1)]
big_lis = list(itertools.permutations(LIS))
L = len(big_lis)

ans2 = 0
for j in range(L):
    i = 1
    ans1 = 1
    for k in big_lis[j]:
        if((i, k) not in lis) & ((k, i) not in lis):
            ans1 = 0
        i = k
    ans2 += ans1
print(ans2)

Solution (Python):
import itertools

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

LIS = [i for i in range(2, n + 1)]
big_lis = list(itertools.permutations(LIS))
L = len(big_lis)

ans2 = 0
for j in range(L):
    i = 1
    ans1 = 1
    for k in big_lis[j]:
        if((i, k) not in lis) & ((k, i) not in lis):
            ans1 = 0
        i = k
    ans2 += ans1
print(ans2)

Solution (Python):
def abc054c_one_stroke_path():
    import itertools
    n, m = map(int, input().split())
    e = [set() for _ in range(n + 1)]
    for _ in range(m):
        a, b = map(int, input().split())
        e[a].add(b)
        e[b].add(a)
    pattern = itertools.permutations(range(2, n + 1))
    cnt = 0
    for p in pattern:
        p_m = [1] + list(p)
        for i in range(n - 1):
            if p_m[i+1] not in e[p_m[i]]:
                break
        else:
            cnt += 1
    print(cnt)


abc054c_one_stroke_path()

Solution (Python):
N,M = [int(a) for a in input().split()]
edges = {i:[] for i in range(1,N+1)}
for i in range(M):
  a,b = [int(a) for a in input().split()]
  edges[a].append(b)
  if a not in edges[b]:
    edges[b].append(a)

def search(lst):
  if len(lst) == N:
    return 1
  else:
    a = lst[-1]
    next = [n for n in edges[a] if n not in lst]
    if len(next) == 0:
      return 0

    tot = 0
    for n in next:
      tot += search(lst + [n])
    
    return tot


ans = search([1])

print(ans)

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


ans = 0
def dfs(node,num,visit):
  visite = visit.copy()
  global ans
  num += 1
  if num == n:
    ans += 1
    return
  else:
    visite[node] = True
    for neib in g[node]:
      if visite[neib] == False:
        dfs(neib,num,visite)
  
visited = [False]*n
dfs(0,0,visited)
print(ans)

Solution (Python):
from itertools import permutations

N,M=map(int,input().split())
E=[[0]*(N+1) for _ in range(N+1)]

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

P=permutations([x for x in range(2,N+1)])

K=0
for p in P:
    Q=[1]+list(p)

    F=1
    for k in range(N-1):
        F*=E[Q[k]][Q[k+1]]

    K+=F
print(K)

Solution (Python):
from itertools import permutations

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

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

ans = 0

for p in permutations(range(N)):
    now = p[0]
    
    if now!=0:
        continue

    for i in range(1, N):
        if G[now][p[i]]==1:
            now = p[i]
        else:
            break
    else:
        ans += 1

print(ans)

Solution (Python):
import itertools as it

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




for i in range(len(a)):
    a.append([a[i][1],a[i][0]])




lis  = list(it.permutations(range(2, n + 1)))

for i in range(len(lis)):
    lis[i] = (1,) + lis[i]



lis2 = []
for i in range(len(lis)):
    lis[i] = list(lis[i])
    lis2.append(lis[i])




ans = 0
for i in range(len(lis2)):
    check = True
    for j in range(len(lis2[i]) - 1):
        if lis2[i][j : j + 2] not in a:
            check = False
    if check:
        ans += 1
print(ans)

Solution (Python):
import itertools as it

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


for i in range(len(a)):
    a.append([a[i][1],a[i][0]])

lis  = list(it.permutations(range(2, n + 1)))
for i in range(len(lis)):
    lis[i] = (1,) + lis[i]

lis2 = []
for i in range(len(lis)):
    lis[i] = list(lis[i])
    lis2.append(lis[i])


ans = 0
for i in range(len(lis2)):
    check = True;
    for j in range(len(lis2[i]) - 1):
        if lis2[i][j : j + 2] not in a:
            check = False;
    if(check):
        ans += 1
print(ans)

Solution (Python):

import itertools as itt

n, m = map(int, input().split())
l = set()
for i in range(m):
    a, b = map(int, input().split())
    l.add((a, b))
    l.add((b, a))

lis = [i for i in range(1, n+1)]
p_lis = list(itt.permutations(lis))

cnt = 0

for i in range(len(p_lis)):
    if p_lis[i][0] != 1:
        continue
    flg = [0]*(n-1)
    for j in range(n-1):
        x = (p_lis[i][j], p_lis[i][j+1])
        if x in l:
            flg[j] = 1
    if all(flg):
        cnt += 1

print(cnt)

Solution (Python):
from itertools import groupby, accumulate, product, permutations, combinations
import numpy as np
N, M = map(int, input().split())
adj = np.zeros((N,N),np.int64)
for i in range(M):
  a,b = map(lambda x:int(x)-1, input().split())
  adj[a,b] = 1
  adj[b,a] = 1
ans = 0
for per in permutations(range(1,N),N-1):
  if adj[0,per[0]]==0:
    continue
  for i in range(N-2):
    if adj[per[i],per[i+1]]==0:
      break
  else:
    ans += 1
print(ans)

Solution (Python):
import itertools

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

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

for _ in range(M):
    a, b = map(lambda x: int(x)-1, input().split())
    graph[a][b] = True
    graph[b][a] = True

ans = 0


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

Solution (Python):

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

path_matrix = []


for n in range(N):
    path_matrix.append([False] * N)


for m in range(M):
    line = map(int, input().split())
    paths = [x - 1 for x in line]
    path_matrix[paths[0]][paths[1]] = True
    path_matrix[paths[1]][paths[0]] = True


visited = [False] * N



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

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

    visited[now] = False

    return total_paths

print(dfs(0, 0))

Solution (Python):
import itertools

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

a = list(itertools.permutations(range(n)))
ans = 0
for i in a:
    if i[0] != 0:
        break
    for j in range(n-1):
        if g[i[j]][i[j+1]] == 0:
            break
    else:
        ans += 1
print(ans)

Solution (Python):
def dfs(v):
    if sum(visited) == N:
        return 1
    res = 0
    for nv in g[v]:
        if visited[nv]:
            continue
        visited[nv] = 1
        res += dfs(nv)
        visited[nv] = 0
    return res


N, M, *ab = map(int, open(0).read().split())
g = [[] for _ in range(N)]
for a, b in zip(*[iter(ab)] * 2):
    a -= 1
    b -= 1
    g[a].append(b)
    g[b].append(a)

visited = [0] * N
visited[0] = 1
print(dfs(0))

Solution (Python):
from itertools import permutations


N, M, *ab = map(int, open(0).read().split())
g = [[0] * N for _ in range(N)]
for a, b in zip(*[iter(ab)] * 2):
    g[a - 1][b - 1] = 1
    g[b - 1][a - 1] = 1

ans = 0
for path in permutations(range(1, N)):
    path = [0] + list(path)
    if all(g[v][nv] for v, nv in zip(path, path[1:])):
        ans += 1
print(ans)

Solution (Python):
from itertools import permutations, islice


def window(seq, n):
    it = iter(seq)
    result = tuple(islice(it, n))
    if len(result) == n:
        yield result
    for elem in it:
        result = result[1:] + (elem,)
        yield result


N, M, *ab = map(int, open(0).read().split())
g = [[0] * N for _ in range(N)]
for a, b in zip(*[iter(ab)] * 2):
    g[a - 1][b - 1] = 1
    g[b - 1][a - 1] = 1

ans = 0
for path in permutations(range(1, N)):
    path = [0] + list(path)
    if all(g[v][nv] for v, nv in window(path, 2)):
        ans += 1
print(ans)

Solution (Python):
from itertools import permutations


N, M, *ab = map(int, open(0).read().split())
g = [[] for _ in range(N)]
for a, b in zip(*[iter(ab)] * 2):
    a -= 1
    b -= 1
    g[a].append(b)
    g[b].append(a)

ans = 0
for path in permutations(range(1, N)):
    v = 0
    for nv in path:
        if nv not in g[v]:
            break
        v = nv
    else:
        ans += 1
print(ans)

Solution (Python):
import itertools

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

l = range(2, N + 1)

ans = 0

for p in itertools.permutations(l):
    
    nums = [1]
    for n in p:
        nums.append(n)

    flag = True

    for i in range(N - 1):
        if nums[i + 1] in G[nums[i]]:
            continue
        else:
            flag = False
            break
    if flag == True:
        ans += 1

print(ans)