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())
edges = [[] for _ in range(n)]
for _ in range(m):
    a, b = map(lambda x: int(x) - 1, input().split())
    edges[a].append(b)
    edges[b].append(a)

count = 0
for perm in itertools.permutations(range(1, n)):
    if not perm[0] in edges[0]:
        continue
    can_visit_all = True
    for i in range(n - 2):
        if not perm[i + 1] in edges[perm[i]]:
            can_visit_all = False
            break
    if can_visit_all:
        count += 1
print(count)

Solution (Python):
from itertools import permutations

n,m = map(int, input().split())
gl = [ [False]*(n+1) for _ in range(n+1) ]
for _ in range(m):
    a,b = map(int, input().split())
    gl[a][b] = True
    gl[b][a] = True


ll = list(range(2,n+1))  
perml = list(permutations(ll, n-1))
ans = 0

for perm in perml:
    curr = 1
    for v in perm:
        if gl[curr][v]:
            curr = v
        else:
            break
    else:
        ans += 1

print(ans)

Solution (Python):
import itertools as it

n,m=map(int,input().split())
ans=[]
for i in range(m):
    a,b=map(int,input().split())
    ans.append([a,b])
    ans.append([b,a])
  
a=0
for e in it.permutations(range(n)):
    
    count=1
    if e[0]!=0:
        break
    
    for i in range(n-1):
        if [e[i]+1,e[i+1]+1] in ans:
            count*=1
        else:
            count*=0
            break
            
    a+=count
    
print(a)

Solution (Python):
import itertools

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

link_flag = 1
cnt = 0

for k in itertools.permutations(range(n)): 
    if k[0] != 0:
        break
    link_flag = 1
    for i in range(len(k)-1):
        if link_flag == 0:
            break
        link_flag = 0
        for j in range(m):
            if k[i]+1 == a_list[j]:
                if k[i+1]+1 == b_list[j]:
                    link_flag = 1
                    
                    break
            if k[i]+1 == b_list[j]:
                if k[i+1]+1 == a_list[j]:
                    link_flag = 1
                    
                    break
        if i == len(k)-2 and link_flag ==1:
            cnt += 1
print(cnt)

Solution (Python):
from itertools import permutations

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

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

l = [i for i in range(1,n)]
for j in permutations(l):
    bit = 1
    if dp[0][j[0]]!=1:
        bit = 0
    for i in range(n-2):
        if dp[j[i]][j[i+1]]!= 1:
            bit = 0
    if bit==1:
        ans += 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 collections
import itertools

N, M = map(int, input().split())
a, b = list(zip(*[map(int, input().split()) for _ in range(M)]))

paths = collections.defaultdict(list)
for i in range(M):
    paths[a[i] - 1].append(b[i] - 1)
    paths[b[i] - 1].append(a[i] - 1)

ans = 0
for perm in itertools.permutations(range(N)):
    if perm[0] != 0:
        continue

    for i in range(1, N):
        if perm[i] not in paths[perm[i - 1]]:
            break
    else:
        ans += 1

print(ans)

Solution (Python):
import itertools

P = []
counter = 0
if __name__ == '__main__':
    N, M = map(int, input().split())
    P = [[0]*N for _ in range(N)]
    for _ in range(M):
        a, b = map(int, input().split())
        P[a-1][b-1] = P[b-1][a-1] = 1
    for v in itertools.permutations(range(N)):
        if v[0] != 0:
            break
        flag = 0
        for i in range(N - 1):
            if P[v[i]][v[i + 1]] == 0:
                flag = 1
                break
        if flag == 0:
            counter += 1
        
    print(counter)

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

G=[[] for _ in range(N+1)]

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

def dfs(v,seen=None,h=[]):
    global ans
    if not seen:
      seen = [0]*(N+1)
    seen[v] = 1
    if len(h) == N:
        ans += 1
        return
    update=0
    for u in G[v]:
        if seen[u] == 0:
          seen[u] = 1
          h.append(u)
          update = 1
          dfs(u,seen,h)
          h.pop()
          seen[u] = 0
    if update==0:return

