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 collections import defaultdict,deque
import itertools

N, M = map(int, input().split())
d = defaultdict(list)
for i in range(M):
    a, b = map(int, input().split())
    d[a].append(b)
    d[b].append(a)

p=list(itertools.permutations([i for i in range(2,N+1)]))
now=1
ans=0
for i in p:
    now=1
    frag=True
    for g in range(N-1):
        if i[g] in d[now]:
            now = i[g]
        else:
            frag=False
            break
    if frag:
        ans+=1
print(ans)

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

from collections import deque
from copy import copy,deepcopy
from itertools import permutations

def myinput():
    return map(int,readline().split())

def mycol(data,col):
    return [ row[col] for row in data ]

n,m = myinput()
ab = [ list(myinput()) for _ in range(m) ]

v = list(range(1,n+1))
p = list(permutations(v))


count = 0
for s in p:
    
    if s[0]!=1:
        pass
    else:
        flag = True
        for j in range(n-1):
            v_tmp = s[j]
            v_next = s[j+1]
            c = [v_tmp,v_next]
            d = [v_next,v_tmp]
            if ( c in ab ) or ( d in ab ):
                pass
            else:
                flag = False

        if flag:
            count += 1
        else:
            pass
    

print(count)

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

i_i = lambda: int(i_s())
i_l = lambda: list(map(int, stdin.readline().split()))
i_s = lambda: stdin.readline().rstrip()

N, M = i_l()
matrix = [[0] * N for _ in range(N)]

for i in range(M):
    a, b = i_l()
    matrix[a-1][b-1] = 1
    matrix[b-1][a-1] = 1

cnt = 0
for x in itertools.permutations(range(N)):
    if x[0] != 0:
        break
    factor = 1
    for i in range(N-1):
        factor *= matrix[x[i]][x[i+1]]
    cnt += factor

print(cnt)

Solution (Python):
import itertools

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

ans = 0
for t in itertools.permutations(range(2, N + 1)):
    tmp = 1
    for x in t:
        if x not in lst[tmp]:
            break
        tmp = x
    else:
        ans += 1
print(ans)

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

import numpy as np
graph = np.zeros((n,n))
for i in range(m):
    a,b = map(int,input().split())
    graph[a-1][b-1] = graph[b-1][a-1] = 1

from itertools import permutations
nv = [i for i in range(1,n)]
def main():
    def checkroot(root,graph):
        if graph[0][root[0]] == 0:
            return 0
        for i in range(1,len(root)):
            if graph[root[i]][root[i-1]]==0:
                return 0
        return 1

    ans = 0
    for root in permutations(nv):
        if checkroot(root,graph)==1:
            ans += 1
    print(ans)

if __name__ == "__main__":
    main()

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

ans=0
def dfs(start,finish):
    global ans
   
    if len(finish)==n:
        ans+=1
    else:
        for i in adlist[start-1]:
            if i not in finish:
                
                
                
                finish_1 = set([i]) | finish
                
                dfs(i,finish_1)

adlist=[]
for h in range(n):    
    adlist.append([])
for j in range(m):
    x=ab[j][0]
    y=ab[j][1]
    adlist[x-1].append(y)
    adlist[y-1].append(x)
finish=set()
finish.add(1)

dfs(1,finish)
print(ans)

Solution (Python):

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


ans = 0
for x in itertools.permutations(range(N)):
    now = 0
    if x[0] == 0:
        
        for e in x[1:]:
            if e not in graph[now]:
                break
            now = e
        else:
            ans += 1
print(ans)

Solution (Python):
from itertools import permutations

def check(adj, pat):
    pos = 1
    for p in pat:
        if p not in adj[pos]:
            return 0
        else:
            pos = p
    return 1

def main():
    n, m = [int(i) for i in input().split()]
    adj = {i+1:[] for i in range(n)}
    for _ in range(m):
        a, b = [int(i) for i in input().split()]
        adj[a].append(b)
        adj[b].append(a)

    res = 0
    for t in permutations(range(2, n+1)):
        res += check(adj, t)
    print(res)

if __name__ == '__main__':
    main()

Solution (Python):
import itertools

n, m = map(int, input().split())
graph = {i + 1 : set() for i in range(n)}
for i in range(m):
    a, b = map(int, input().split())
    graph[a] |= set([b])
    graph[b] |= set([a])
