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 sys
sys.setrecursionlimit(4100000)

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

 
def main():
    input =  sys.stdin.readline
    n, m = map(int, input().split())
    e = [list(map(int, input().split())) for i in range(m)]
    g = [[False for j in range(n)] for i in range(n)]
    for i, j in e:
        g[i-1][j-1] = True
        g[j-1][i-1] = True
    visited = [False for i in range(n)]
    visited[0] = True
    
    print(Dfs(g, 0, n, visited))

if __name__ == "__main__":
    main()

Solution (Python):
import sys
import copy
def solve():
    sys.setrecursionlimit(100000)
    input = sys.stdin.readline
    N, M = map(int, input().split())
    adjM = [[0] * N for i in range(N)] 
    for i in range(M):
        a, b = map(int, input().split())
        adjM[a - 1][b - 1] = 1
        adjM[b - 1][a - 1] = 1

    arrived = [False] * N
    ans = dfs(0, adjM, arrived, N)
    print(ans)

def dfs(now, adjM, arrived, N):
    arrived[now] = True
    if arrived == [True] * N:
        return 1
    
    cnt = 0
    for i in range(N):
        if adjM[now][i] == 1 and not arrived[i]:
            cnt += dfs(i, adjM, copy.deepcopy(arrived), N)
    
    return cnt


if __name__ == '__main__':
    solve()

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

def DFS(now,v_set):
  if v_set.count(True) == n:
    return 1
  if all(v_set[i] for i in path[now]):
    return 0
  c = 0
  for v in path[now]:
    if v_set[v]==False:
      v_set[v] = True
      c += DFS(v,v_set)
      v_set[v] = False
  return c
  
v_set = [False]*n
v_set[0] = True
print(DFS(0,v_set))

Solution (Python):
from collections import deque
from copy import copy as dc
import sys

def main():
    input = sys.stdin.readline
    n, m = map(int, input().split())
    ab = [list(map(int, input().split())) for i in range(m)]
    g = [[] for i in range(n+1)]
    for i in ab:
        g[i[0]].append(i[1])
        g[i[1]].append(i[0])
    que = deque()
    que.append([1,-1,0,set([1])])
    ans = 0
    while que:
        v, p, cnt, check = que.popleft()
        if cnt >= n - 1:
            if len(check) == n:
                ans += 1
            continue
        for nv in g[v]:
            if nv == p:
                continue
            a = dc(check)
            a.add(nv)
            que.append([nv, v, cnt+1, a])
    print(ans)

if __name__ == "__main__":
    main()

Solution (Python):
def perm(k,x):
    v=[]
    for i in range(x):
        c=k%x+2
        if c not in v:
            v.append(c)
            k//=x
        else:
            return []
    return v       

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

if N==2:
    ans=1 if e[1][2] else 0
else:
    ans=0
    for k in range((N-1)**(N-1)):
        v=perm(k,N-1)
        if v and e[1][v[0]]:
            f=True
            for j in range(N-2):
                if not e[v[j]][v[j+1]]:
                    f=False
                    break
                if j==N-3:
                    ans+=1

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

def dfs(x,s,flags):
    vlist = adj[x]
    flags = list(flags)
    flags[x] = False
    flags = tuple(flags)
    if sum(flags) == 0:
        return 1
    s = 0
    for v in vlist:    
        if flags[v]:
            s += dfs(v,s,flags)
    return s        

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

Solution (Python):
import itertools

n,m=map(lambda x: int(x), input().split())

path={}
for i in range(n+1):
    path[i]=[]

for _ in range(m):
    a,b=map(lambda x: int(x), input().split())
    path[a].append(b)
    path[b].append(a)

node_list=list(itertools.permutations(range(2, n+1)))
ans=0
for node_tup in node_list:
    flag=True
    if node_tup[0] not in path[1]:
        continue
    for i in range(n-2):
        if node_tup[i+1] not in path[node_tup[i]]:
            flag=False
            break
    ans+=flag
print(ans)