dfs(1,h=[1])
print(ans)

Solution (Python):


from itertools import permutations
N, M = list(map(int, input().split()))
L=[]
for _ in range(M):
    L.append(list(map(int, input().split())))


P = list(permutations(range(1,N+1)))

ct = 0
for i in P:
    if i[0]==1 and \
    all((sorted([i[j], i[j+1]]) in L) for j in range(N-1)):
        ct += 1
print(ct)

Solution (Python):
import itertools
import numpy as np


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

count=0
for route in ls:
    if route[0]!=1:
        break

    flag = True
    for i in range(n-1):
        if ( ([route[i],route[i+1]] in ab) or ([route[i+1],route[i]] in ab) )  == False:
            flag = False
            continue
    if flag == False:
        continue
    count +=1

print(count)

Solution (Python):
import itertools

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

count = 0
for c in itertools.permutations(bag):
    if not c[0] == 1:
        continue
    flag = False
    for i in range(N-1):
        if not c[i+1] in V[c[i]-1]:
            flag = True
            break
    if not flag:
        count += 1
print(count)

Solution (Python):
from collections import deque
import copy



N, M = map(int, input().split())
V = [[] for _ in range(N)]
cont = [0 for _ in range(N)]
for _ in range(M):
    a, b = map(int, input().split())
    V[a-1].append([b, copy.deepcopy(cont)])
    V[b-1].append([a, copy.deepcopy(cont)])


q = deque()
q.append([1, copy.deepcopy(cont)])
count = 0
while q:
    c_v = q.pop()
    c_v[1][c_v[0]-1] = 1
    next_vs = V[c_v[0]-1]
    ifComplete = 1
    for v in next_vs:
        if c_v[1][v[0]-1] == 1:
            continue
        else:
            ifComplete = 0
        
        
        v[1] = copy.deepcopy(c_v[1])
        q.append(v)
    
    if ifComplete:
        flag = 1
        for x in c_v[1]:
            if x == 0:
                flag = 0
                break
        if flag:
            count += 1
print(count)

Solution (Python):
import itertools

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

ls = [[] for _ in range(n)]

for _ in range(m):
    s, t = map(int, input().split())
    ls[s-1].append(t-1)
    ls[t-1].append(s-1)

count = 0
for per in itertools.permutations(range(n)):

    if per[0] != 0:
        continue
    for i in range(1, n):
        if per[i] not in ls[per[i-1]]:
            break
        if i == n-1:
            count += 1

print(count)

Solution (Python):
import sys
import math
import heapq
mod=10**9+7
inf=float("inf")
from math import sqrt
from collections import deque
from collections import Counter
from math import ceil
input=lambda: sys.stdin.readline().strip()
sys.setrecursionlimit(11451419)
from decimal import Decimal 
from functools import lru_cache






from itertools import permutations as per
n,m=map(int,input().split())
A=[[] for i in range(n)]
for i in range(m):
    a,b=map(int,input().split())
    a-=1 ;b-=1
    A[a].append(b)
    A[b].append(a)

ans=0
for bit in per([i for i in range(1,n)]):
    
    peanut=0
    bit=[0]+list(bit)
    for i in range(n-1):
        if not bit[i] in A[bit[i+1]]:
            peanut=1
            break
    else:
        ans+=1
    

print(ans)

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

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

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

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

print(dfs(0, used))

Solution (Python):
from itertools import permutations
n,m=map(int,input().split())
e=[[]for _ in range(n)]
for _ in range(m):
  a,b=map(int,input().split())
  e[a-1]+=[b-1]
  e[b-1]+=[a-1]
num=list(permutations([0]+list(range(1,n))))
ans=0
for i in range(len(num)):
  if num[i][0]!=0:continue
  s=1
  now=0
  while s<n:
    if num[i][s] in e[now]:
      now=num[i][s]
      s+=1
    else:break
  if s==n:ans+=1