count = 0
node = [i + 2 for i in range(n - 1)]
for i in itertools.permutations(node):
    route = [1] + list(i)
    flag = True
    for j in range(n - 1):
        if route[j + 1] not in graph[route[j]]:
            flag = False
            break
    if flag == True:
        count += 1
print(count)

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

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

if __name__ == "__main__":
    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)



def dfs(x, y, l):
    if y == n - 1:
        return 1
    else:
        ans = 0
        for i in range(len(g[x])):
            if not g[x][i] in l:
                l2 = l + [g[x][i]]
                ans += dfs(g[x][i], y + 1, l2)
        return ans

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

Solution (Python):
import itertools

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

node = [i for i in range(2,n+1)]
permutations_node = itertools.permutations(node)
ans = 0

for one_node in permutations_node:
    start = 1
    memo = []
    for x in one_node:
        for edge_x, edge_y in edges:
            if edge_x == start and edge_y == x and x not in memo:
                memo.append(x)
                start = x
            if edge_x == x and edge_y == start and x not in memo:
                memo.append(x)
                start = x
                
    if len(memo) == n-1:
        ans += 1
    
print(ans)

Solution (Python):
from itertools import permutations


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 exists(self, path):
        for i in range(len(path)-1):
            if not path[i+1] in self.adjacency_dict[path[i]]:
                return False
        return True


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

    graph = Graph()
    for v in range(1, N+1):
        graph.add_vertex(v)
    for e in edges:
        graph.add_edge(e[0], e[1])

    count = 0
    for path in permutations(range(2, N+1)):
        path = list(path)
        path.insert(0, 1)
        if graph.exists(path):
            count += 1
    print(count)


if __name__ == "__main__":
    main()

Solution (Python):
from itertools import permutations


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 exists(self, path):
        for i in range(len(path)-1):
            if not path[i+1] in self.adjacency_dict[path[i]]:
                return False
        return True


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

    graph = Graph()
    for v in range(1, N+1):
        graph.add_vertex(v)
    for e in edges:
        graph.add_edge(e[0], e[1])

    count = 0
    for path in permutations(range(2, N+1)):
        path = list(path)
        path.insert(0, 1)
        if graph.exists(path):
            count += 1
    print(count)


if __name__ == "__main__":
    main()

Solution (Python):
import math
import copy
from copy import deepcopy
import sys
import fractions

from functools import reduce

import decimal
import heapq
import collections
import itertools
from operator import mul

sys.setrecursionlimit(100001)







def getInputInt():
    inputNum = int(input())
    return inputNum


def getInputListInt():
    outputData = []
    inputData = input().split()
    outputData = [int(n) for n in inputData]

    return outputData


def getSomeInputInt(n):
    outputDataList = []
    for i in range(n):
        inputData = int(input())
        outputDataList.append(inputData)

    return outputDataList


def getSomeInputListInt(n):
    inputDataList = []
    outputDataList = []
    for i in range(n):
        inputData = input().split()
        inputDataList = [int(n) - 1 for n in inputData]
        outputDataList.append(inputDataList)

    return outputDataList




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

d = getSomeInputListInt(m)

path = []
for p in itertools.permutations(range(1, n), n-1):
    tmp = (0,) + p
    path.append(tmp)


def pathsearch(a, b):
    flga = False
    for tmp_d in d:
        if a in tmp_d and b in tmp_d:
            flga = True
            break

    return flga


ans = 0
for p in path:
    flg = True
    for i in range(1, n, 1):
        tmp = pathsearch(p[i - 1], p[i])
        if not tmp:
            flg = False
            break

    if flg:
        ans += 1

print(ans)

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

Solution (Python):
import itertools
n,m=map(int,input().split())
G=[[0]*n for i in range(n)]
for i in range(m):
  a,b=map(int,input().split())
  G[a-1][b-1]=1
  G[b-1][a-1]=1
S=""
for i in range(1,n):
  S=S+str(i)
ans=0
for x in itertools.permutations(S):
  a=0
  if G[0][int(x[0])]==0:
    a=1
  for i in range(n-2):
    if G[int(x[i])][int(x[i+1])]==0:
      a=1
  if a==0:
    ans=ans+1
