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
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LS()
    return l
sys.setrecursionlimit(1000000)
mod = 1000000007
dire4 = [(1,0), (0,1), (-1,0), (0,-1)]
dire8 = [(1, 0), (1, 1), (0, 1), (-1, 1), (-1, 0), (-1, -1), (0, -1), (1, -1)]

N, M = LI()
ab = LIR(M)

for i in range(M):
    ab[i] = [ab[i][0]-1, ab[i][1]-1]

edge = [[0]*N for i in range(N)]

for e in ab:
    edge[e[0]][e[1]] = edge[e[1]][e[0]] = 1

ans = 0

def make_permutation(li, r):
    if (r <= 0) or (r > len(li)):
        return []
    
    result = []
    _make_permutation(li, r, [], result)
    return result

def _make_permutation(li, r, out, result):
    if (r == 0):
        result.append(out)
        return

    for i, num in enumerate(li):
        _make_permutation(li[:i]+li[i+1:], r-1, out+[li[i]], result)

vs = list(range(1,N))
perm = make_permutation(vs, N-1)

for pe in perm:
    before = 0
    for num in pe:
        if (edge[before][num]):
            before = num
            continue
        else:
            break
    else:
        ans += 1

print(ans)

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

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

def dfs(v):
    if sum(visited) == N:
        return 1 
    
    ret = 0
    for u in to[v]:
        if not visited[u]:
            visited[u] = True
            ret += dfs(u)
            visited[u] = False  

    return ret


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

visited[0] = True
print(dfs(0))

Solution (Python):
import numpy as np
import copy


def visit(next_node, visited_nodes, adj_mat):
    assert next_node not in visited_nodes

    if len(visited_nodes) + 1 == len(adj_mat):
        
        return 1
    else:
        adj_nodes = np.argwhere(adj_mat[next_node].flatten() == 1)
        if len(adj_nodes) == 0:
            
            return 0
        else:
            n_paths = 0
            for adj_node in adj_nodes:
                if adj_node not in visited_nodes:
                    n_paths += visit(adj_node, visited_nodes +
                                     [next_node, ], adj_mat)
                else:
                    continue
            return n_paths


def main():
    N, M = map(int, input().split())
    adj_mat = np.zeros((N, N), dtype=np.int32)
    for _ in range(M):
        a, b = map(int, input().split())
        adj_mat[a-1][b-1] = 1
        adj_mat[b-1][a-1] = 1
    assert np.sum(adj_mat) == M * 2

    next_nodes = np.argwhere(adj_mat[0].flatten() == 1)
    n_paths = np.sum([visit(next_node, [0, ], adj_mat)
                      for next_node in next_nodes])

    print(n_paths)


if __name__ == '__main__':
    main()

Solution (Python):
from itertools import*
n,*t=map(int,open(0).read().split())
e={0}
for a in zip(t[1::2],t[2::2]):e|={a,a[::-1]}
print(sum(all(u in e for u in zip(t,t[1:]))for t in permutations(range(1,n+1))if t[0]<2))

Solution (Python):
from itertools import*
n,*t=map(int,open(0).read().split())
e={0}
for a in zip(t[1::2],t[2::2]):e|={a,a[::-1]}
print(sum(all(u in e for u in zip(t,t[1:]))for t in permutations(range(1,n+1))if t[0]<2))

Solution (Python):

from collections import defaultdict
import itertools

def main():
    node_num, edge_num = map(int, input().split())
    data = [list(map(int, input().split())) for i in range(edge_num)]
    edge_dic = defaultdict(set)
    for i in range(edge_num):
        a, b = data[i]
        edge_dic[a].add(b)
        edge_dic[b].add(a)

    ori_list = [i for i in range(2, node_num + 1)]
    ans = 0
    for root in list(itertools.permutations(ori_list, node_num - 1)):
        root = [1] + list(root)
        for i in range(node_num - 1):
            if root[i + 1] not in edge_dic[root[i]]:
                break
        else:
            ans += 1

    print(ans)




if __name__ == '__main__':
    main()

Solution (Python):
from itertools import permutations

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

L = [[False for j in range(N)] for i in range(N)]

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

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

ans = 0

for perm in P :
    perm = list(perm)
    
    for s,g in zip([0] + perm, perm) :
        if not L[s][g] :
            break
    else :
        ans += 1

print(ans)

