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

input_int = lambda:int(input())
input_ints = lambda:map(int,input().split())
input_ints_list = lambda:list(input_ints())
input_str = lambda:input()
input_strs = lambda:input().split()
input_lines = lambda n,f:[f() for _ in range(n)]

import functools,fractions
gcd = lambda a:functools.reduce(fractions.gcd,a) 
lcm_base = lambda a,b:(a*b)//fractions.gcd(a,b) 
lcm = lambda a:functools.reduce(lcm_base,a,1) 

import itertools
permutations = lambda a,n:itertools.permutations(a,n) 
combinations = lambda a,n:itertools.combinations(a,n) 
product = lambda a,b:itertools.product(a,b) 

init_array_1dim = lambda v,n:[v for _ in range(n)]
init_array_2dim = lambda v,n,m:[[v for _ in range(n)] for _ in range(m)]

import math

ceil = lambda a:math.ceil(a) 
floor = lambda a:math.floor(a) 

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

def init_graph(n,a,directed=False):
    visited = init_array_1dim(False,n)
    graph = init_array_2dim(False,n,n)
    for e in a:
        graph[e[0]-1][e[1]-1] = True
        if not directed:graph[e[1]-1][e[0]-1] = True 
    return visited,graph

def solution():
    N,M = input_ints()
    ab = input_lines(M,input_ints_list)
    visited,graph = init_graph(N,ab)
    visited[0] = True
    print(dfs(0,N,graph,visited))

if __name__ == '__main__':
    solution()

Solution (Python):
ans = 0
def dfs(v, visitedNode, graph):
    visitedNode[v] = 1
    
    if all(visitedNode):
        global ans
        ans += 1
        return
    for node in graph[v]:
        if visitedNode[node]:
            
            continue
        else:
            
            dfs(node, visitedNode[:], graph)


N, M = map(int, input().split())
v = 0
visitedNode = [0] * N


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



dfs(v, visitedNode, graph)
print(ans)

Solution (Python):
ans = 0
def dfs(v, visitedNode, graph):
    visitedNode[v] = 1
    if all(visitedNode):
        global ans
        ans += 1
        return
    for node in graph[v]:
        if visitedNode[node]:
            continue
        else:
            dfs(node, visitedNode[:], graph)


N, M = map(int, input().split())
v = 0
visitedNode = [0] * N



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



dfs(v, visitedNode, graph)
print(ans)

Solution (Python):


def read_input():
    n, m = map(int, input().split())

    edges = []
    nodes = list(range(1, n + 1))

    for i in range(m):
        a, b = map(int, input().split())
        edges.append((a, b))


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

    for edge in edges:
        edges_dic[edge[0]].append(edge[1])
        edges_dic[edge[1]].append(edge[0])

    return n, m, nodes, edges_dic



def check_path(curr_node, rest_nodes, edges_dic, through):
    
    if not rest_nodes:
        return 1

    
    next_nodes = edges_dic[curr_node]
    targets = []
    for n in next_nodes:
        if n in rest_nodes:
            targets.append(n)

    
    if not targets:
        return 0

    
    count = 0
    for t in targets:
        new_rest = [r for r in rest_nodes if r != t]
        new_through = through + [curr_node]
        count += check_path(t, new_rest, edges_dic, new_through)

    return count


def submit():
    n, m, nodes, edges_dic = read_input()

    rest_nodes = [r for r in nodes if r != 1]
    paths = check_path(1, rest_nodes, edges_dic, [])
    print(paths)


if __name__ == '__main__':
    submit()

Solution (Python):
def find_path(x, v, e):
    if len(v) == len(e):
        return 1
    ans = 0
    for xi in e[x - 1]:
        if xi in v:
            continue
        vi = v + [xi]
        ans += find_path(xi, vi, e)
    return ans

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

Solution (Python):
import copy
n,m = map(int,input().split(' '))
route = [[]for i in range(n+1)]
already = [0 for i in range(n+1)]
already[0:2]=[1,1]
cnt=0

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