print(ans)

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

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

Solution (Python):
f=lambda:map(int,input().split())
n,m=f()
g=[[0]*n for _ in range(n)]
for i in range(m):
  a,b=f(); g[a-1][b-1]=g[b-1][a-1]=1
import itertools as it
c=0
for t in it.permutations(range(1,n)):
  p,d=0,1
  for q in t: d*=g[p][q]; p=q
  c+=d
print(c)

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

Solution (Python):
n,m=map(int,input().split())
ab=[list(map(int,input().split())) for i in range(m)]
import itertools
ans=0
l = [i for i in range(1,n+1)]
p = itertools.permutations(l, n)
for v in p:
  v=list(v)
  if v[0]!=1:
    continue
  x=0
  for i in range(n-1):
    w=v[i:i+2]
    w.sort()
    if w not in ab:
      x=1
      break
  if x==0:
    ans+=1
print(ans)

Solution (Python):
import  itertools 
n,m=map(int,input().split())
edges=[[0]*n  for i in range(n)]

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


l=[i for i in range(n)]
p_obj=itertools.permutations(l)
ans=0
for i in p_obj:
    
    if i[0]>0:
        break
    flag=True
    for j in range(1,n):
        if edges[i[j-1]][i[j]]==0:
            flag=False
            break
    if flag:
        ans+=1
print(ans)

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

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

ans = 0


def dfs(pos, cnt, his):
    global ans
    his[pos] = 1
    if cnt == n:
        if sum(his) == n:
            ans += 1
        return

    for next in data[pos]:
        dfs(next, cnt+1, his[:])


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

Solution (Python):

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



adjl=[[0 for i in range(n)] for j in range(n)]

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

import itertools
l=[i for i in range(1,n+1)]
ans=0

for v in itertools.permutations(l):
    
    
    flag=True
    if v[0]!=1 :
        continue
    for i in range(n-1):
        if adjl[v[i]-1][v[i+1]-1]==0:
            flag=False
            break
    if flag:
        ans+=1
print(ans)

Solution (Python):
import sys 
sys.setrecursionlimit(1000000)
n, m = map(int, input().split())
graph = [[] for _ in range(n)]
for _ in range(m):
  a, b = map(lambda x:int(x)-1, input().split())
  graph[a] += [b]
  graph[b] += [a]

used = [0]*n
global ans 
ans = 0
def dfs(u):
  global ans
  used[u] = 1
  if sum(used) == n:
    ans += 1
    return 
  
  for v in graph[u]:
    if used[v] == 0:
      used[v] = 1
      dfs(v)
      used[v] = 0 

  return 

dfs(0)
print(ans)

Solution (Python):
import numpy as np

n, m = map(int, input().split())
graph = np.zeros((n, n), dtype=np.int8)
for _ in range(m):
    a, b = map(int, input().split())
    graph[a-1, b-1] = 1
    graph[b-1, a-1] = 1

def dfs(node, visited):
    if sum(visited) == n:
        return 1
    res = 0
    for i in range(n):
        if graph[node, i] and not visited[i]:
            visited[i] = 1
            res += dfs(i, visited)
            visited[i] = 0
    return res

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

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

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

def search(node: int, visited: set):
    visited.add(node)
    if len(visited) == N:
        return 1

    ans = 0
    for next_node in edge_dict[node]:
        if not next_node in visited:
            ans += search(next_node, visited.copy())
    return ans

visited = set()
node = 1
print(search(node, visited))

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

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

count = 0
visited = [0]*n
def dfs(initial,graph,visited):
    global count
    all_visited = True
    visited[initial] = 1
    for i in visited:
        if i == 0:
            all_visited = False 
            
    if all_visited == True:
        count += 1
        return 0
    
    for i in range(n):
        if graph[initial][i] ==1:
            if visited[i] == 0:
                visited[i] = 1
                dfs(i,graph  ,visited)
                visited[i] = 0
    return count


print(dfs(0 ,graph , visited ))

Solution (Python):
import itertools

n, m = map(int, input().split())
path = [[False] * n for _ in range(n)]

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


ans = 0
x = list(itertools.permutations(range(1,n)))
for i in range(len(x)):
    u = list(x[i])
    w = [0] + u
    ok = 0
    for j in range(n-1):
        if path[w[j]][w[j+1]]:
            ok += 1
        else:
            break

    if ok == n-1:
        
        ans += 1