Solution (Python):
N,M = map(int,input().split())
Branch = [list(map(int,input().split())) for i in range(M)]
Visited = [0 for i in range(N)]
Visited[0] = 1
Glaph = [[0 for i in range(N)] for i in range(N)] 
for b in Branch:
  Glaph[b[0]-1][b[1]-1] = 1; Glaph[b[1]-1][b[0]-1] = 1
def dfs(v,N,Visited):
  flag = True
  for i in range(N):
    if Visited[i] == 0:
      flag = False
  if flag:
    return 1
  
  ret = 0
  
  for i in range(N):
    if Glaph[v][i] == False: continue
    if Visited[i]: continue    
    Visited[i] = 1    
    ret+=dfs(i,N,Visited)
    Visited[i]= 0
  return ret

print(dfs(0,N,Visited ))

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

ed=[0]*n
ed[0]=1
ans=[0]*n

def f(x):
    if 0 not in ed:
        ans[x]+=1
        return
    for a in g[x]:
        if ed[a]==0:
            ed[a]=1
            f(a)
            ed[a]=0
f(0)
print(sum(ans))

Solution (Python):
from itertools import permutations
import sys

sys.setrecursionlimit(10**7)
N, M = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(M)]

adjm = [[0]*N for _ in range(N)]
for abi in ab:
    adjm[abi[0]-1][abi[1]-1] = 1
    adjm[abi[1]-1][abi[0]-1] = 1

cnt = 0
order = list(range(1, N))
for v in permutations(order):
    last = 0
    for i in v:
        if adjm[last][i] == 1:
            last = i
        else:
            break
    else:
        cnt += 1
print(cnt)

Solution (Python):
from sys import stdin
N = int()
memo = {}
graph = []


def dfs(e, done):
    if (1 << N) - 1 == done:
        return 1
    key = (e, done)
    if key in memo:
        return memo[key]
    ret = 0
    for s in graph[e]:
        if done >> s & 1:
            continue
        done ^= 1 << s
        ret += dfs(s, done)
        done ^= 1 << s
    memo[key] = ret
    return ret


def main():
    lines = stdin.readlines()
    global N
    N, M = map(int, lines[0].split())
    global graph
    graph = [[] for i in range(N)]
    for i in range(1, M + 1):
        a, b = map(lambda x: int(x) - 1, lines[i].split())
        
        graph[a].append(b)
        graph[b].append(a)
    print(dfs(0, 1))
    return


main()

Solution (Python):
from sys import stdin


def dfs(e, ans, done, N, graph):
    if (1 << N) - 1 == done:
        ans += 1
        return ans
    for s in graph[e]:
        if done >> s & 1:
            continue
        done ^= 1 << s
        ans = dfs(s, ans, done, N, graph)
        done ^= 1 << s
    return ans


def main():
    lines = stdin.readlines()
    N, M = map(int, lines[0].split())
    graph = [[] for i in range(N)]
    for i in range(1, M + 1):
        a, b = map(lambda x: int(x) - 1, lines[i].split())
        
        graph[a].append(b)
        graph[b].append(a)
    ans = 0
    print(dfs(0, ans, 1, N, graph))
    return


main()

Solution (Python):
from sys import stdin


def dfs(e, ans, graph, done, N):
    if sum(done) == N:
        ans += 1
        return ans
    for s in graph[e]:
        if not done[s]:
            done[s] = True
            ans = dfs(s, ans, graph, done, N)
            done[s] = False
    return ans


def main():
    lines = stdin.readlines()
    N, M = map(int, lines[0].split())
    graph = [[] for i in range(N)]
    for i in range(1, M + 1):
        a, b = map(int, lines[i].split())
        
        graph[a - 1].append(b - 1)
        graph[b - 1].append(a - 1)
    ans = 0
    done = [False] * N
    done[0] = True
    print(dfs(0, ans, graph, done, N))
    return


main()

Solution (Python):
from sys import stdin


def dfs(e, ans, graph, done, N):
    if sum(done) == N:
        ans += 1
        return ans
    for s in graph[e]:
        if not done[s]:
            done[s] = True
            ans = dfs(s, ans, graph, done, N)
            done[s] = False
    return ans