def trace(index,already):
    global cnt
    
    if not(0 in already):
        cnt += 1
    else:
        for new_point in route[index]:
            if already[new_point]!=1:
                new_already = copy.copy(already)
                new_already[new_point] = 1
                trace(new_point,new_already)

trace(1,already)

print(cnt)

Solution (Python):
from itertools import permutations

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

nodes = list(range(N))
paths = [[0] * N for i in range(N)]

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

ans = 0

for p in permutations(nodes[1:],len(nodes)-1):
	cnt = 0
	for j in range(len(p)):
		if(j == 0):
			nb = 0
			nn = p[j]
		else:
			nb = p[j-1]
			nn = p[j]
		if(paths[nb][nn] == 1):
			cnt = cnt + 1
		else:
			break
		if(cnt == len(p)):
			ans = ans + 1
print(ans)

Solution (Python):
from itertools import permutations


def calcpath(nodes, edges):
    start = nodes[0]
    pattern = permutations(nodes[1:])

    count = 0
    for p in pattern:
        path = [start] + list(p)
        for i in range(len(path) - 1):
            if edges[path[i]][path[i+1]] != 1:
                break
            if i + 1 == len(path) - 1:
                count += 1

    return count


def main():
    n, m = list(map(int, input().split()))
    nodes = [i for i in range(n)]
    edges = [[0 for i in range(n)] for _ in range(n)]
    for _ in range(m):
        a, b = list(map(int, input().split()))
        edges[a - 1][b - 1] = 1
        edges[b - 1][a - 1] = 1
    print(calcpath(nodes, edges))


main()

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

dict_path = {}
path = []

for i in range(M):
    a, b = input().split()
    path.append((a, b))
    path.append((b, a))

for i in range(1, N+1):
    tmp = []
    for j in path:
        a, b = j
        if a == str(i):
            tmp.append(b)
    dict_path[str(i)] = tmp

stack = ['1']
root = ['1']

ans = 0
while stack:
    path = stack.pop(-1)
    now = path[-1]
    for i in dict_path[now]:
        tmp = path
        if i not in path:
            tmp += i
            if tmp not in root:
                stack.append(tmp)
                root.append(tmp)
                if len(tmp) == N:
                    ans += 1

print(ans)

Solution (Python):
import itertools

N, M = map(int, input().split(" "))
edge = [[False]*N for _ in range(N)]

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

ans = 0

for i in itertools.permutations(range(1,N)):
    P = (0,) + i
    flag = True
    for j in range(len(P)-1):
        if edge[P[j]][P[j+1]] == False:
            flag = False
            break
    if flag:
        ans += 1

print(ans)

Solution (Python):
import itertools

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

ans=0
for i in itertools.permutations(list(range(n))):
  if i[0]!=0:
    continue
  flg=True
  for j in range(len(i)-1):
    if path[min(i[j],i[j+1])][max(i[j],i[j+1])]==False:
      flg=False
      break
  if flg:
    ans+=1
print(ans)

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

def dfs(s, path):
    if len(path) == n:
        return 1
    cnt = 0
    for next in g[s]:
        if next in path:
            continue
        cnt += dfs(next, path + [next])
    return cnt

print(dfs(0, [0]))

Solution (Python):
import itertools
N, M = map(int, input().split())
A = [set(map(int, input().split())) for _ in range(M)]
ans = 0
for p in itertools.permutations(range(2, N+1)):
    q = list(p) + [1]
    for i in range(N-1):
        if not {q[i], q[i+1]} in A:
            break
    else:
        ans += 1
print(ans)

Solution (Python):
import copy

N,M = list(map(int,input().rstrip().split()))
sides = []
for i in range(M):
    ab = list(map(int,input().rstrip().split()))
    sides.append(ab)
    ba = [ab[1],ab[0]]
    sides.append(ba)

explored = [False for i in range(N+1)]
explored[0] = True
explored[1] = True

