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):
from sys import setrecursionlimit
setrecursionlimit(10**9)

from sys import stdin

readline=stdin.readline
n,m=map(int,readline().split())
G=[[] for _ in range(n)]
for i in range(m):
    a,b=map(lambda x:int(x)-1,readline().split())
    G[a].append(b)
    G[b].append(a)

flags=[False]*n
ans=0
def dfs(now,cnt):
    global ans
    cnt+=1
    flags[now]=True
    if cnt==n:
        ans+=1
    else:
        for nex in G[now]:
            if flags[nex]==False:
                dfs(nex,cnt)
    flags[now]=False

dfs(0,0)
print(ans)

Solution (Python):
def dfs(a,count,seen):
    nseen=seen[:]
    ans=0
    nseen[a] = 1;
    if count==n-1:
        return 1
    else:
        for i in g[a]:
            if not seen[i]:
                ans+=dfs(i,count+1,nseen)
        return ans
n,m=map(int,input().split())
g=[[]*n 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)
seen=[0]*n
print(dfs(0,0,seen))

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


LI = lambda: list(map(int, input().split()))


N, M = LI()
AB = [LI() for _ in range(M)]

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


def create_link():
    for a, b in AB:
        link[a - 1].append(b - 1)
        link[b - 1].append(a - 1)


def dfs(v=0, s=set()):
    s = s | {v}
    if len(s) == N:
        return 1
    ans = 0
    for u in link[v]:
        if u in s:
            continue
        ans += dfs(u, s)
    return ans


def main():
    create_link()
    ans = dfs()
    print(ans)


if __name__ == "__main__":
    main()

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

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

D = [0]*N
C = 0
D[0] = 1

def dfs(x):
    global C
    
    if not 0 in D:
        C += 1
        return
    
    for i in A[x]:
        if D[i] == 1:
            continue
        D[i] = 1
        dfs(i)
        D[i] = 0

dfs(0)
print(C)

Solution (Python):
N, M = list(map(int,input().split()))
adj = []
visit = []

def DFS(p):
  count = 0
  if all(visit):
    return 1
  for n in adj[p]:
    if visit[n] == 0:
      visit[n] = 1
      count += DFS(n)
      visit[n] = 0
  return count

def main():
  for n in range(N):
    adj.append([])
    visit.append(0)
  for m in range(M):
    i, j = list(map(int,input().split()))
    adj[i-1].append(j-1)
    adj[j-1].append(i-1)
  visit[0] = 1
  return DFS(0)

print(main())

Solution (Python):
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)
import sys
sys.setrecursionlimit(10**7)

def dfs(t,seen):
  if all(seen):
    return 1
  ret=0
  l=g[t]
  for li in l:
    if seen[li]==0:
      seenli=seen.copy()
      seenli[li]=1
      ret+=dfs(li,seenli)
  return ret
seen=[0]*n
seen[0]=1
print(dfs(0,seen))

Solution (Python):
import itertools

n, m = list(map(int, input().split()))
v = []
for i in range(m):
  tpl = tuple(map(int, input().split()))
  v.append(tpl)
  v.append((tpl[1], tpl[0]))

perms = list(itertools.permutations(range(1, n+1)))
c = 0
for i in perms:
  if i[0] != 1:
    continue
  for j in range(len(i)-1):
    if (i[j], i[j+1]) not in v:
      break
  else:
    c += 1
print(c)

Solution (Python):
import sys
import os
import math
import bisect
import collections
import itertools
import heapq
import re
import queue
from decimal import Decimal



sys.setrecursionlimit(10000000)

ii = lambda: int(sys.stdin.buffer.readline().rstrip())
il = lambda: list(map(int, sys.stdin.buffer.readline().split()))
fl = lambda: list(map(float, sys.stdin.buffer.readline().split()))
iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)]

iss = lambda: sys.stdin.buffer.readline().decode().rstrip()
sl = lambda: list(map(str, sys.stdin.buffer.readline().decode().split()))
isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)]