print(ans)

Solution (Python):


import sys
 
stdin = sys.stdin
inf = 1 << 60
mod = 1000000007
 
ni      = lambda: int(ns())
nin     = lambda y: [ni() for _ in range(y)]
na      = lambda: list(map(int, stdin.readline().split()))
nan     = lambda y: [na() for _ in range(y)]
nf      = lambda: float(ns())
nfn     = lambda y: [nf() for _ in range(y)]
nfa     = lambda: list(map(float, stdin.readline().split()))
nfan    = lambda y: [nfa() for _ in range(y)]
ns      = lambda: stdin.readline().rstrip()
nsn     = lambda y: [ns() for _ in range(y)]
ncl     = lambda y: [list(ns()) for _ in range(y)]
nas     = lambda: stdin.readline().split()

from itertools import permutations

n, m = na()
ab = nan(m)
g = [[] for _ in range(n)]
for i in range(m):
    a, b = ab[i]
    a -= 1
    b -= 1
    g[a].append(b)
    g[b].append(a)

def dfs(i, c, p):
    if p[c] == i:
        if c == n - 1:
            return 1
    else:
        return 0
    res = 0
    for j in g[i]:
        res = max(res, dfs(j, c + 1, p))
    return res

ans = 0
for p in permutations(range(n)):
    if p[0] == 0:
        ans += dfs(0, 0, p)

print(ans)

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

def onestrokepath(start,visited=[]):
    flag=0
    count=0
    for next in hen[start]:
        if not next in visited:
            flag=1
            count+=onestrokepath(next,visited+[next])
    if flag==0:
        check=[i for i in range(0,N)]
        visited.sort()
        if check==visited:
            return 1
        else:
            return 0
    return count

print(onestrokepath(0,[0]))

Solution (Python):
import copy
from collections import deque
cnt = 0
def dfs(G,s,n,seen):
    global cnt
    li = copy.copy(seen)
    li.append(s)
    if len(li) == n:
        cnt += 1
        return 0
    for x in G[s]:
        if x in li:
            continue
        dfs(G,x,n,li)

N,m = map(int,input().split())
seen = []
G = [[] for _ in range(N)]
for i in range(m):
    a,b = map(lambda x:int(x)-1,input().split())
    G[a].append(b)
    G[b].append(a)
dfs(G,0,N,seen)
print(cnt)

Solution (Python):
import copy
from collections import deque
cnt=0
def dfs(G,s,N,seen):
    global cnt
    li=copy.copy(seen)
    li.append(s)
    if(len(li)==N):
        cnt+=1
        return 0
    for x in G[s]:
        if x in li:
            continue
        dfs(G,x,N,li)
        
N,M=map(int,input().split())
seen=[]
G=[[] for i in range(N)]
for i in range(M):
    a,b=map(lambda x:int(x)-1,input().split())
    G[a].append(b)
    G[b].append(a)
dfs(G,0,N,seen)
print(cnt)

Solution (Python):
from itertools import permutations
def check(i,j):
    if j==N-2 and x[j] in G[i]:
        return True
    if x[j] in G[i]:
        return check(x[j],j+1)
    return False
    
N,M = map(int,input().split())
G = {i:[] for i in range(1,N+1)}
for _ in range(M):
    a,b = map(int,input().split())
    G[a].append(b)
    G[b].append(a)
cnt = 0
for x in permutations(range(2,N+1),N-1):
    if check(1,0):
        cnt += 1
print(cnt)

Solution (Python):
from itertools import permutations
n,m=map(int,input().split())
g=[[] for i in range(n)]
for _ in range(m):
  u,v=map(int,input().split())
  g[u-1].append(v-1)
  g[v-1].append(u-1)
ans=0
for v in permutations([int(i) for i in range(n)],n):
  if v[0]!=0:
    continue
  for i in range(n-1):
    if not v[i+1] in g[v[i]]:
      break
  else:
    ans+=1
print(ans)