def explore(currentposition,flg):
    count = 0
    if all(flg):
        return 1
    for p in sides:
        if p[0] == currentposition and flg[p[1]]==False:
            tmp_flg = copy.deepcopy(flg)
            tmp_flg[p[1]] = True
            count += explore(p[1],tmp_flg)
    return count

print(explore(1,explored))

Solution (Python):
import numpy as np
N, M = map(int, input().split())

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

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


Check = [0]*N
Check[0] = 1
ans = 0

def TreeSearch(x):
    
    for i in Node[x]:
        
        if Check[i] == 0:
            Check[i] = 1
            
            if np.prod(Check) == 1:
                global ans
                ans += 1
                
                
            TreeSearch(i)
            Check[i] = 0
            
           
TreeSearch(0)
print(ans)

Solution (Python):
import math, string, itertools, fractions, heapq, collections, re,  array, bisect, sys, random, time, copy, functools
sys.setrecursionlimit(10**7)
inf = 10 ** 20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def _I(): return int(sys.stdin.readline())
def _F(): return float(sys.stdin.readline())
def pf(s): return print(s, flush=True)

N,M=LI()
AB=[LI() for i in range(M)]
ans=0
L = list(itertools.permutations(range(2,N+1)))

for l in L:
	for lidx in range(len(l)):
		if lidx == 0:
			if [1,l[lidx]] not in AB:
				break
			continue
		
		if [l[lidx-1],l[lidx]] not in AB and [l[lidx],l[lidx-1]] not in AB:
			break
	else:
		ans+=1
print(ans)

Solution (Python):
from itertools import permutations

n, m = list(map(int, input().split()))
mat = [[False] * n for i in range(n)]
for i in range(m):
    a, b = list(map(int, input().split()))
    mat[a - 1][b - 1] = mat[b - 1][a - 1] = True
ans = 0
for pat in permutations(range(n)):
    if pat[0] != 0:
        continue
    f = True
    for i in range(n - 1):
        if not mat[pat[i]][pat[i + 1]]:
            f = False
    if f:
        ans += 1
print(ans)

Solution (Python):


A = list(map(int,input().split()))
N = A[0]
M = A[1]

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



def hitohudegaki(i,done):
    pattern = 0
    
    if i in done:
        return 0
    
    elif len(done) == N-1:
        return 1
    
    for j in range(len(L[i])):
        pattern += hitohudegaki(L[i][j],done+[i])
            
    return pattern



print(hitohudegaki(0,[]))

Solution (Python):
n,m = map(int,input().split())
l = [[] for _ in range(n)]
for _ in range(m):
    a,b = map(int,input().split())
    l[a-1].append(b-1)
    l[b-1].append(a-1)
def dfs(i,done):
    ret = 0
    if i in done:
        return 0
    if len(done)==n-1:
        return 1
    for j in range(len(l[i])):
        ret += dfs(l[i][j],done+[i])
    return ret
print(dfs(0,[]))

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

ans = 0
def dfs(visited, v):
    global ans
    nvisited = visited[:]
    nvisited.append(v)
    if len(nvisited) == n:
        ans += 1
    for item in edge[v]:
        if item not in nvisited:
            dfs(nvisited, item) 

dfs([], 0)
print(ans)

Solution (Python):
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)

flag = [False] * n
flag[0] = True
ans = 0

def dfs(x):
    global ans
    if all(flag):
        ans += 1
    for j in edge[x]:
        if not flag[j]:
            flag[j] = True
            dfs(j)
            flag[j] = False

dfs(0)
print(ans)

Solution (Python):
def search(i, bit):
  global ans
  if i<0 or i>=N:
    return;
  else:
    bit |= (1<<i)
  if bit == (1<<N)-1:
    ans += 1
    return
  else:
    for j in A[i]:
      if bit&(1<<j) == 0:
        search(j, bit)
    return
        

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

search(0, 0)

print(ans)