def main():
    lines = stdin.readlines()
    N, M = map(int, lines[0].split())
    graph = []
    for i in range(N):
        graph.append([])
    for i in range(1, M + 1):
        a, b = map(int, lines[i].split())
        
        graph[a - 1].append(b - 1)
        graph[b - 1].append(a - 1)
    ans = 0
    done = [False] * N
    done[0] = True
    print(dfs(0, ans, graph, done, N))
    return


main()

Solution (Python):
import itertools

n,m = map(int,input().split())
E = [list(map(int,input().split())) for i in range(m)]
G = [[] for i in range(n)]
for i in range(m):
    G[E[i][0]-1] += [E[i][1]-1]
    G[E[i][1]-1] += [E[i][0]-1]

ans = 0
for p in itertools.permutations(range(1,n)):
    if p[0] in G[0] and all([p[i] in G[p[i-1]] for i in range(1,n-1)]):
        ans += 1

print(ans)

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

matrix = [[0 for _ in range(N)] for _ in range(N)]

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

def func(p, l):
    '''
    count = 0
    if Pから行ける場所が探索済み:
        if 全頂点探索済み:
            count = 1
        else:
            count = 0
    else:
        foreach Pから行ける未探索頂点:
            count += func(p, l)

    '''
    count = 0
    if all(l):
        count = 1
    else:
        for np, e in enumerate(matrix[p]):
            if e == 0:
                continue
            if p == np:
                continue
            if l[np] == True:
                continue

            l[np] = True
            count += func(np, l)
            l[np] = False

    return count

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


print(func(0, l))

Solution (Python):
N,M = map(int,input().split())
G = {}
for _ in range(M):
    a,b = map(int,input().split())
    if a not in G:
        G[a] = []
    G[a].append(b)
    if b not in G:
        G[b] = []
    G[b].append(a)
hist = [0 for _ in range(N+1)]
stack = [1]
hist[1] = 1
cnt = 0
F = {}
while stack:
    cur = stack[-1]
    if cur not in F:
        F[cur] = G[cur][:]
        F[cur] = iter(F[cur])
    F1 = list(F[cur])

    if len(F1)>0:
        F[cur] = iter(F1)
        x = next(F[cur])
        if hist[x]==0:
            stack.append(x)
            hist[x] = 1
        else:
            if sum(hist)==N:
                cnt += 1
                hist[cur]=0
                del F[cur]
                stack.pop()
    else:


        if sum(hist)==N:
            cnt += 1
        hist[cur]=0
        del F[cur]
        stack.pop()
print(cnt)

Solution (Python):
import itertools
import collections

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

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

cnt = 0

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

print(cnt)

Solution (Python):
import sys
from collections import deque, defaultdict

input = sys.stdin.readline


class AtCoder:
    def main(self):
        N, M = map(int, input().split())
        edges = defaultdict(set)
        for _ in range(M):
            a, b = map(int, input().split())
            edges[a].add(b)
            edges[b].add(a)

        deq = deque()
        deq.append((1, 1, {1}))

        ans = 0
        while deq:
            node = deq.popleft()
            node_num = node[0]
            cnt = node[1]
            already = node[2]

            if cnt == N:
                ans += 1
                continue

            already.add(node_num)

            for n in edges[node_num]:
                if n not in already:
                    deq.append((n, cnt + 1, already.copy()))

        print(ans)



if __name__ == '__main__':
    AtCoder().main()

Solution (Python):
from sys import stdin
mat = [[False] * 8 for _ in range(8)]
def dfs(point, visited):
        all_visited = True
        n = len(visited)
        for i in range(n):
            if visited[i] == False:
                all_visited = False
        if all_visited:
            return 1
        ans = 0
        for i in range(n):
            
            
            if mat[point][i] == True and visited[i] ==False:
                
                visited[i] = True
                ans += dfs(i, visited)
                visited[i] = False
        return ans