Solution (Python):
def bit_DP(N,Adj):
    dp=[[0]*N for i in range(1<<N)]
    dp[1][0]=1
    for S in range(1<<N):
        for v in range(N):
            if (S&(1<<v))==0:
                continue
            sub=S^(1<<v)
            
            for u in range(N):
                if (sub&(1<<u)) and (Adj[u][v]):
                    dp[S][v]+=dp[sub][u]
    ans=sum(dp[(1<<N)-1][u] for u in range(1,N))
    return ans
def main():
    N,M=map(int,input().split())
    Adj=[[0]*N for i in range(N)]
    for _ in range(M):
        a,b=map(int,input().split())
        Adj[a-1][b-1]=1
        Adj[b-1][a-1]=1
    ans=bit_DP(N,Adj)
    print(ans)
if __name__=='__main__':
    main()

Solution (Python):


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

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

def dfs(v, visited):
  all_visited = True
  for i in range(N):
    if not visited[i]:
      all_visited = False
      
  if all_visited:
    return 1
  
  ret = 0
  for i in range(N):
    if not graph[v][i]: continue
    if visited[i]: continue
    
    visited[i] = True
    ret += dfs(i, visited)
    visited[i] = False
  
  return ret

visited = [False] * N
visited[0] = True
ans = dfs(0, visited)
print(ans)

Solution (Python):
import sys
INF = 10**10
MOD = 10**9 + 7
sys.setrecursionlimit(100000000)
from functools import lru_cache
from itertools import permutations

def main():
    n,m = map(int,input().split())
    dist = [[1] * n for _ in range(n)]
    for _ in range(m):
        a,b = map(int,input().split())
        a -= 1
        b -= 1
        dist[a][b] = 0
        dist[b][a] = 0
    
    cnt = 0
    for ptr in permutations(range(1,n)):
        flag = True
        if  dist[0][ptr[0]]:
            continue

        for i in range(n - 2):
            if dist[ptr[i]][ptr[i + 1]]:
                flag = False
                break
        
        if flag:
            cnt += 1
    
    print(cnt)

if __name__=='__main__':
    main()

Solution (Python):
import itertools

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

perms = itertools.permutations(range(1, N+1))
ans = 0
for perm in perms:
  if perm[0] != 1:
    continue
  is_goal = True
  for i in range(N-1):
    a = perm[i]
    b = perm[i+1]
    if not a < b:
      a, b = b, a
    if not [a, b] in ab:
      is_goal = False
  if is_goal:
    ans += 1

print(ans)

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

Solution (Python):
printn = lambda x: print(x,end='')
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True 
BIG = 10**18
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)

def dfs(k,dep):
    if dep==n:
        return 1
    sm = 0
    for i in dst[k]:
        if used[i]:
            continue
        used[i] = True
        sm += dfs(i,dep+1)
        used[i] = False
    return sm

n,m = inm()
dst = {}
for i in range(m):
    a,b = inm()
    if a not in dst:
        dst[a] = {}
    dst[a][b] = 1
    if b not in dst:
        dst[b] = {}
    dst[b][a] = 1
used = [False]*(n+1)
used[1] = True
print(dfs(1,1))

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

ans = 0



def dfs(pos, visit):
    global l, ans
    f = True
    visit.append(pos)
    for d in l[pos]:
        if (d in visit):
            continue
        f = False
        dfs(d, visit.copy())

    if (f):
        if (len(visit) == N):
            ans += 1


dfs(0, [])
print(ans)

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

connect = [[0 for _ in range(n)] for _ in range(n)]
for a, b in edge:
    connect[a-1][b-1] = 1
    connect[b-1][a-1] = 1

import itertools
ans = 0
for l in itertools.permutations(range(1, n)):
    ok = True
    pre = 0
    for x in l:
        if connect[pre][x] == 0:
            ok = False
            break
        pre = x
    if ok:
        ans += 1
print(ans)

Solution (Python):
N, M = map(int, input().split())
E = [[0] * N for i in range(N)] 
for i in range(M):
  a_i, b_i = map(int, input().split())
  a_i = a_i - 1
  b_i = b_i - 1
  E[a_i][b_i] = 1
  E[b_i][a_i] = 1

visited = [0]*N

def dfs(n, depth):
  if visited[n]: 
    return 0
  
  if depth == N:
    return 1
  
  visited[n] = 1
  
  ans = 0
  for next_n in range(N):
    if E[n][next_n]:
      ans += dfs(next_n, depth+1)
  
  visited[n] = 0
  return ans