Solution (Python):
def dfs(now,depth):
    if use[now]:
        return 0

    if depth==n:
        return 1

    use[now]=1
    ans=0

    for i in range(n):
        if gragh[now][i]:
            ans+=dfs(i,depth+1)

    use[now]=0
    return ans

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

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

use=[0]*n

print(dfs(0,1))

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

ans = 0

def dfs(v=0,visited=[0]*N):
    visited[v] = 1
    if all(visited):
        global ans
        ans += 1
        return
    for nv in ad[v]:
        if visited[nv] == 1: continue
        dfs(nv,visited[:])

dfs()
print(ans)

Solution (Python):
N,M = map(int,input().split())
ad = [[0]*N for _ in range(N)]
for _ in range(M):
    a,b = map(int,input().split())
    a -= 1; b -= 1
    ad[a][b] = 1
    ad[b][a] = 1

ans = 0

def dfs(v=0,visited=[0]*N):
    visited[v] = 1
    if all(visited):
        global ans
        ans += 1
        return
    for nv, bit in enumerate(ad[v]):
        if bit == 0 or visited[nv] == 1: continue
        dfs(nv,visited[:])

dfs()
print(ans)

Solution (Python):
N,M = map(int,input().split())
ad = [[0]*N for _ in range(N)]
for _ in range(M):
    a,b = map(int,input().split())
    a -= 1; b -= 1
    ad[a][b] = 1
    ad[b][a] = 1

ans = 0

def dfs(v=0,d=0,visited=[1]+[0]*(N-1)):
    if d == N-1:
        global ans
        ans += 1
        return
    for nv, bit in enumerate(ad[v]):
        if bit == 0: continue
        if visited[nv] == 1: continue
        visited[nv] = 1
        dfs(nv,d+1)
        visited[nv] = 0

dfs()
print(ans)

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 itertools
N,M=map(int,input().split())
path=[[False]*N for _ in range(N)]
for i in range(M):
    a,b=[int(j) for j in input().split()]
    path[a-1][b-1]=True
    path[b-1][a-1]=True
ans=0
for junjo in itertools.permutations(range(1,N)):
    nexts=list(junjo)
    if path[0][nexts[0]]==False:continue
    if all([path[nexts[i]][nexts[i+1]] for i in range(N-2)]):
        ans+=1
print(ans)

Solution (Python):
N, M = map(int, raw_input().split())
graph = []
for i in range(0, N):
	lst = []
	for j in range(0, N):
		lst.append(False)
	graph.append(lst)
for i in range(0, M):
	a, b = map(int, raw_input().split())
	graph[a-1][b-1] = True
	graph[b-1][a-1] = True
memo = []
for i in range(0, N):
	memo.append(True)
queue = [[0, memo]]
cnt = 0
while queue != []:
	now = queue.pop(0)
	newmemo = []
	for i in range(0, N):
		if i == now[0]: newmemo.append(False)
		else: newmemo.append(now[1][i])
	if True not in newmemo: cnt += 1
	else:
		for i in range(0, N):
			if graph[now[0]][i] and newmemo[i]:
				queue.append([i, newmemo])
print cnt

Solution (Python):
import sys

def f(G, start, visited):
    cnt = 0
    n = len(G)
    visited_ = visited + [start]

    if len(visited_) == n:
        return 1

    next_node = set(G[start]) - set(visited_)
    if len(next_node) == 0:
        return 0

    for nn in next_node:
        cnt += f(G, nn, visited_)

    return cnt


def main():
    input = sys.stdin.readline
    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)

    cnt = f(G, 0, [])

    return cnt


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

Solution (Python):
import itertools

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

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

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

ans = 0

p = [i for i in range(1, n)]

for x in itertools.permutations(p):
    x = list(x)
    x.insert(0,0)
    for i in range(n-1):
        if not line[x[i]][x[i+1]]:
            break
        if i == n-2:
            ans += 1

print(ans)

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

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


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

stack = [0]
visited = [[0]]
ans = 0