lcm = lambda x, y: (x * y) // math.gcd(x, y)


MOD = 10 ** 9 + 7
MAX = float('inf')


def dfs(graph, start, visited):
    visited[start] = True
    ret = 0
    if all(visited):
        visited[start] = False
        return 1

    for next in graph[start]:
        if not visited[next]:
            ret += dfs(graph, next, visited)
    visited[start] = False
    return ret


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    N, M = il()
    graph = {n: [] for n in range(N)}
    visited = [False] * N
    for _ in range(M):
        a, b = il()
        graph[a - 1].append(b - 1)
        graph[b - 1].append(a - 1)

    print(dfs(graph, 0, visited))


if __name__ == '__main__':
    main()

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

hen=[]
check=0

for _ in range(m):
  hen.append(list(map(int, input().split())))

l=list(range(2, n+1))
for v in itl.permutations(l):
  
  for i in range(n-2):
    if not(sorted(v[i:i+2]) in hen) or not(list([1, v[0]]) in hen):
      break
  else:
    if n==2:
      check+=1
    elif i==n-3:
      check+=1
    continue
print(check)

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

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

def bfs(bit, pos, s):
    global ans
    if bit == bin[-1] - 1:
        ans += 1
        return
    for next_pos in ab[pos]:
        if (bit // bin[next_pos]) % 2 == 1:
            continue
        bfs(bit + bin[next_pos], next_pos, s + str(next_pos + 1))

ans = 0
bfs(1, 0, "1")
print(ans)

Solution (Python):

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

import itertools 

state = list(itertools.permutations(list(range(n)) ,n ))
def abc054c(i):
    counter = 1
    if i[0] != 0:
        return 0
    for j,k  in enumerate(i):
        if j == n -1:
            pass
        elif i[j +1] in connect[k]:
            pass
        else:
            counter = 0
            break
    return counter
total = 0
for  i in state:
    total += abc054c(i)
    
print(total)

Solution (Python):


import sys
import numpy
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil,pi,factorial
from operator import itemgetter
from copy import deepcopy
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
def SI(): return input().rstrip()
def printns(x): print('\n'.join(x))
def printni(x): print('\n'.join(list(map(str,x))))
inf = 10**17
mod = 10**9 + 7

n,m=MI()
tree=[[] for i in range(n)]
for i in range(m):
    a,b=MI()
    a-=1;b-=1
    tree[a].append(b)
    tree[b].append(a)



count=0
def dfs(x,al):
    global count
    if len(al+[x])==n:
        count+=1
        
        return
    
        
    
    
    for y in tree[x]:
        if not (y in al):
            
            dfs(y,al+[x]) 
dfs(0,[])
print(count)

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

ans = 0
def dfs(visited, current):
    global ans
    if len(visited) == n:
        ans += 1
        return
    for nex in mat[current]:
        if nex not in visited:
            _vi = visited[:]
            _vi.append(nex)
            dfs(_vi, nex)

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

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

res = 0
for case in itertools.permutations(range(n)):
  if case[0] != 0:
    continue
  for i in range(n-1):
    if case[i+1] not in path[case[i]]:
      break
  else:
    res+=1
print(res)

Solution (Python):
import sys
sys.setrecursionlimit(10**5)
def solve():
    N,M = map(int,input().split())
    G = [[False]*N for _ in range(N)]
    for _ in range(M):
        a, b = map(int,input().split())
        a -= 1
        b -= 1
        G[a][b] = True
        G[b][a] = True
    
    visited = [False] * N
    print(dfs(0, G, visited[:], N))

def dfs(now, G, visited, N):
    visited[now] = True
    if not (False in visited):
        return 1
    
    cnt = 0
    for next in range(N):
        if not visited[next] and G[now][next]:
            cnt += dfs(next,G,visited[:],N)
    
    return cnt

if __name__ == '__main__':
    solve()

Solution (Python):
from itertools import permutations

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

all_routes = list(permutations([i for i in range(1, N + 1)]))

ans = 0
for route in all_routes:
    flg = True
    if route[0] != 1:
        break
    for i in range(1, N):
        if path[route[i-1] - 1][route[i] - 1] != 1:
            flg = False
            break
    if flg:
        ans += 1

print(ans)

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):
from collections import deque
import copy
n,m = map(int,input().split())
Map = [[] for i in range(n)]