print(dfs(0,1))

Solution (Python):
N, M = map(int, input().split())
root = {i: [] for i in range(N)}
for i in range(M):
  a, b = map(int, input().split())
  root[a-1].append(b-1)
  root[b-1].append(a-1)
fact = 1
for i in range(N-1):
  fact *= (i+1)
realcnt = 0
for i in range(fact):
  p = [i for i in range(1, N)]
  L = []
  for j in range(N-1):
    L.append(i % (j + 1))
    i //= (j + 1)
  LL = [0]
  for j in range(N-1):
    LL.append(p[L[N-2-j]])
    p.remove(p[L[N-2-j]])
  cnt = 1
  for j in range(N-1):
    if LL[j+1] in root[LL[j]]:
      cnt += 1
  if cnt == N:
    realcnt += 1
print(realcnt)

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

root_dict = {str(i) : [] for i in range(1, N+1)}
for i in range(M):
    root = input().split()
    root_dict[root[0]] = root_dict[root[0]] + [root[1]]
    root_dict[root[1]] = root_dict[root[1]] + [root[0]]
result = 0
numbers = [str(i) for i in range(2, N+1)]
numbers = ''.join(numbers)

for order in itertools.permutations(numbers, N-1):
    prev_num = "1"
    flag = True
    for num in order:
        if num not in root_dict[prev_num]:
            flag = False
            break
        prev_num = num
    if flag:
        result += 1

print(result)

Solution (Python):
from itertools import permutations

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

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

for a, b in ab:
    graph[a - 1].append(b - 1)
    graph[b - 1].append(a - 1)

perm = [i for i in range(N)]

ans = 0

for p in permutations(perm):
    
    if p[0] != 0:
        break
    flag = False
    for i in range(len(p) - 1):
        if not p[i + 1] in graph[p[i]]:
            flag = True
            break

    if not flag:
        
        ans += 1

print(ans)

Solution (Python):
import itertools


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

ans = 0
for p in itertools.permutations(range(1, n + 1)):
    if p[0] != 1:
        break

    for i in range(n - 1):
        for ai, bi in ab:
            if (p[i] == ai and p[i + 1] == bi
                    or p[i] == bi and p[i + 1] == ai):
                break
        else:
            break
    else:
        ans += 1

print(ans)

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

graph = [[0 for j in range(N)] for i in range(N)]

for e in E:
    graph[e[0] - 1][e[1] - 1] = 1
    graph[e[1] - 1][e[0] - 1] = 1

res = 0

dp = [[0 for j in range(N)] for i in range(2**N)]
dp[1][0] = 1

for i in range(2**N):
    for j in range(N):
        for k in range(N):
            if not (i >> k & 1) and graph[j][k]:
                dp[(i)|(1 << k)][k] += dp[i][j]

print(sum(dp[-1]))

Solution (Python):
class Graph(): 
    def __init__(self,n,edge):
        self.n = n
        self.graph = [[] for _ in range(n)]
        self.deg = [0 for _ in range(n)]
        for e in edge:
            self.graph[e[0] - 1].append(e[1] - 1)
            self.graph[e[1] - 1].append(e[0] - 1)
            self.deg[e[0] - 1] += 1
            self.deg[e[1] - 1] += 1

from itertools import permutations

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

G = Graph(N, E)
res = 0

for p in permutations(range(N)):
    if p[0] != 0:
        continue
    for i in range(N - 1):
        if not p[i + 1] in G.graph[p[i]]:
            break
    else:
        res += 1

print(res)

Solution (Python):
import itertools

def resolve():
    n, m = map(int, input().split())
    S = [[0]*n for i in range(n)]

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

    ans = 0
    for p in itertools.permutations(range(n)):
        if p[0] != 0:
            break
        tmp = 1
        for i in range(n-1):
            tmp *= S[p[i]][p[i+1]]
        ans += tmp

    print(ans)

if __name__ == '__main__':
    resolve()

Solution (Python):
from itertools import permutations
N, M, *L = map(int, open(0).read().split())
dic = [[] for i in range(N+1)]
for a, b in zip(*[iter(L)]*2):
  dic[a].append(b)
  dic[b].append(a)

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