while stack:
    p = stack.pop()
    v = visited.pop()
    for i in range(n):
        if line[p][i]:
            if i not in v:
                if len(v) == n-1:
                    ans += 1
                else:
                    stack.append(i)
                    v.append(i)
                    visited.append([x for x in v])
                    v.pop()

print(ans)

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)

import itertools
ans = 0
for p in itertools.permutations(range(n)):
    if p[0] == 0:
        flag = True
        for i in range(n-1):
            if not p[i+1] in l[p[i]]:
                flag = False
        if flag:
            ans += 1
print(ans)

Solution (Python):
N, M = map(int, input().split())
L = [[] for i 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)
    
import itertools
count = 0
for p in itertools.permutations(range(N)):
    if p[0] == 0:

        flag = True
        for i in range(N-1):

            if not p[i+1] in L[p[i]]:
                flag = False

        if flag:
            count += 1
print(count)

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

visited = [False]*N

ans = 0
import copy

def dfs(node, visited):
    global ans
    v = copy.copy(visited)
    if v[node]:
        return
    v[node] = True
    if all(v):
        ans += 1
    else:
        cands = graph[node]
        for cand in cands:
            dfs(cand, v)

dfs(0, visited)
print(ans)

Solution (Python):
import sys
import collections
ns = lambda: sys.stdin.readline().rstrip()
ni = lambda: int(ns())
nm = lambda: map(int, sys.stdin.readline().split())
nl = lambda: list(nm())
nsl = lambda: map(str, sys.stdin.readline().split())

n, m = nm()
lis = [[] for i in range(n)]
for i in range(m):
    a, b = nm()
    lis[a - 1].append(b)
    lis[b - 1].append(a)
visited = [0] * n


def dfs(v, n, visited):
    count = 1
    for i in range(n):
        if visited[i] == 0:
            count = 0
    if count == 1:
        return 1
    res = 0
    for i in lis[v]:
        if visited[i - 1] == 1:
            continue
        visited[i - 1] = 1
        res += dfs(i - 1, n, visited)
        visited[i - 1] = 0
    return res


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

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

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

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


path=[i for i in range(2,n+1)]

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

def dfs(v):
    if visited==[1]*n:
        return 1
    res=0
    for x in X[v]:
        if visited[x]==0:
            visited[x]=1
            res+=dfs(x)
            visited[x]=0
    return res

print(dfs(0))

Solution (Python):
N, M = map(int, input().split())
L = [[] for i 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)
    
import itertools
count = 0
for p in itertools.permutations(range(N)):
    if p[0] == 0:

        flag = True
        for i in range(N-1):

            if not p[i+1] in L[p[i]]:
                flag = False

        if flag:
            count += 1
print(count)

Solution (Python):
from functools import reduce
import math
import itertools

def main():
    
    
    
    
    
    
    
    
    
    

    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    

    
    
    
    
    N,M = (int(_) for _ in input().split())
    a = []
    b = []
    for i in range(M):
        c, d = (int(_) for _ in input().split())
        a.append(c)
        b.append(d)
    l = list(_ for _ in range(2,N+1))
    d = []
    for elem in itertools.permutations(l,len(l)):
        elem = list(elem)
        elem.insert(0,1)
        d.append(elem)
    ans = 0
    for l1 in d:
        flag = True
        for i in range(len(l1)-1):
            for j in range(M):
                if(a[j]==l1[i] and b[j] ==l1[i+1]) or (b[j]==l1[i] and a[j] ==l1[i+1]):
                    flag = True
                    break
                flag = False
            if flag == False:
                break
        if flag:
            ans += 1

    print(ans)
if __name__ == '__main__':
    main()

Solution (Python):
import itertools

def is_edge_exists(node1, node2, edges):
	for edge in edges:
		if node1 in edge and node2 in edge:
			return True
	return False

def route_count(route, edges):
	if route[0]!=1:
		return 0
	for i in range(len(route)-1):
		if not is_edge_exists(route[i], route[i+1], edges):
			return 0
	return 1