print(ans)

Solution (Python):
n,m=map(int,input().split())
e=[[]for _ in range(n)]
for _ in range(m):
  a,b=map(int,input().split())
  e[a-1]+=[b-1]
  e[b-1]+=[a-1]
def dfs(now,vis):
  vis+=[now]
  if len(vis)==n:return 1
  res=0
  for to in e[now]:
    if to not in vis:
      res+=dfs(to,vis[:])
  return res
print(dfs(0,[]))

Solution (Python):
from itertools import permutations
n,m=map(int,input().split())
e=[[]for _ in range(n)]
for _ in range(m):
  a,b=map(int,input().split())
  e[a-1]+=[b-1]
  e[b-1]+=[a-1]
def dfs(now,vis):
  vis+=[now]
  if len(vis)==n:return 1
  res=0
  for to in e[now]:
    if to not in vis:
      res+=dfs(to,vis[:])
  return res
print(dfs(0,[]))

Solution (Python):



class Graph():

    def __init__(self):
        self.adjacency_dict = {}
    
    def add_vertex(self, v):
        self.adjacency_dict[v] = []

    def add_edge(self, v1, v2):
        self.adjacency_dict[v1].append(v2)
        self.adjacency_dict[v2].append(v1)

    def remove_edge(self, v1, v2):
        self.adjacency_dict[v1].remove(v2)
        self.adjacency_dict[v2].remove(v1)

    def remove_vertex(self,v):
        while self.adjacency_dict[v] != []:
            adjacency_vertex = self.adjacency_dict[v][-1]
            self.remove_edge(v, adjacency_vertex)
        del adjacency_vertex[v]

    def get_vertexes(self):
        return self.adjacency_dict.keys()

    def get_edges(self, v):
        return self.adjacency_dict[v]

    def print_graph(self):
        print(self.adjacency_dict)

import itertools

g = Graph()
N, M = map(int, input().strip().split())
for i in range(N):
    g.add_vertex(i+1)
for _ in range(M):
    a, b = map(int, input().strip().split())
    g.add_edge(a, b)
res = 0
permutations_vertexes = itertools.permutations(g.get_vertexes())
for permutation in permutations_vertexes:
    prev_vertex = permutation[0]
    if prev_vertex != 1:
        continue
    can_all_vertex = True
    for vertex in permutation:
        if prev_vertex == vertex:
            continue
        if vertex not in g.get_edges(prev_vertex):
            can_all_vertex = False
            break
        prev_vertex = vertex
    if can_all_vertex:
        res += 1
print(res)

Solution (Python):
from collections import deque
import copy

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

waiting = deque()
flag_s = [0]*N
start_point = 0
waiting.append([start_point, flag_s])
cnt = 0
while len(waiting) != 0:
    cur_node, flag = waiting.pop()
    flag = copy.deepcopy(flag)
    flag[cur_node] = 1
    if sum(flag) == N: cnt += 1
    for e in e_list[cur_node]:
        if flag[e] != 1:
            waiting.append([e, flag])

print(cnt)

Solution (Python):
from collections import defaultdict

N, M = map(int, input().split())
adj_list = defaultdict(set)

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

visited = set() 

res = 0

def backtrack(visited, num):
    global res
    if num in visited:
        return
    if len(visited | {num}) == N:
        res = res + 1
        return

    for neighbor in adj_list[num]:
        backtrack(visited | {num}, neighbor)

backtrack(visited, 1)

print(res)

Solution (Python):
import itertools as it
import sys

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

a=[]

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

ans=0
for e in it.permutations(range(N)):
    if e[0]!=0:
        break
        
    count=1
    for j in range(N-1):
        if [e[j]+1,e[j+1]+1] in a:
            count*=1
        else:
            count*=0
            break
            
    ans+=count

print(ans)

Solution (Python):
import itertools as it
import sys

N, M = map(int, input().split())
if N==0 or M==0:
    print(0)
    sys.exit()
a=[]

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