Solution (Python):
import itertools
n, m = map(int, input().split())
e = set([tuple(sorted(map(int, input().split()))) for x in range(m)])
cnt = 0
for i in itertools.permutations(range(2, n+1), n-1):
    l = [1]+list(i)
    if sum(1 for x in range(n-1) if tuple(sorted(l[x: x+2])) in e) == n-1:
        cnt += 1
print(cnt)

Solution (Python):
inpl = lambda: list(map(int,input().split()))

def routes(start, tovisit):
	if len(tovisit) == 0:
		return 1
	else:
		ret = sum(routes(nextnode, tovisit - {nextnode}) for nextnode in neigh[start] & tovisit)
		if ret is None:
			return 0
		else:
			return ret

N, M = inpl()
neigh = [ set() for _ in range(N) ]
for _ in range(M):
	a, b = inpl()
	neigh[a-1].add(b-1)
	neigh[b-1].add(a-1)

print(routes(0,set(range(1,N))))

Solution (Python):
inpl = lambda: list(map(int,input().split()))

def routes(start, tovisit):
	if len(tovisit) == 0:
		return 1
	else:
		ret = sum(routes(nextnode, tovisit - {nextnode}) for nextnode in neigh[start] & tovisit)
		if ret is None:
			return 0
		else:
			return ret

N, M = inpl()
neigh = [ set() for _ in range(N) ]
for _ in range(M):
	a, b = inpl()
	neigh[a-1].add(b-1)
	neigh[b-1].add(a-1)

print(routes(0,set(range(1,N))))

Solution (Python):
inpl = lambda: list(map(int,input().split()))

def routes(start, tovisit):
	if len(tovisit) == 0:
		return 1
	else:
		ret = sum(routes(nextnode, tovisit - {nextnode}) for nextnode in neigh[start] & tovisit)
		if ret is None:
			return 0
		else:
			return ret

N, M = inpl()
neigh = [ set() for _ in range(N) ]
for _ in range(M):
	a, b = inpl()
	neigh[a-1].add(b-1)
	neigh[b-1].add(a-1)

print(routes(0,set(range(1,N))))

Solution (Python):
from itertools import permutations

N, M = map(int, input().split())
ab = [[int(_) for _ in input().split()] for _ in range(M)]
Graph = [[] for _ in range(N+1)]
cand = list(permutations(range(1, N+1), N))
ans = 0

for i in ab:
    Graph[i[0]].append(i[1])
    Graph[i[1]].append(i[0])

for i in cand:
    if i[0] != 1:
        break
    flag = True
    for j in range(len(i)-1):
        if not (i[j+1] in Graph[i[j]]):
            flag = False
            break
    
    if flag:
        ans += 1

print(ans)

Solution (Python):
from itertools import combinations, permutations
def inpl(): return list(map(int, input().split()))

N, M = inpl()
G = [[0]*(N+1) for _ in range(N+1)]

for _ in range(M):
    a, b = inpl()
    G[a][b] = 1
    G[b][a] = 1

ans = 0
for X in permutations(range(2, N+1)):
    a = 1
    for i in range(N-1):
        b = X[i]
        if G[a][b] == 0:
            break
        a = b
    else:
        ans += 1

print(ans)

Solution (Python):
import sys
import heapq
input = sys.stdin.readline

N, M, = map(int, input().split())
L = [[int(v) for v in input().split()] for _ in range(M)]
t = [set() for _ in range(N)]

for i in range(M):
    x, y = L[i]
    
    t[x - 1].add(y - 1)
    t[y - 1].add(x - 1)

ans = 0
def dfs(now, visited):
    global ans
    
    if len(visited) == N:
        ans += 1
        return
    
    for v in t[now]:
        if v not in visited:
            dfs(v, visited + [v])

    return

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

Solution (Python):


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


def dfs(cur, path):
    if len(path) == N:
        return 1
    else:
        ret = 0
        for neighbor in Neighbor_list[cur]:
            if neighbor not in path:
                next_list = path[:]
                next_list.append(neighbor)
                ret += dfs(neighbor, next_list)
        return ret


print(dfs(0, [0]))

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

def checkpath(nodes,E,current):
    next = []
    newnodes = nodes.copy()
    newnodes[current] = 0

    for e in E[current]:
        if newnodes[e]:
            next.append(e)

    if len(next) == 0:
        if sum(newnodes) == 0:
            return 1
        else:
            return 0
    else:
        return sum([checkpath(newnodes,E,e) for e in next])