N, M = map(int, input().split())
edges = [list(map(int, input().split())) for i in range(M)]
nodes = [i+1 for i in range(N)]
routes = list(itertools.permutations(nodes))

ans = 0
for route in routes:
	ans += route_count(route, edges)
print(ans)

Solution (Python):
N, M = map(int, input().split())
L = [[] for i 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)
    
import itertools
s = [int(i) for i in range(N)]
count = 0
for p in itertools.permutations(s, N):

    if p[0] == 0:

        flag = True
        for i in range(N-1):


            if p[i+1] not in L[p[i]]:
                flag = False
        if flag:

            count += 1
print(count)

Solution (Python):
def dfs(v,n,visi,G):
    allv=True

    if False in visi:
        allv=False

    if allv:
        return 1

    ret=0

    for i in range(n):
        if G[v][i]==False:
            continue
        if visi[i]:
            continue
        visi[i]=True
        ret+=dfs(i,n,visi,G)
        visi[i]=False

    return ret

def main():
    ans=0
    n,m=map(int,input().split())
    ab=[list(map(int,input().split()))for i in range(m)]
    G=[[False for i in range(8)]for i in range(8)]
    for a,b in ab:
        G[a-1][b-1]=G[b-1][a-1]=True

    visi=[False for i in range(n)]

    visi[0]=True

    return dfs(0,n,visi,G)

print(main())

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

ans=0


def dfs(v,n,visi):
    allv=True

    for i in visi:
        if not i:
            allv=False

    if allv:
        return 1

    ret=0

    for i in range(n):
        if G[v][i]==False:
            continue
        if visi[i]:
            continue
        visi[i]=True
        ret+=dfs(i,n,visi)
        visi[i]=False

    return ret

n,m=map(int,input().split())
ab=[list(map(int,input().split()))for i in range(m)]
G=[[False for i in range(8)]for i in range(8)]

for a,b in ab:
    G[a-1][b-1]=G[b-1][a-1]=True

visi=[False for i in range(n)]

visi[0]=True

print(dfs(0,n,visi))

Solution (Python):



from itertools import permutations

N,M = map(int,input().split())
E = []
for i in range(M):
    a,b = (int(_) for _ in input().split())
    E.append((a,b))
V = (i+1 for i in range(N))
one_strike_cnt = 0

for vertexs in permutations(V):
    
    if vertexs[0] != 1:
        continue
    
    one_strike = True
    for vertex_index in range(len(vertexs)-1):
        flag = False
        for i in range(M):
            a,b = E[i]
            if (a == vertexs[vertex_index] and b == vertexs[vertex_index+1]) or (a == vertexs[vertex_index+1] and b == vertexs[vertex_index]):
                flag = True
                break
        if not flag:
            one_strike = False
            break
    if one_strike:
        one_strike_cnt += 1

print(one_strike_cnt)

Solution (Python):
from collections import defaultdict
vertices, edges = map(int, input().split(" "))
connect = defaultdict(set)
for i in range(edges):
    a, b = map(int, input().split(" "))
    connect[a] |= {b}
    connect[b] |= {a}

answer = 0
queue = [[set(), 1]]
while queue:
    visited, now = queue.pop()
    visited |= {now}
    
    if len(visited) == vertices:
        answer += 1
    else:
        for conn in connect[now]:
            if conn not in visited:
                queue.append([visited | {conn}, conn])
        

print(answer)

Solution (Python):
z,m=map(int,input().split());a=[[],[]];ans=0
for i in range(m):aa,bb=map(int,input().split());a[0].append(aa);a[1].append(bb)
def d(n,nl,ml):
  if sorted(nl+[n])==[i+1for i in range(z)]:return 1
  if n in nl:return 0
  l=len(ml[0]);ans=0
  for i in range(l):
    c=[ml[0][:i]+ml[0][i+1:],ml[1][:i]+ml[1][i+1:]]
    if ml[0][i]==n:ans+=d(ml[1][i],nl+[n],c)
    if ml[1][i]==n:ans+=d(ml[0][i],nl+[n],c)
  return ans