for i in range(m):
    a,b = map(int,input().split())
    Map[a-1].append(b-1)
    Map[b-1].append(a-1)
visit = [False for i in range(n)]
ans = 0
q = deque()
q.append((0,visit))
while q:
    index,visit = q.popleft()
    Visit = copy.deepcopy(visit)
    if not Visit[index]:
        Visit[index] = True
    else:
        continue
    if all(Visit):
        ans += 1
        continue
    for i in Map[index]:
        q.append((i,Visit))
print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(10 ** 9)
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)
D = [0] * N
D[0] = 1

C = 0
def dfs(n):
    global C
    if not 0 in D:
        C += 1
        return
    for i in G[n]:
        if D[i] == 1:
            continue
        D[i] = 1
        dfs(i)
        D[i] = 0

dfs(0)
print(C)

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

N, M = map(int, input().split())
paths = [[] for n in range(N)]
def add_paths(a, b):
    paths[a - 1].append(b - 1)
    paths[b - 1].append(a - 1)

for i in range(M):
    a, b = map(int, input().split())
    add_paths(a, b)
route = deque([(0, paths[0], [False for n in range(N)])])
ans = 0
while len(route) > 0:
    vertex, path, visited = route.pop()
    visited[vertex] = True
    for i in path:
        if visited[i] != True:
            route.append((i, paths[i], deepcopy(visited)))
    if visited.count(False) == 0:
        ans += 1
print(ans)

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

    
    G = {}
    for m in range(M):
        a, z = map(int, input().split())
        G[a] = G.get(a, [])
        G[a].append(z)
        G[z] = G.get(z, [])
        G[z].append(a)

    

    
    if G.get(1, 0) == 0:
        print(0)
        return

    def dfs(a, path):
        path.append(a)
        if len(path) == N:
            return 1

        paths = 0
        for z in G.get(a):
            if z in path:
                continue
            paths += dfs(z, path[:])

        return paths

    print(dfs(1, []))



if __name__ == "__main__":
    abc054_c_one_stroke_paths()

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

    
    G = {}
    for m in range(M):
        a, z = map(int, input().split())
        G[a] = G.get(a, [])
        G[a].append(z)
        G[z] = G.get(z, [])
        G[z].append(a)

    

    
    if G.get(1, 0) == 0:
        print(0)
        return

    paths = []

    def solve(a, path):
        path.append(a)
        if len(path) == N:
            paths.append(path)
            return
        for z in G.get(a):
            p = copy.copy(path)
            if z in p:
                continue
            solve(z, p)

    solve(1, [])
    
    print(len(paths))



if __name__ == "__main__":
    abc054_c_one_stroke_paths()

Solution (Python):
import math



def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    
    return divisors

def ValueToBits(x,digit):
    res = [0 for i in range(digit)]
    now = x
    for i in range(digit):
        res[i]=now%2
        now = now >> 1
    return res

def BitsToValue(arr):
    n = len(arr)
    ans = 0
    for i in range(n):
        ans+= arr[i] * 2**i
    return ans

def ZipArray(a):
    aa = [[a[i],i]for i in range(n)]

    aa.sort(key = lambda x : x[0])
    for i in range(n):
        aa[i][0]=i+1
    aa.sort(key = lambda x : x[1])
    b=[aa[i][0] for i in range(len(a))]
    return b

def ValueToArray10(x, digit):
    ans = [0 for i in range(digit)]
    now = x
    for i in range(digit):
        ans[digit-i-1] = now%10
        now = now //10
    return ans

def Zeros(a,b):
    if(b<=-1):
        return [0 for i in range(a)]
    else:
        return [[0 for i in range(b)] for i in range(a)]