nodes = [1]*(n+1)
nodes[0] = 0
print(checkpath(nodes,edge,1))

Solution (Python):
ans=0
def DFS(v,visited):
    global ans
    if visited == [1]*N:
        ans += 1
        return
    for next in edge[v]:
        if visited[next] != 1:
            visited[next] = 1
            DFS(next,visited)
            visited[next] = 0 
    return

N, M = map(int,input().split())
edge = [[] for _ in range(N)]
for i in range(M):
    a, b = map(int, input().split())
    edge[a-1].append(b-1)
    edge[b-1].append(a-1)
visited = [0 for _ in range(N)]
visited[0]=1
DFS(0,visited)
print(ans)

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

nums = [i for i in range(n)]
for num in itertools.permutations(nums):
    if(num[0] != 0):
        continue
    flag = True
    for i in range(n - 1):
        if(d[num[i]][num[i+1]] != 1):
            flag = False
            break
    if(flag):
        ans += 1

print(ans)

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

def dfs(x, t):
  if t==n:
    return 1

  visited[x] = 1
  cur = 0
  for nx in edge[x]:
    if not visited[nx]:
      cur += dfs(nx, t+1)
  visited[x] = 0
  return cur

print(dfs(0, 1))

Solution (Python):
from collections import deque
from itertools import permutations as perm

N,M = map(int, input().split())
A = {}
for i in range(M):
    a,b = map(int, input().split())
    if a not in A:
        A[a] = {}
    if b not in A:
        A[b] = {}
    A[a][b] = A[b][a] = 1

ans = 0
for lst in perm([i for i in range(2,N+1)]):
    tmp = 1
    for i in range(N-1):
        if lst[i] not in A[tmp]:
            break
        tmp = lst[i]
    else:
        ans += 1
print(ans)

Solution (Python):
from itertools import permutations

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

for i in range(M):
    a, b = map(int, input().split())
    gr |= {(a-1,b-1),(b-1,a-1)}

ans = 0
for p in permutations(range(N)):
    if p[0]==0:
        cnt = 0
        cntp = 0
        for i in range(N-1):
            cnt += 1
            if (p[i],p[i+1]) in gr:
                cntp += 1
            else:
                break
        if cnt == cntp:
            ans += 1
print(ans)

Solution (Python):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, M = MAP()
ab = [LIST() for _ in range(M)]

graph = [[0]*N for _ in range(N)]
for a, b in ab:
	graph[a-1][b-1] = 1
	graph[b-1][a-1] = 1

ans = 0
for i in permutations(range(1, N)):
	i = list(i)
	i.insert(0, 0)
	
	for j in range(N-1):
		if graph[i[j]][i[j+1]] != 1:
			break
	else:
		ans += 1
print(ans)

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

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

link = []

for i in range(n):
    num = i + 1
    link.append([])
    for a_i, b_i in zip(a, b):
        if a_i == num:
            link[i].append(b_i)
        if b_i == num:
            link[i].append(a_i)
pass_count = 0

hie_ind = [0 for i in range(n)]
pass_his = [1]
finish = False
while True:
    if len(pass_his) == n:
        pass_count += 1
        pass_his.pop()

    hierarchy = len(pass_his) - 1
    now_n = pass_his[-1]-1
    now_ind = hie_ind[hierarchy]

    while True:
        if now_ind > (len(link[now_n]) - 1):
            if now_n == 0:
                finish = True
                break
            pass_his.pop()
            hie_ind[hierarchy] = 0

            hierarchy = len(pass_his) - 1
            now_n = pass_his[-1]-1
            now_ind = hie_ind[hierarchy]
        else:
            break
    if finish:
        break

    cand_n = link[now_n][now_ind]

    if not(cand_n in pass_his):
        pass_his.append(cand_n)
    hie_ind[hierarchy] += 1

print(pass_count)

Solution (Python):
from itertools import permutations

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

perm = permutations(list(range(2, n+1)), n - 1)

ans = 0
for p in perm:
    flag = True
    for i in range(n-1):
        if i == 0:
            if not [1, p[i]] in ab:
                flag = False
                break
        else:
            if not ([p[i-1], p[i]] in ab or [p[i], p[i-1]] in ab):
                flag = False
                break
    if flag: ans += 1
print(ans)