for i in range(m):
  if a[0][i]==1:
    c=[a[0][:i]+a[0][i+1:],a[1][:i]+a[1][i+1:]]
    ans+=d(a[1][i],[1],c)
print(ans)

Solution (Python):
N,M = map(int,input().split())
dict = {}
for m in range(M):
    a,b = map(int,input().split())
    if a in dict:
        dict[a].append(b)
    else:
        dict[a] = [b]
    if b in dict:
        dict[b].append(a)
    else:
        dict[b] = [a]
ans = 0
l = [0 for i in range(N+1)]
l[1] = 1
def dfs(l,now):
    global ans
    if sum(l) == N:
        ans += 1
        return(0)
    for i in dict[now]:
        if l[i] == 0:
            l[i] += 1
            now = i
            dfs(l,now)
            l[i] -= 1
        else:
            continue
dfs(l,1)
print(ans)

Solution (Python):
N, M = map(int, input().split())
ab = [list(map(int, input().split())) for i in range(M)]
visited = {i:False for i in range(N)}
visited[0] = True
ans = 0

def DFS(x):

  global ans
  nextx = []
  if False not in visited.values():
    ans += 1
    return
  for i in range(M):
    if x in ab[i]:
      xcol = ab[i].index(x)
      if visited[ab[i][1-xcol]-1]:
        continue
      else:
        nextx.append(ab[i][1-xcol])

  for i in nextx:
    visited[i-1] = True
    DFS(i)
    visited[i-1] = False
  return

DFS(1)
print(ans)

Solution (Python):
def one_stroke_path(N: int, M: int, edges: list) -> int:
    g = [[] for _ in range(N)]
    for u, v in edges:
        g[u-1].append(v-1)
        g[v-1].append(u-1)

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

    def dfs(current: int, visited_num: int) -> int:
        if not visited[current] and visited_num + 1 == N:
            return 1

        visited[current] = True

        total = sum(dfs(to, visited_num + 1)
                    for to in g[current] if not visited[to])

        visited[current] = False

        return total

    return dfs(0, 0)


if __name__ == "__main__":
    M = 0
    N, M = map(int, input().split())
    edges = [tuple(int(s) for s in input().split()) for _ in range(M)]
    ans = one_stroke_path(N, M, edges)
    print(ans)

Solution (Python):
from collections import deque
def dfs(v,N,memo):
    ans =0
    if not False in memo.values():
        return 1
    for u in E[v]:
        if memo[u]!=True:
            memo[u] = True
            ans += dfs(u,N,memo)
            memo[u] = False
    return ans
N,M = list(map(int,input().split()))
memo = {i:False for i in range(1,N+1)}
E = {i: []for i in range(1,N+1)}
for i in range(M):
    u,v = list(map(int,input().split()))
    E[u].append(v)
    E[v].append(u)
memo[1] = True
print(dfs(1,N,memo))

Solution (Python):
N,M = map(int,input().split())
edge_list = [list() for i in range(N)]
for i in range(M):
        a,b = map(int,input().split())
        edge_list[a-1].append(b-1)
        edge_list[b-1].append(a-1)
done = [0] * N
chk = 0
def dfs(s,done):
    done = done[:]
    global chk
    done[s] = True
    if all(done):
        chk += 1
    for i in edge_list[s]:
        if not done[i]:
            dfs(i,done)
    return 0
dfs(0,done)
print(chk)

Solution (Python):
import sys
n,m=map(int,input().split())
number=[[int(i) for i in l.split()] for l in sys.stdin]
visit=[0]*(n+1)
visit[1]=1
node=[[] for i in range(n+1)]
for i in number:
  node[i[0]].append(i[1])
  node[i[1]].append(i[0])
ans=0
def dfs(x):
  global ans
  if visit.count(1)==n:
    ans+=1
    return 0
  for i in node[x]:
    if visit[i]==0:
      visit[i]=1
      dfs(i)
      visit[i]=0
  return 0
dfs(1)
print(ans)