def AddV2(v,w):
    return [v[0]+w[0],v[1]+w[1]]

dir4 = [[1,0],[0,1],[-1,0],[0,-1]]


def clamp(x,y,z):
    return max(y,min(z,x))

class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
 
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
 
    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i
            

def Zaatsu(a):
    a.sort()
    now = a[0][0]
    od = 0
    for i in range(n):
        if(now==a[i][0]):
            a[i][0]=od
        else:
            now = a[i][0]
            od+=1
            a[i][0] = od
    
    a.sort(key = lambda x : x[1])
    return a

class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n+1)]
        self.rank = [0] * (n+1)

    
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    
    def same_check(self, x, y):
        return self.find(x) == self.find(y)


'''
def cmb(n, r, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % p

p = 2
N = 10 ** 6 + 2
fact = [1, 1]  
factinv = [1, 1]  
inv = [0, 1]  

for i in range(2, N + 1):
    fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)

'''

def rl(x):
    return range(len(x))












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

for i in range(m):
    p,q = list(map(int, input().split()))
    p-=1
    q-=1
    nb[p][q]=1
    nb[q][p]=1

import itertools
L = list(itertools.permutations(range(n)))
ans = 0
for i in L:
    if(i[0]!=0):
        continue
    ok = 1
    for j in range(1,n):
        if(not i[j] in nb[i[j-1]]):
            ok=0
            break
    if(ok==0):
        continue
    else:
        ans += 1
        
        
print(ans)

Solution (Python):
n,m = map(int,input().split())
edge = [[] for i in range(n)]
for i in range(m):
    x,y = map(int,input().split())
    edge[x-1].append(y-1)
    edge[y-1].append(x-1)
def dfs(visited,i):
    visited.append(i)
    if len(visited) == n:
        return 1
    count = 0
    for j in edge[i]:
        if j in visited:
            continue
        count += dfs(visited[:],j)
    return count
print(dfs([],0))

Solution (Python):
from collections import deque
import numpy as np
import math
import copy
import bisect  

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

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


q = deque()
ans = 0
visited = [False for i in range(N)]
visited[0] = True
q.append((0, visited))
while(len(q) > 0):
    
    tmp, visited = q.popleft()
    if not(False in visited):
        ans += 1
    for e in E[tmp]:
        if not visited[e]:
            tmp_visited = copy.deepcopy(visited)
            tmp_visited[e] = True
            
            q.append((e, copy.deepcopy(tmp_visited)))

print(ans)

Solution (Python):
import sys
import itertools
import copy

input = sys.stdin.readline

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    N, M = MI()
    numlist = [i for i in range(1, N)]
    mylist2 = [[0 for i in range(N)] for j in range(M)]
    result = 0
    for i in range(M):
        a, b = MI()
        mylist2[min(a, b) - 1][max(a, b) - 1] = 1
    for j in itertools.permutations(numlist, len(numlist)):
        mylist = copy.deepcopy(mylist2)
        index = 0
        past = 0
        for k in j:
            try:
                
                if mylist[min(past, k)][max(past, k)] == 1:
                    mylist[min(past, k)][max(past, k)] = 0
                    past =  k
                    index += 1
                else:
                    break
            except:
                if mylist[0][k] == 1:
                    mylist[0][k] = 0
                    past = k
                    index += 1
                else:
                    break
        if index == len(numlist):
            result += 1
    print(result)
    
main()

Solution (Python):
import itertools
N,M=map(int,input().split())
ki=[[]for i in range(N)]
for i in range(M):
 a,b=map(int,input().split())
 ki[a-1].append(b-1)
 ki[b-1].append(a-1)
ans=0
for v in itertools.permutations(range(1,N), N-1):
 path=0
 if v[0] in ki[0]:
  path+=1
 if N>2:
  for i in range(N-2):
   if v[i+1] in ki[v[i]]:
    path+=1
 if path==N-1:
  ans+=1
print(ans)

Solution (Python):

from collections import deque
from copy import deepcopy