ans=0
for e in it.permutations(range(N)):
    if e[0]!=0:
        break
        
    count=1
    for j in range(N-1):
        if [e[j]+1,e[j+1]+1] in a:
            count*=1
        else:
            count*=0
            break
            
    ans+=count

print(ans)

Solution (Python):
import itertools
N,M=map(int,input().split())
branch=[]
for _ in range(M):
    a,b=map(int,input().split())
    branch.append([a,b])
    branch.append([b,a])
ans=0
for perm in itertools.permutations(list(range(1,N+1))):
    f=True
    if perm[0]==1:
        for i in range(N-1):
            if not [perm[i],perm[i+1]] in branch:
                f=False
        if f:
            ans+=1
print(ans)

Solution (Python):

N,M = [int(i) for i in input().split(" ")]
neighbor_dict={n:set() for n in range(1,N+1)}


for i in range(M):
    a,b = [int(i) for i in input().split(" ")]
    neighbor_dict[a].add(b)
    neighbor_dict[b].add(a)

ans = 0

def crawl(vertex:int,visited_set:set):
    visited_set = visited_set | {vertex}
    if len(visited_set) == N:
        global ans
        ans = ans + 1
        return

    to_visit = set(neighbor_dict[vertex]) - visited_set

    for v in to_visit:
        crawl(v,visited_set)

crawl(1,set())
print(ans)

Solution (Python):
from collections import deque
N, M = map(int, input().split())
L = [list(map(int, input().split())) for _ in range(M)]
stack = deque([[1]])
seen = deque([])
c = 0
while stack:
  x = stack.pop()
  seen.append(x)
  if len(x)==N:
    c += 1
    continue
  p = x[-1]
  A = []
  for l in L:
    if l[0]==p:
      A.append(l[1])
    if l[1]==p:
      A.append(l[0])
  A = [a for a in A if a not in x]
  for a in A:
    if x+[a] in (seen or stack):
      continue
    else:
      stack.append(x+[a])
print(c)

Solution (Python):
from collections import defaultdict
n, m = map(lambda x: int(x), input().split())

links = defaultdict(set)

for _ in range(m):
    a, b = map(lambda x: int(x), input().split())
    links[a].add(b)
    links[b].add(a)
    
path_counter = 0
    
def path_patterns_number(current_node, remaining_nodes):
    if len(remaining_nodes) == 0:
        return 1
    
    patterns = 0
    
    for next_node in (links[current_node] & remaining_nodes):


        patterns += path_patterns_number(
            next_node,
            remaining_nodes.copy() - {next_node}

        )
    
    return patterns
    
print(path_patterns_number(1, set(range(2,n+1))))

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

I = [set() for _ in range(N)]
seq = [i for i in range(1,N)]

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

ans = 0
for p in itertools.permutations(seq):
  flag = True
  for i in range(N-2):
    
    if p[i+1] not in I[p[i]]:
      flag = False 
      break
  if 0 not in I[p[-1]]:
    flag = False 
  if flag:
    ans += 1

print(ans)

Solution (Python):
import itertools
n, m = map(int, input().split())
G = [set() for _ in range(n)]
for _ in range(m):
    a,b = map(lambda x:int(x)-1, input().split())
    G[a].add(b)
    G[b].add(a)

P = [*itertools.permutations(range(1,n))]
ans = 0
for p in P:
    nw = 0
    for nx in p:
        if nx in G[nw]:
            nw = nx
        else:
            break
    else:
        ans += 1
print(ans)

Solution (Python):

import sys
sys.setrecursionlimit(10**7)
import bisect
import heapq
import itertools
import math
from collections import Counter, defaultdict, deque
from copy import deepcopy
from decimal import Decimal
from math import gcd
from operator import add, itemgetter, mul, xor
def cmb(n,r,mod):
  bunshi=1
  bunbo=1
  for i in range(r):
    bunbo = bunbo*(i+1)%mod
    bunshi = bunshi*(n-i)%mod
  return (bunshi*pow(bunbo,mod-2,mod))%mod