def main():
    n, m = list(map(int, input().split()))
    
    for _ in range(m):
        a, b = list(map(int, input().split()))
        a = a - 1
        b = b - 1
        mat[a][b] = True
        mat[b][a] = True
    
    v = [False] * n
    v[0] = True
    print(dfs(0, v))

if __name__ == '__main__':
    main()

Solution (Python):
from itertools import permutations
N,M=map(int,input().split())
l=[[] for _ in range(N)]
for _ in range(M):
  x,y=map(int,input().split())
  l[x-1].append(y-1)
  l[y-1].append(x-1)

res=0
for i in permutations(range(2,N+1)):
  s='1'
  for j in i:
    s+=str(j)
  ans=True
  for k in range(N-1):
    ss=int(s[k])-1
    st=int(s[k+1])-1
    if st not in l[ss]:
      ans=False
  if ans:
    res+=1
print(res)

Solution (Python):

import sys
import itertools
def solve(N: int, M: int, a: "List[int]", b: "List[int]"):
    all_per = itertools.permutations(range(2,N+1))
    
    matrix = [[0]*N for _ in range(N)]

    for aa,bb in zip(a,b):
        matrix[aa-1][bb-1] = 1
        matrix[bb-1][aa-1] = 1
    answer = 0
    for per in all_per:
        if matrix[0][per[0]-1] == 0:
            continue
        for i in range(N-2):
            if matrix[per[i]-1][per[i+1]-1] == 0:
                break
        else:
            answer += 1

    print(answer)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  
    M = int(next(tokens))  
    a = [int()] * (M)  
    b = [int()] * (M)  
    for i in range(M):
        a[i] = int(next(tokens))
        b[i] = int(next(tokens))
    solve(N, M, a, b)

if __name__ == '__main__':
    main()

Solution (Python):
n, m = map(int, input().split())
a_and_b = [list(map(int, input().split())) for _ in range(m)]
point = [[] for _ in range(n)]
reached = [False for _ in range(n)]
answer = 0
for i in range(m):
    for j in range(n):
        if a_and_b[i][0] == j+1:
            point[j].append(a_and_b[i][1])
        if a_and_b[i][1] == j+1:
            point[j].append(a_and_b[i][0])


def dfs(start_point=0):
    global answer
    if not (False in reached):
        answer += 1
    for k in point[start_point]:
        if reached[k-1] is False:
            reached[k-1] = True
            dfs(start_point=k-1)
            reached[k-1] = False


reached[0] = True
dfs(start_point=0)
print(answer)

Solution (Python):
def slove():
    import sys
    import bisect
    import collections
    import copy
    import fractions
    import heapq
    input = sys.stdin.readline
    n, m = list(map(int, input().rstrip('\n').split()))
    d = collections.defaultdict(list)
    for i in range(m):
        a, b = list(map(int, input().rstrip('\n').split()))
        d[a-1] += [b-1]
        d[b-1] += [a-1]

    ql = collections.deque()
    ql.append([0, [0]])
    cnt = 0
    while True:
        if len(ql) != 0:
            qp, ls = ql.popleft()
            for v in d[qp]:
                if v not in ls:
                    tls = copy.deepcopy(ls)
                    tls.append(v)
                    if len(tls) < n:
                        ql.append([v, tls])
                    else:
                        cnt += 1
        else:
            break
    print(cnt)


if __name__ == '__main__':
    slove()

Solution (Python):

cnt=0 
ans=0 
from collections import defaultdict 
from collections import Counter 
def check(arr): 
    c=Counter(arr)
    for i in range(n):
        if c[i]!=1:
            return 0 
    return 1 


class Graph: 

	def __init__(self,vertices): 
		
		self.V= vertices 
		
		
		self.graph = defaultdict(list) 

	
	def addEdge(self,u,v): 
		self.graph[u].append(v) 
	def printAllPathsUtil(self, u, d, visited, path):
	   
		
		visited[u]= True
		path.append(u) 
		global ans 
		
		
		if u ==d: 
		   
		    if check(path): 
		        ans+=1 
		else: 
			
			
			for i in self.graph[u]: 
				if visited[i]==False: 
					self.printAllPathsUtil(i, d, visited, path) 
					
		
		path.pop() 
		visited[u]= False


	
	def printAllPaths(self,s, d): 

		
		visited =[False]*(self.V) 

		
		path = [] 

		
		self.printAllPathsUtil(s, d,visited, path) 