Solution (Python):
import itertools
N,M = map(int,input().split())
edges = set()
for _ in range(M):
  a,b = map(int,input().split())
  edges.add((a,b))
  edges.add((b,a))

answer = 0

for p in itertools.permutations(range(1,N+1)):
  if p[0] != 1:
    continue
  bl = True
  for i in range(N-1):
    if (p[i], p[i+1]) not in edges:
      bl = False
      break
  if bl:
    answer += 1

print(answer)

Solution (Python):
from collections import defaultdict

n, m = map(int, input().split())
p = defaultdict(set)
for _ in range(m):
  ai, bi = map(int, input().split())
  p[ai].add(bi)
  p[bi].add(ai)

cnt = 0
cand_list = [(1, set(range(2, n + 1)))]

while(len(cand_list) != 0):
  c = cand_list.pop(0)

  if len(c[1]) == 0:
    cnt += 1
  for x in c[1] & p[c[0]]:
    remain = c[1].copy()
    remain.remove(x)
    cand_list.append((x, remain))

print(cnt)

Solution (Python):
import copy
n, m = [ int(v) for v in input().split() ]
connect_matrix = [[ 0 for i in range(n)] for j in range(n)]

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


one_path_list = [[0]]
for i in range(n-1):
    next_path_list = []

    for j in range(len(one_path_list)):

        next_point_list = [ k for k in range(n) if connect_matrix[one_path_list[j][-1]][k] == 1 and k not in one_path_list[j]]

        for k in range(len(next_point_list)):
            next_path_list.append(copy.deepcopy(one_path_list[j])+[next_point_list[k]])

    one_path_list = next_path_list 

print(len(one_path_list))

Solution (Python):
n,m=map(int,input().split())
l=[list(map(int,input().split())) for _ in range(m)]
p=[list() for i in range(n+1)]
for a,b in l:
	p[a].append(b)
	p[b].append(a)
q=[(1,[1])]
ans=0
while len(q)!=0:
	x,v=q.pop(0)
	if len(v)==n:
		ans+=1
		continue
	for i in p[x]:
		if i in v:continue
		q.append((i,v+[i]))
print(ans)

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

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

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

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

print(dfs(0, used))

Solution (Python):
nmax=8

def dfs(v,n,visited):
    all_visited=True
    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 graph[v][i]==False:
            continue
        
        if visited[i]:
            continue
        
        visited[i]=True
        
        ans += dfs(i,n,visited)
        
        visited[i]=False
    return ans

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

graph=[]
for i in range(n):
    graph.append([False]*n)

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

visited=[]
for _ in range(n):
    visited.append(False)

visited[0]=True
print(dfs(0,n,visited))

Solution (Python):
import sys
from collections import deque

sys.setrecursionlimit(4100000)


def inputs(num_of_input):
    ins = [input() for i in range(num_of_input)]
    return ins


def solve(N, M, inputs):
    relations = {}
    visited_all = (2 ** N) - 1
    for i in range(1, N + 1):
        relations[i] = []

    for i in inputs:
        [parent, child] = string_to_int(i)
        relations[parent].append(child)
        relations[child].append(parent)

    routes = 0
    queue = deque([[1, 0]])
    while len(queue) > 0:
        [node, visited] = queue.popleft()

        if visited & (1 << (node - 1)) != 0:
            continue

        visited = visited + (1 << (node - 1))

        if visited == visited_all:
            routes += 1
            continue

        for next in relations[node]:
            queue.append([next, visited])
    return routes


def string_to_int(string):
    return list(map(lambda x: int(x), string.split()))


if __name__ == "__main__":
    [N, M] = string_to_int(input())
    ret = solve(N, M, inputs(M))
    print(ret)

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

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

V = [0] * N
V[0] = 1
def dfs(n, V):
    if all([v == 1 for v in V]):
        return 1

    ans = 0
    for e in G[n]:
        if V[e] == 1:
            continue
        V[e] = 1
        ans += dfs(e, V)
        V[e] = 0
    
    return ans

print(dfs(0, V))

Solution (Python):
import sys
sys.setrecursionlimit(10000)
n,m=map(int,input().split())
bra=[set() for _ in range(n)]
for i in range(m):
    a,b=map(int,input().split())
    bra[a-1].add(b-1)
    bra[b-1].add(a-1)

visit=[1]+[0]*(n-1)