mod = 10**9+7
def I(): return int(input())
def LI(): return list(map(int,input().split()))
def MI(): return map(int,input().split())
def LLI(n): return [list(map(int, input().split())) for _ in range(n)]

n,m = MI()
graph = [[] for _ in range(n+1)]
for i in range(m):
    a,b = MI()
    graph[a].append(b)
    graph[b].append(a)
visited = [False]*(n+1)
visited[0] = True
visited[1] = True
def dfs(v,visited):
    if all(visited):
        return 1
    ans = 0
    for i in graph[v]:
        if visited[i]:
            continue
        visited[i] = True
        ans += dfs(i,visited)
        visited[i] = False
    return ans
print(dfs(1,visited))

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

g = [[] for _ in range(N)]

for i in range(M):
    a, b = list(map(int, input().split()))

    g[a-1].append(b-1)
    g[b-1].append(a-1)

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

def dfs(now, prev, vis):
    visited_copy = copy.copy(vis)
    visited_copy[now] = True
    all_visited = True

    for is_node_visited in visited_copy:
        if not is_node_visited:
            all_visited = False

    if all_visited:
        return 1

    counter = 0
    for adj in g[now]:
        if prev == adj:
            continue

        if visited_copy[adj]:
            continue
        counter += dfs(adj, now, visited_copy)

    return counter

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

Solution (Python):
from itertools import permutations

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

res = 0
for t in permutations(list(range(1, n))):
    l = list(t)
    l.insert(0, 0)
    flag = True

    for i in range(n-1):
        if not edge[l[i]][l[i+1]]:
            flag = False

    if flag:
        res += 1

print(res)

Solution (Python):
import itertools
N, M, *AB = [int(_) for _ in open(0).read().split()]
G = [set() for _ in range(N)]
for a, b in zip(AB[::2], AB[1::2]):
    a -= 1
    b -= 1
    G[a].add(b)
    G[b].add(a)
ans = 0
for root in itertools.permutations(range(1, N), N - 1):
    root = [0] + list(root)
    if all(a in G[b] for a, b in zip(root, root[1:])):
        ans += 1
print(ans)

Solution (Python):



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

graph = [ ]
for _ in range(N+1):
    graph.append([])

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

visited = []
for _ in range(N+1):
    visited.append(False)


def dfs(dep,cur):
    global N,visited,graph

    if dep == N:
        return 1

    ans = 0

    for dist in graph[cur]:
        if visited[dist] == False:
            visited[dist] = True
            ans += dfs(dep + 1,dist)
            visited[dist] = False
    return ans

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

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):
N,M = map(int, input().split())
G = [[] for j in range(N)]
for i in range(M):
    a,b = map(int, input().split())
    G[a-1].append(b-1)
    G[b-1].append(a-1)
visited = [False]*N
visited[0] = True
def DFS(v,visited):
    
    if all(visited):
        return 1
    ans = 0
    for i in G[v]:
        if visited[i]:
            continue
        visited[i] = True
        ans += DFS(i,visited)
        visited[i] = False
    return ans
 
print(DFS(0,visited))

Solution (Python):
"""
順列全探索
"""
import itertools
n, m = map(int, input().split())
path = []
for _ in range(m) :
    a, b = map(int, input().split())
    path.append([a, b])

ans = 0
order_list = list(itertools.permutations(range(2,n+1)))
for order in order_list :
    now = 1
    for i in order :
        if [now,i] in path :
            now = i
        elif [i,now] in path :
            now = i
        else :
            break
    else :
        ans += 1
print(ans)

Solution (Python):
from collections import defaultdict


def read_int():
    return int(input().strip())


def read_ints():
    return list(map(int, input().strip().split(' ')))


def solve():
    N, M = read_ints()
    G = defaultdict(list)
    for _ in range(M):
        a, b = read_ints()
        G[a].append(b)
        G[b].append(a)

    def dfs(node, visited):
        if len(visited) == N:
            return 1
        answer = 0
        for child in G[node]:
            if child not in visited:
                visited.add(child)
                answer += dfs(child, visited)
                visited.discard(child)
        return answer
    
    return dfs(1, set([1]))