n,m=map(int,input().split())
g = Graph(n)
for i in range(m): 
    a,b=map(int,input().split())
    g.addEdge(a-1,b-1)
    g.addEdge(b-1,a-1)
s = 2 ; d = 3
s=0 
for d in range(0,n): 
    g.printAllPaths(s, d) 
print(ans)

Solution (Python):
class Graph:
    def __init__(self):
        n, m = map(int, input().split())

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

        self.cnt = 0
        self.depth = 0
        self.ds = [-1] * n

    def solve(self, u):
        self.ds[u] = self.depth
        if self.ds.count(-1) == 0:
            self.cnt += 1
            return

        self.depth += 1
        for v in self.adj[u]:
            if self.ds[v] == -1:
                self.solve(v)
                self.ds[v] = -1
        self.depth -= 1


def main():
    graph = Graph()
    graph.solve(0)
    print(graph.cnt)


if __name__ == "__main__":
    main()

Solution (Python):
class Graph:
    def __init__(self, n, adj):
        self.adj = adj
        self.cnt = 0
        self.depth = 0
        self.ds = [-1] * n

    def solve(self, u):
        self.ds[u] = self.depth
        if self.ds.count(-1) == 0:
            self.cnt += 1
            return

        self.depth += 1
        for v in self.adj[u]:
            if self.ds[v] == -1:
                self.solve(v)
                self.ds[v] = -1
        self.depth -= 1


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

    graph = Graph(n, adj)
    graph.solve(0)
    print(graph.cnt)


if __name__ == "__main__":
    main()

Solution (Python):
from copy import deepcopy

cnt = 0
depth = 0


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

    def f(u, d):
        global cnt, depth
        cp = deepcopy(d)
        cp[u] = depth
        if cp.count(-1) == 0:
            cnt += 1
        else:
            vs = adj[u]
            depth += 1
            for v in vs:
                if cp[v] == -1:
                    f(v, cp)
            depth -= 1

    f(0, [-1] * n)

    print(cnt)


if __name__ == "__main__":
    main()

Solution (Python):
from itertools import permutations

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

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

Solution (Python):
def dfs(curr, visit_state, adj_list, count, num_vertex):
    if count == num_vertex:
        return 1
    if all(visit_state[i] for i in adj_list[curr]) and count != num_vertex:
        return 0
    result = 0
    for nb in adj_list[curr]:
        if not visit_state[nb]:
            visit_state[nb] = True
            result += dfs(nb, visit_state, adj_list, count + 1, num_vertex)
            visit_state[nb] = False
    return result


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

Solution (Python):
N,M=map(int,input().split())
AB=[list(map(int,input().split())) for i in range(M)]
c=[[0]*N for i in range(N)]
for a,b in AB:
    c[a-1][b-1]=c[b-1][a-1]=1
from itertools import permutations
r=0
for n in permutations(range(1,N)):
    n=[0]+list(n)
    x=1
    for i in range(N-1):
        if not c[n[i]][n[i+1]]:
            x=0
    r+=x
print(r)

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