def parse():
  N, M = map(int, input().split(" "))
  
  edges = [[] for n in range(N)]
  for m in range(M):
    a, b = map(int, input().split(" "))
    edges[a - 1].append(b - 1)
    edges[b - 1].append(a - 1)
  return N, M, edges

def main():
  N, M, edges = parse()
  

  
  stack = deque([(0, edges[0], [False for n in range(N)])])
  ans = 0
  while len(stack) > 0:
    i, paths, visited = stack.pop()
    visited[i] = True
    for path in paths:
      
      if not visited[path]:
        stack.append((path, edges[path], deepcopy(visited)))
    
    
    if not (False in visited):
      ans += 1

  print(ans)

if __name__ == "__main__":
  main()

Solution (Python):
from itertools import permutations
def main():
    N,M = map(int, input().split())
    edge = [[False]*N for _ in range(N)]
    for i in range(M):
        a,b = map(lambda x:x-1, map(int, input().split()))
        edge[a][b] = True
        edge[b][a] = True
    ans = 0
    for perm in permutations([i for i in range(1,N)]):
        arrived = [False]*N
        flag = False
        prev = 0
        for p in perm:
            
            if not edge[prev][p]:
                flag = True
                break
            
            else:
                
                if arrived[p]:
                    flag = True
                    break
                else:
                    arrived[p] = True
            prev = p
        if not flag:
            ans += 1
    print(ans)
main()

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


l=[[] for _ in range(n)]
for i in range(m):
    a,b=s[i][0],s[i][1]
    l[a-1].append(b)
    l[b-1].append(a)

def dfs(now, prev, visited):
    visited.append(now)
    if len(visited) == n:
        return 1
 
    ret = 0 
    for edge in l[now-1]:
        if edge == prev:
            continue
        if edge in visited:
            continue
 
        ret += dfs(edge, prev, visited[:])
 
    return ret 

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

Solution (Python):
import sys

import math
import itertools






n,m=map(int,input().split())
v=tuple(tuple(map(lambda x: int(x)-1,input().split())) for _ in range(m))

node=[[] for _ in range(n)]
for pair in v:
    node[pair[0]].append(pair[1])
    node[pair[1]].append(pair[0])
c=0
p=list(itertools.permutations(list(range(1,n))))
for res in p:
    for i in range(n-1):
        if i==0:
          if res[0] in node[0]:
            continue
          else:
            break
        if res[i] in node[res[i-1]]:
            continue
        else:
            break
    else:
        c+=1
print(c)

Solution (Python):
import itertools
N, M = map(int, input().split())
l = []
seq = []
for i in range(1,N+1):
  seq.append(i)
  i+=1
for _ in range(M):
    A = list(map(int, input().split()))
    l.append(A)
cnt = 0
for i in list(itertools.permutations(seq)):
  if i[0]!=1:
    continue
  for j in range(N-1):
    if sorted([i[j],i[j+1]]) in l:
      if j == N-2:
        cnt += 1
    else:
      break
print(cnt)

Solution (Python):
import itertools
N, M = map(int, input().split())
l = []
seq = []
for i in range(N):
  seq.append(i)
  i+=1
for _ in range(M):
    a,b = list(map(int, input().split()))
    l.append([a-1,b-1])
cnt = 0
for i in list(itertools.permutations(seq)):
  if i[0]!=0:
    continue
  for j in range(N-1):
    if sorted([i[j],i[j+1]]) in l:
      if j == N-2:
        cnt += 1
    else:
      break
print(cnt)

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


def dfs(now, visited):
    visited.append(now)
    if len(visited) == N:
        return 1

    ret = 0
    for edge in graph[now]:
        if edge in visited:
            continue
        ret += dfs(edge, visited[:])

    return ret


print(dfs(0, []))

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


def dfs(now, prev, visited):
    visited.append(now)
    if len(visited) == N:
        return 1

    ret = 0
    for edge in graph[now]:
        if edge == prev:
            continue
        if edge in visited:
            continue

        ret += dfs(edge, prev, visited[:])

    return ret


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