if __name__ == '__main__':
    print(solve())

Solution (Python):

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

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

is_used = [False for _ in range(N)]
is_used[0] = True
buf = [(0, is_used)]
ans = 0

while buf:
    src, is_used = buf.pop()
    if all(is_used):
        ans += 1

    else:
        for dst in graph[src]:
            if not is_used[dst]:
                is_used2 = list(is_used)
                is_used2[dst] = True
                buf.append((dst, is_used2))

print(ans)

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

lis = [x for x in range(2, N+1)] 
ans = 0

permutations_lis = itertools.permutations(lis)

for one_case in permutations_lis:
  List = [1]
  List.extend(one_case)
  for i in range(N-1):
    if not ([List[i], List[i+1]] in Path or [List[i+1], List[i]] in Path):
      break
  else:
    ans += 1
print(ans)

Solution (Python):
import itertools
n,m=map(int,input().split())
path=[]
for i in range(m):
    a,b=map(int,input().split())
    path.append([a,b])
    path.append([b,a])
ans=0
factorial=list(itertools.permutations(list(range(1,n+1))))

for i in range(len(factorial)):
    if factorial[i][0]!=1:
        continue
    flag=True
    for j in range(1,n):
        if [factorial[i][j-1],factorial[i][j]] not in path:
            flag=False
    ans+=flag
print(ans)

Solution (Python):
mat = [[] for i in range(10)]
vis  = [False for i in range(10)]
def dfs(a, n):
	all_vis= True
	for i in range(0, n):
		if vis[i]==False:
			all_vis=False
	if all_vis==True:
		return 1
	ans =0
	for i in mat[a]:
		if vis[i]==True:
			continue
		vis[i]=True
		ans = ans+dfs(i,n)
		vis[i]=False
	return ans
n , m = map(int , input().split())
for i in range(m):
	a, b= map(int ,input().split())
	a =a-1
	b=b-1
	mat[a].append(b)
	mat[b].append(a)
vis[0]=True
print(dfs(0, n))

Solution (Python):
import itertools

n, m = map(int, input().split())
lsts = []
for _ in range(m):
  lsts.append(list(map(int, input().split())))
m = list(range(2, n + 1))
all = []
for v in itertools.permutations(m):
  l = [1] + list(v)
  all.append(l)


count = 0
for each in all:
  for i in range(n - 1):
    flag = False
    pos_1 = each[i]
    pos_2 = each[i + 1]
    for lst in lsts:
      if (pos_1 == lst[0] and pos_2 == lst[1]) or (pos_1 == lst[1] and pos_2 == lst[0]):
        flag = True
        break
    if not flag:
      break
  if flag:
    count += 1
print(count)

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

def dfs(depth, node):
    global visited
    global ans
    visited[node] = 1
    if depth == N - 1:
        if sum(visited) == N:  ans += 1
        return
    for i in G[node]:
        if visited[i] == 0:
            dfs(depth + 1, i)
            visited[i] = 0
            
ans = 0
visited = [0 for _ in range(N)]
dfs(0, 0)
print(ans)

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

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

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

for i in range(1 << n):
    for u in range(n):
        for v in adj[u]:
            if i >> v & 1 == 0:
                nxt = i + (1 << v)
                dp[nxt][v] += dp[i][u]

print(sum(dp[-1]))

Solution (Python):
from itertools import permutations

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

g = [[0] * (n + 1) for _ in range(n + 1)]
for a, b in ab:
    g[a][b] = 1
    g[b][a] = 1

ans = 0
for nxt in permutations(range(2, n + 1), n - 1):
    bl = 1
    u = 1
    for v in nxt:
        if not g[u][v]:
            bl = 0
            break
        u = v

    ans += bl

print(ans)