cnt=[]
def dfs(a,visit):
    if visit==[1]*n:
        cnt.append(1)
        return 
    for e in bra[a]:
        if visit[e]==0:
            visit[e]=1

            dfs(e,visit)
            visit[e]=0  
    return 
dfs(0,visit)
print(len(cnt))

Solution (Python):
from collections import deque

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

for i in range(M):
  a, b = map(int,input().split())
  edge[a-1].append(b-1)
  edge[b-1].append(a-1)
  
def DFS(n):
  global count
  if len(visited) == N:
    count += 1
    return
  else:
    for i in edge[n]:
      if not(i in visited):
        visited.append(i)
        DFS(i)
        visited.remove(i)
    return

DFS(0)

print(count)

Solution (Python):
n,m=map(int,input().split())
l=list(range(2,n+1))
v=[[] for i in range(1+n)]
for i in range(m):
    a,b=map(int,input().split())
    v[a].append(b)
    v[b].append(a)

def check(ls):
    fr=1
    for to in ls:
        if int(to) not in v[fr]:
            return 0
        fr=int(to)
    return 1

def gen(ls):
    if not ls:
        return [[]]
    return [[a]+b for i,a in enumerate(ls) for b in gen(ls[:i]+ls[i+1:])]
    
print(sum([check(i) for i in gen(l)]))

Solution (Python):
import itertools
n,m=map(int,input().split())
lst=[]
for i in range(m):
    lst+=[list(map(int,input().split()))]



pair=[[0]*n for i in range(n)]
for i,j in lst:
    pair[i-1][j-1]=1
    pair[j-1][i-1]=1


def keiro(a):
    count=0
    for i in range(n-1):
        if pair[a[i]-1][a[i+1]-1]==0:
            break
    else:
        count+=1
    return count
cn=0
b=[i for i in range(2,n+1)]
for i in list(itertools.permutations(b)):
    a=[1]+list(i)
    if keiro(a)==1:
        cn+=1

print(cn)

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

edges = [set() for _ in range(N + 1)]
for a, b in AB:
	edges[a] |= {b}
	edges[b] |= {a}

count = 0
def dfs(current, visited):
	global count
	if N == len(visited):
		count += 1
		return
	for _next in edges[current]:
		if _next not in visited:
			dfs(_next, visited | {_next})

dfs(1, {1})

print(count)

Solution (Python):


import copy

n,m = list(map(int,input().split()))
rinset = [[0]*(n+1) for _ in range(n+1)]
for _ in range(m):
    a,b = list(map(int,input().split()))
    rinset[a][b]=b
    rinset[b][a]=a
cnt = 0
def solve(start,visitted):
    global cnt
    visitted = copy.deepcopy(visitted)
    visitted.append(start)
    if len(visitted) == n:
        cnt+=1
        return
    next_start=[i for i in rinset[start] if (i>1 and i not in visitted)]
    for i in next_start:
        solve(i,visitted)

solve(1,[])
print(cnt)

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

visited = [False] * N

def dfs(v, count):
    if visited.count(True) == N:
        return 1
    else:
        ans = 0
        for i in g[v]:
            if not visited[i]:
                visited[i] = True
                ans += dfs(i, count+1)
                visited[i] = False
        return ans

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

Solution (Python):
def dfs(num,s):
    cnt = 0
    s.add(num)
    if(len(s)==N):
        s.discard(num)
        return 1
    for x in li[num]:
        if(x not in s):
            cnt += dfs(x,s)
    s.discard(num)
    return cnt

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

sets = set()
ans = dfs(1,sets)
print(ans)

Solution (Python):
from itertools import permutations

N, M = map(int, input().split())
E = []
for _ in range(M):
    a, b = map(int, input().split())
    E.append((a, b))
    E.append((b, a))
ans = 0
for p in permutations(range(2, N+1)):
    perm = [1] + list(p)
    for i in range(N-1):
        if (perm[i], perm[i+1]) not in E:
            break
    else:
        ans += 1
print(ans)

Solution (Python):
import pdb

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

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

visited = set()
ans = 0

def dfs(num):
    global ans
    
    visited.add(num)
    if len(visited) == N:
        ans += 1
        return 
    
    for next_num, connected in enumerate(mat[num]):
        if not connected:
            continue
        if next_num in visited:
            continue
        visited.add(next_num)
        dfs(next_num)
        visited.remove(next_num)
    return