Solution (Python):
from collections import deque

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

stack = deque([0])
visited = [False]*n
visited[0] = True

def dfs(visited,stack):
    tmp = 0
    while stack:
        x = stack.pop()
        if all(visited):
            return 1
        for e in edge_li[x]:
            if visited[e]:
                continue
            visited[e]=True
            stack.append(e)
            tmp+=dfs(visited,stack)

            visited[e]=False
    return tmp

print(dfs(visited,stack))

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(1,n)):
    now = 0
    for nxt in p:
        if nxt not in G[now]: break
        now = nxt
    else:
        ans += 1
print(ans)

Solution (Python):
def root(lista, S, G, M, N, memory):
  if(S == G and memory == set(range(1, N+ 1))):
    return 1
  elif(S == G and memory != set(range(1, N+ 1))):
    return 0
  elif(lista == []):
    return 0
  else:
    roots = 0
    possibilities = 0
    possibleroots = []
    for i in range(M):
      if(S in lista[i]):
        q = list(filter(lambda x: x != S, lista[i])).pop()
        if(q in memory):
          continue
        else:
          possibleroots.append(q)
    if(possibleroots == []):
      return 0
    else:
      for q in possibleroots:
        newlista = list(filter(lambda x: x != {S, q}, lista))
        newmemory = memory| {q}
        
        roots+= root(newlista, q, G, M- 1, N, newmemory)
      return roots


N, M = map(int, input().split())
lista = []
for i in range(M):
  lista.append(set(map(int, input().split())))
  
ans = 0
for i in range(2, N+ 1):
  ans+= root(lista, 1, i, M, N, {1})
  
print(ans)

Solution (Python):
import itertools

N, M = map(int, input().split())
node_relationship = [set(map(int, input().split())) for _ in range(M)]
permutations_lis = list(itertools.permutations([x for x in range(1, N + 1)]))
ans = 0

for one_case in permutations_lis:
    if one_case[0] != 1:
        continue

    flg = True
    for i in range(len(one_case) - 1):
        if not flg:
            break
        tmp = {one_case[i], one_case[i + 1]}
        if not tmp in node_relationship:
            flg = False
    if flg:
        ans += 1

print(ans)

Solution (Python):
from itertools import permutations


def main():
    n, m = map(int, input().split())
    a = {tuple(int(i) - 1 for i in input().split()) for _ in range(m)}
    c = 0
    for per in permutations(range(1, n)):
        p = [0] + list(per)
        for i in range(n - 1):
            if (p[i], p[i + 1]) not in a and (p[i + 1], p[i]) not in a:
                break
        else:
            c += 1
    print(c)


if __name__ == '__main__':
    main()

Solution (Python):
import itertools

n, m = (int(x) for x in input().split())
li = []
for i in range(m):
    li.append([int(x) for x in input().split()])


paths = list(itertools.permutations([int(x) for x in range(1,n+1)]))



ans = 0
for path in paths:
    if path[0] != 1:
        continue
    flag = True
    for i in range(n-1):
        if path[i] < path[i+1]:
            a = path[i]
            b = path[i+1]
        else:
            b = path[i]
            a = path[i+1]
        if [a,b] not in li:
            flag = False
            break
    if flag:
        ans += 1
print(ans)

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

import itertools
np = [i for i in range(1,n)]
p = list(itertools.permutations(np))
ans = 0
for pi in p:
  flag = True
  sta = 0
  for j in range(n-1):
    if pi[j] not in graph[sta]:
      flag = False
      break
    else:
      sta = pi[j]
  if flag: ans += 1

print(ans)

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

import itertools
np = [i for i in range(1,n)]
p = list(itertools.permutations(np))
ans = 0
for pi in p:
  flag = True
  sta = 0
  for j in range(n-1):
    if pi[j] not in graph[sta]:
      flag = False
      break
    else:
      sta = pi[j]
  if flag:
    ans += 1

print(ans)