Solution (Python):
f=lambda:map(int,input().split())
n,m=f()
g=[[] for _ in range(n)]
for _ in range(m):
  a,b=f()
  g[a-1]+=[b-1]
  g[b-1]+=[a-1]
from itertools import *
p=[*permutations(range(1,n))]
a=0
for t in p:
  v=0
  for c in t:
    if c in g[v]: v=c
    else: break
  else: a+=1
print(a)

Solution (Python):
f=lambda:map(int,input().split())
n,m=f()
g=[[0]*n for _ in range(n)]
for _ in range(m):
  a,b=f()
  g[a-1][b-1]=1
  g[b-1][a-1]=1
from itertools import *
p=[*permutations(range(1,n))]
a=0
for t in p:
  v=0
  for c in t:
    if g[v][c]: v=c
    else: break
  else: a+=1
print(a)

Solution (Python):
f=lambda:map(int,input().split())
n,m=f()
g=[set() for _ in range(n)]
for _ in range(m):
  a,b=f()
  g[a-1].add(b-1)
  g[b-1].add(a-1)
from itertools import *
p=[*permutations(range(1,n))]
c=0
for t in p:
  v=0
  for i in t:
    if i in g[v]: v=i
    else: break
  else: c+=1
print(c)

Solution (Python):
from collections import deque
N,M = map(int,input().split())
g = [[] for i in range(N)]
for i in range(M):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    g[a].append(b)
    g[b].append(a)
ans = 0
que = deque([[0]])
while len(que) != 0:
    p = que.popleft()
    if len(p) == N:
        ans += 1
    else:
        for i in range(len(g[p[-1]])):
            if not g[p[-1]][i] in p:
                que.append(p + [g[p[-1]][i]])
print(ans)

Solution (Python):
import sys
from itertools import permutations

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N, M, *AB = map(int, read().split())
    G = [[] for _ in range(N)]
    for a, b in zip(*[iter(AB)] * 2):
        G[a - 1].append(b - 1)
        G[b - 1].append(a - 1)

    def dfs(v, seen):
        if len(seen) == N:
            return 1

        ans = 0
        for nv in G[v]:
            if nv not in seen:
                seen.add(nv)
                ans += dfs(nv, seen)
                seen.remove(nv)

        return ans

    print(dfs(0, {0}))
    return


if __name__ == '__main__':
    main()

Solution (Python):
import sys
from itertools import permutations

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N, M, *AB = map(int, read().split())
    G = [[False] * N for _ in range(N)]
    for a, b in zip(*[iter(AB)] * 2):
        G[a - 1][b - 1] = G[b - 1][a - 1] = True

    ans = 0
    for perm in permutations(range(1, N)):
        if not G[0][perm[0]]:
            continue
        ok = True
        for i in range(N - 2):
            if not G[perm[i]][perm[i + 1]]:
                ok = False
                break
        if ok:
            ans += 1

    print(ans)
    return


if __name__ == '__main__':
    main()

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())
    g[a-1].append(b-1)
    g[b-1].append(a-1)

ans = 0
for perm in permutations(range(1, n), n-1):
    s = 0
    flag = True
    for p in perm:
        if p not in g[s]:
            flag = False
            break
        s = p
    if flag:
        ans += 1
print(ans)

Solution (Python):
from itertools import *
f=lambda:map(int,input().split())
N,M=f()
a=[[*f()] for i in range(M)]
a=[*a,*[[y,x] for x,y in a]]
p=[(1,*i)for i in [*permutations(range(2,N+1))]]
print([sum(1 for y in range(N-1)if [x[y],x[y+1]] in a)for x in p].count(N-1))

Solution (Python):
from itertools import permutations
import copy

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

    ls = list(permutations(range(1, N)))
    ans = 0
    for l in ls:
        h = copy.deepcopy(G)
        cnt = 1
        p = 0 
        for k in l:
            if h[p][k] == 0:
                break
            else:
                cnt += 1
                p = k
        if cnt == N:
            ans += 1
    print(ans)
    return

resolve()