def main():
    dfs(0)
    print(ans)

main()

Solution (Python):
import itertools

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 itertools

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

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

ans = 0


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

print(ans)

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

graph = [[0] * N for _ in range(N)]
for u, v in edges:
    graph[u - 1][v - 1] = 1
    graph[v - 1][u - 1] = 1

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

def dfs(s):    
    if all(visited):
        return 1

    cnt = 0
    for i in range(N):
        if visited[i] or graph[s][i] != 1:
            continue
            
        visited[i] = True
        cnt += dfs(i)
        visited[i] = False
        
    return cnt

print(dfs(0))

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

graph = [[None] * N for _ in range(N)]
for u, v in edges:
    graph[u - 1][v - 1] = True
    graph[v - 1][u - 1] = True

def dfs(s):    
    if all(visited):
        return 1

    cnt = 0
    for i in range(N):
        if graph[s][i] is None:
            continue

        if visited[i]:
            continue
            
        visited[i] = True
        cnt += dfs(i)
        visited[i] = False
        
    return cnt

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

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

graph = [[False] * N for _ in range(N)]
for u, v in edges:
    graph[u - 1][v - 1] = True
    graph[v - 1][u - 1] = True

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

def dfs(s):    
    if all(visited):
        return 1

    cnt = 0
    for i in range(N):
        if not graph[s][i]:
            continue
        
        if visited[i]:
            continue
            
        visited[i] = True
        cnt += dfs(i)
        visited[i] = False
        
    return cnt

print(dfs(0))

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

graph = [[False] * N for _ in range(N)]
for u, v in edges:
    graph[u - 1][v - 1] = True
    graph[v - 1][u - 1] = True

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

def dfs(s):    
    if all(visited):
        return 1

    cnt = 0
    for i in range(N):
        if visited[i]:
            continue
            
        if not graph[s][i]:
            continue
            
        visited[i] = True
        cnt += dfs(i)
        visited[i] = False
        
    return cnt

print(dfs(0))

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

graph = [[0] * N for _ in range(N)]
for u, v in edges:
    graph[u - 1][v - 1] = 1
    graph[v - 1][u - 1] = 1

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

def dfs(s):    
    if all(visited):
        return 1

    cnt = 0
    for i in range(N):
        if visited[i] or graph[s][i] != 1:
            continue
            
        visited[i] = True
        cnt += dfs(i)
        visited[i] = False
        
    return cnt

print(dfs(0))

Solution (Python):
import sys
sys.setrecursionlimit(10000000)

def dfs(v, 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 graph[v][i] == False:
			continue
		if visited[i]:
			continue
		
		visited[i] = True
		ret += dfs(i, visited)
		visited[i] = False
	
	return ret

N, M = [int(x) for x in input().split()]
graph = [[False] * N for _ in range(N)]

for i in range(M):
	A, B = [int(x) for x in input().split()]
	graph[A-1][B-1] = graph[B-1][A-1] = True

visited = [False] * N

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

Solution (Python):
import itertools

n, m=map(int, input().split())
branch=[]
for i in range(m):
    a, b=map(int, input().split())
    branch.append((a, b))
seq=[]
for i in range(2, n+1):
    seq.append(i)
ans=0
permutation=list(itertools.permutations(seq))
for i in range(len(permutation)):
    number_list=list(map(int, permutation[i]))
    start=1
    flag=1
    for j in range(n-1):
        if not ((start, number_list[j]) in branch or (number_list[j], start) in branch):
            flag=0
            break
        start=number_list[j]
    if flag:
        ans=ans+1
print(ans)

Solution (Python):
from itertools import permutations

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

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

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

P = permutations([0] + [i for i in range(1,N)])

ans = 0

for perm in P :
    visited = [0 for i in range(N)]
    visited[0] = 1
    for i in range(N-1) :
        if perm[i+1] not in L[perm[i]] :
            break
         
        if visited[perm[i+1]] :
            break
        
        visited[perm[i+1]] = 1
    
    if sum(visited) == N :
        ans += 1

print(ans)

Solution (Python):
def DFS(now, visited):

    if len(visited) == n:
        ans.append(1)
        return

    for i in graph[now]:
        if not i in visited:
            DFS(i, visited + [i])


n, m = map(int, input().split())
graph = [[] for i in range(n)]
ans = []

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

DFS(0,[0])

print(len(ans))