Graph = [[0]*N for _ 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
  
A = []
for i in range(1,N): A.append(i)

ans = 0
Comb = list(itertools.permutations(A))
for i in range(len(Comb)):
  tmp = list(Comb[i])
  
  judge = 1
  for j in range(len(tmp)):
    if(j == 0): judge = judge*Graph[0][tmp[j]]
    else: judge = judge*Graph[tmp[j-1]][tmp[j]]
  if(judge == 1): ans += 1
 
print(ans)

Solution (Python):
import itertools
n,m=map(int,input().split())
l=[list(map(int,input().split())) for _ in range(m)]
p=list(itertools.permutations(list(range(2,n+1))))
ans=0
for i in p:
    tmp=1
    for j in range(n-1):
        if [tmp,i[j]] in l or [i[j],tmp] in l:
            tmp=i[j]
        else:break
        if j==n-2:ans+=1
print(ans)

Solution (Python):
import copy

N,M = map(int,input().split())
t_dict = dict()
for _ in range(M):
    a,b = map(int,input().split())
    try:
        t_dict[a] += [b]
    except KeyError:
        t_dict[a] = [b]
        
    try:
        t_dict[b] += [a]
    except KeyError:
        t_dict[b] = [a]
        

origin = [1]
new_origin = []
for one in t_dict[1]:
    new_origin.append(origin+[one])

for _ in range(N-2):
    origin = copy.deepcopy(new_origin)
    new_origin = []
    for one in origin:
        for two in t_dict[one[-1]]:
            if two  in one :
                pass
            else:
                new_origin.append(one+[two])
                
print(len(new_origin))

Solution (Python):
from collections import defaultdict


def c():
    n, m = map(int, input().split())
    graph = defaultdict(list)
    for i in range(m):
        a, b = map(int, input().split())
        graph[a].append(b)
        graph[b].append(a)
    stack = []
    count = 0

    stack.append((1, set()))

    while stack:
        val, visited = stack.pop()
        visited.add(val)
        if len(visited) == n:
            count += 1
            continue

        for g in graph[val]:
            if g not in visited:
                stack.append((g, set(visited)))

    print(count)


if __name__ == '__main__':
    c()

Solution (Python):
import itertools

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

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

per = list(itertools.permutations(range(N)))

count = 0

for x in per:
    if x[0] != 0:
        continue
    det = 0
    for k in range(N-1):
        if x[k+1] in con[x[k]]:
            continue
        else:
            det = -1
            break
    if det == 0:
        count += 1

print(count)

Solution (Python):
def dfs(visited, s):
    visited = visited[:]  
    global ans
    visited[s] = True
    for t in graph[s]:  
        if not visited[t]:  
            dfs(visited, t)

    
    if all(visited):
        ans += 1


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

graph = [[] for _ in range(N)]
visited = [False]*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
dfs(visited, 0)

print(ans)

Solution (Python):
def dfs(visited, s):
    visited = visited[:]
    global ans
    visited[s] = True
    for t in graph[s]:
        if not visited[t]:
            dfs(visited, t)
    if all(visited):
        ans += 1


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

graph = [[] for _ in range(N)]
visited = [False] * 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
dfs(visited, 0)

print(ans)

Solution (Python):
n,m=map(int,input().split())
lis=[[0 for i in range(n)] for _ in range(n)]
for i in range(m):
	x,y=map(int,input().split())
	lis[x-1][y-1]=1
	lis[y-1][x-1]=1
s=""
k=[]
import itertools
for i in range(n):
	s+=str(i)
for i in itertools.permutations(s):
	k.append(i)
ans=0
for i in range(len(k)):
	if k[i][0]!="0":
		continue
	for j in range(n-1):
		if lis[int(k[i][j])][int(k[i][j+1])]==0:
			break
		elif j==n-2:
			ans+=1
print(ans)

Solution (Python):
def dfs(visited, s):  
    global ans
    visited[s] = True
    for t in graph[s]:
        if not visited[t]:
            dfs(visited[:], t)
    if all(visited):
        ans += 1


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

graph = [[] for _ in range(N)]
visited = [False] * 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
dfs(visited, 0)

print(ans)

Solution (Python):
from itertools import permutations
N, M = map(int, input().split())
T=[[]*N for _ in range(N)]
for _ in range(M):
  i ,j = map(int,input().split())
  T[i-1].append(j-1)
  T[j-1].append(i-1)

def main():
  ans = 0
  for p in permutations(range(1,N)): 
    c=0
    for n in p:
      if n not in T[c]:
        break
      c=n
    else:
      ans += 1
  print(ans)

if __name__ == "__main__":
  main()

Solution (Python):
import itertools

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

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

  
L=[i for i in range(1,N+1)]

ans=0
for v in itertools.permutations(L,len(L)):
  sw=1
  
  if v[0]!=1:
    continue
  for i in range(len(v)-1):
    if C[v[i]][v[i+1]]==0:
      sw=0
      break
  if sw==1:
    ans+=1
print(ans)

Solution (Python):
def main():
    N, M = (int(i) for i in input().split())
    G = [set() for _ in range(N+1)]
    for m in range(M):
        a, b = (int(i) for i in input().split())
        G[a].add(b)
        G[b].add(a)
    
    from itertools import permutations
    trial_path = (p for p in permutations(range(2,N+1),N-1))

    def exist_path(st,path):
        for p in path:
            if p in G[st]: st = p
            else: return False
        else: 
            return True

    ans = 0
    for path in trial_path:
        if exist_path(1,path):
            ans += 1
    print(ans)

if __name__ == '__main__':
    main()

Solution (Python):
N,M = tuple(map(int,input().split()))
from collections import defaultdict
graph = defaultdict(list)
for i in range(M):
  a,b = tuple(map(int,input().split()))
  graph[a].append(b)
  graph[b].append(a)
  

queue = [(1,set())]
res = 0
while queue:
  now,prevs = queue.pop()
  
  if len(prevs) == N-1:
      res += 1
      continue
  for next_node in graph[now]:
    
    if next_node not in prevs:
      queue.append((next_node, prevs|{now}))
print(res)

Solution (Python):
import sys

stdin = sys.stdin

ns = lambda : stdin.readline().rstrip()
ni = lambda : int(ns())
na = lambda : list(map(int, stdin.readline().split()))

sys.setrecursionlimit(10**6)

def main():
  n, m = na()
  graph = [[] for _ in range(n + 1)]
  for _ in range(m):
    a, b = na()
    graph[a] += [b]
    graph[b] += [a]
  
  def dfs(e, reach):
    if all(reach):
      return True

    ret = 0
    for e in graph[e]:
      if reach[e - 1]:
        continue
      reach[e - 1] = True
      ret += dfs(e, reach)
      reach[e - 1] = False
    return ret

  reach = [False] * n
  reach[0] = True
  print(dfs(1, reach))

main()

Solution (Python):
def bfs(u):
  if used.count(True) == N:
    res[0] += 1
    return
  for v in adj[u]:
    if used[v]:
      continue
    used[v] = True
    bfs(v)
    used[v] = False

N, M = map(int, input().split())
adj = [[] for i in range(N)]
for i in range(M):
  u, v = map(lambda x: int(x)-1, input().split())
  adj[u].append(v)
  adj[v].append(u)

used = [False for i in range(N)]
used[0] = True
res = [0]
bfs(0)

print(res[0])

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

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

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


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

ans = 0

for i in permutations(range(1, N)):
    here = 0
    for j in i:
        if j not in ver[here]:
            break
        here = j
    else:
        ans += 1

print(ans)

Solution (Python):
from itertools import permutations
n, m = map(int, input().split())
d = [[] for _ in range(n)]
ans = 0
for i in range(m):
  a, b = map(int, input().split())
  d[a - 1].append(b - 1)
  d[b - 1].append(a - 1)
l = permutations(range(1, n))
for i in l:
  pre = 0
  c = 0
  for j in i:
    if not j in d[pre]:
      break
    c += 1
    pre = j
  if c == n-1:
    ans += 1
print(ans)

Solution (Python):
def dfs(v,N,visited):
  if sum(visited) == len(visited):
    return 1
  
  ret =0
  for i in range(N):
    if graph[v][i] == 0:
      continue
    if visited[i]:
      continue
    
    visited[i] = 1
    ret += dfs(i,N,visited)
    visited[i] = 0
    
  return ret


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

for mi in range(m):
  a,b = map(int,input().split())
  graph[a-1][b-1] = 1
  graph[b-1][a-1] = 1
  
visited = [0]*n
visited[0]= 1
print(dfs(0,n,visited))