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):
N, M = list(map(int, input().split()))
ab = {i:[] for i in range(N)}
for _ in range(M):
    a, b = list(map(int, input().split()))
    ab[a-1].append(b-1)
    ab[b-1].append(a-1)
    
cand = [[0]+[one] for one in ab[0]]
while len(cand)>0 and len(cand[0])<N:
    tmp_cand = []
    for c in cand:
        last = c[-1]
        n = []
        for nc in ab[last]:
            if nc not in c:
                n.append(c+[nc])
        tmp_cand.extend(n)
    cand = tmp_cand
print(len(cand))

Solution (Python):
import itertools
n,m=map(int,input().split())
es=[set() for i in range(n)]
for i in range(m):
    a,b=map(int,input().split())
    es[a-1].add(b-1)
    es[b-1].add(a-1)
ans=0
for v in itertools.permutations(range(1,n)):
    u=0
    link=True
    for i in v:
        if i in es[u]:
            u=i
        else:
            link=False
            break
    if link:
        ans+=1
print(ans)

Solution (Python):
import itertools

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

for _ in range(M):
	ta, tb = map(int, input().split())
	E[ta-1].append(tb-1)
	E[tb-1].append(ta-1)

ans = 0

for p in itertools.permutations(range(1,N)):
	p = [0] + list(p)
	cond = 1
	for i in range(N-1):
		if p[i+1] not in E[p[i]]:
			cond = 0
	if cond:
		ans += 1


print(ans)

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

for _ in range(M):
	ta, tb = map(int, input().split())
	E[ta-1].append(tb-1)
	E[tb-1].append(ta-1)


def next_permutation(out, cnt, flg):
	if cnt == N:
		for i in range(N-1):
			if out[i+1] not in E[out[i]]:
				return 0
		return 1

	ans = 0

	for i in range(N):
		if flg[i] == 0:
			out.append(i)
			flg[i] = 1

			ans += next_permutation(out, cnt+1, flg)

			out.pop()
			flg[i] = 0

	return ans

perm = [0]
cnt = 1
flg = [0 for _ in range(N)]
flg[0] = 1

answer = next_permutation(perm, cnt, flg)

print(answer)

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

def dfs(v, used, cnt):
    used[v] = 1
    if all(used):
        cnt.append(1)
    for nv in es[v]:
        if used[nv]:
            continue
        dfs(nv, used, cnt)
    used[v] = 0

used = [0] * N
cnt = []
dfs(0, used, cnt)

print(sum(cnt))

Solution (Python):
import numpy as np
import itertools 
N,M=map(int,input().split())
G=np.zeros((N+1,N+1),dtype=np.int32)
for i in range(M):
  a,b=map(int,input().split())
  G[a][b]=1
  G[b][a]=1

ans=0
for i in itertools.permutations(range(2,N+1)):
  cnt=0
  for j in range(N-2):
    if G[i[j]][i[j+1]]!=0:
      cnt+=1
  if G[1][i[0]]==1:
    cnt+=1
  if cnt==N-1:
    ans+=1
print(ans)

Solution (Python):
N , M = map(int , input().split())
A = [list(map(int,input().split())) for i in range(M)]
tf = [False]*N

for i in range(M):
    A.append(list(reversed(A[i])))

def saiki(aaa):
    ans = 0
    if all(tf) == True:
        return 1
    stack = []
    for i in range(len(A)):
        if A[i][0] == aaa and tf[A[i][1]-1] == False:
            stack.append(A[i][1])

    for i in range(len(stack)):
        tf[stack[i]-1] = True
        ans += saiki(stack[i])
        tf[stack[i]-1] = False
    return ans

def main():
    tf[0] = True
    ans = saiki(1)
    print(ans)

if __name__ == '__main__':
    main()

Solution (Python):
N, M = map(int,input().split())
G = [[] for _ 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 = [True]*N
visited_all = [False]*N
cnt = [0]

def dfs(visited, pos):
  visited[pos] = False
  if visited == visited_all:
    cnt[0] += 1
  else:
    for p in G[pos]:
      if visited[p] == False:
        continue
      dfs(visited, p)
      visited[p] = True

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

Solution (Python):
import itertools
n, m = list(map(int, input().split()))
a = [list(map(int, input().split())) for _ in range(m)]
y = 0
s = []
for i in range(1, n):
  s.append(i+1)
for x in itertools.permutations(s):
  if [1, int(x[0])] in a:
      for i in range(n-2):
          if not [int(x[i]), int(x[i+1])] in a and not [int(x[i+1]), int(x[i])] in a:
            break
      else: y += 1
print(y)

Solution (Python):
import itertools
import copy
n, m = map(int, input().split())
graph = [[] * n for i in range(n)]
for _ in range(m):
    num_from, num_to = map(int, input().split())
    graph[num_from - 1].append(num_to - 1)
    graph[num_to - 1].append(num_from - 1)

count = 0
node_list = [i + 1 for i in range(n - 1)]
for pattern in itertools.permutations(node_list):
    pattern_list = list(pattern)
    pattern_list.insert(0, 0)
    can_arrive = False
    for i in range(n):
        if i == n - 1:
            can_arrive = True
            break
        if pattern_list[i + 1] not in graph[pattern_list[i]]:
            can_arrive = False
            break
    if can_arrive:
        count += 1

print(count)

Solution (Python):
import sys
input = sys.stdin.readline
n, m = [int(x) for x in input().strip().split()]
g = [[0] * n for _ in range(n)]
for i in range(m):
    a, b = [int(x) for x in input().strip().split()]
    g[a-1][b-1] = 1
    g[b-1][a-1] = 1

flags = [False] * n
def dfs(flags, v):
    if flags.count(False) == 1:
        return 1
    flags[v] = True
    ret = 0
    for i, f in enumerate(g[v]):
        if f == 0 or flags[i]:
            continue
        ret += dfs(flags[:], i)
    return ret

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

Solution (Python):
n,m=[int(x) for x in input().split()]
edges=[[] for x in range(n)]
for i in range(m):
    a,b=[int(x)-1 for x in input().split()]
    edges[a].append(b)
    edges[b].append(a)
def ans(path):
    if len(path)==n:
        
        return 1
    res=0
    for i in range(n):
        if not i in path and  i in edges[path[-1]]:
            res+=ans(path+[i])
    return res
print(ans([0]))

Solution (Python):
N, M = map(int, input().split())
matrix=[[0]*N for i in range(N)]
for i in range(M):
    a, b = map(int, input().split())
    matrix[a-1][b-1]=1
    matrix[b-1][a-1]=1
import itertools 
count=0
for i in itertools.permutations(range(N)):
    if i[0]==0:
        result=1
        for j in range(N-1):
            result*=matrix[i[j]][i[j+1]]
        if result==1:
            count+=1
    else:
        break
print(count)

Solution (Python):

import itertools

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

cnt = 0

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

print(cnt)

Solution (Python):
def dfs(v,been):
    if len(been) == n:
        ans.append(1)
        
        return
    for i in graph[v]:
        if i in been:
            pass
        else:
            been.add(i)
            dfs(i,been)
            been.remove(i)
    return

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


ans = []

dfs(1,set([1]))
print(sum(ans))

Solution (Python):
import sys
import copy

input = sys.stdin.readline

A = None


def dfs(i, v):
    global A
    v.add(i)

    ans = 0
    for j in A[i]:
        if j not in v:
            v2 = copy.deepcopy(v)
            ans += dfs(j, v2)

    if len(A) - 1 == len(v):
        ans += 1
    return ans


def main():
    global A
    N, M = [int(x) for x in input().split()]
    A = [[] for j in range(N + 1)]
    for _ in range(M):
        a, b = [int(x) for x in input().split()]
        A[a].append(b)
        A[b].append(a)

    print(dfs(1, set()))


if __name__ == '__main__':
    main()

Solution (Python):
N, M = map(int, input().split())
AB = [tuple(map(int, input().split())) for _ in range(M)]
G = [[] for _ in range(N)]
for a, b in AB:
    G[a-1].append(b-1)
    G[b-1].append(a-1)
visited = [False] * N
visited[0] = True
ans = 0
def dfs(x):
    global ans
    if all(visited):
        ans += 1
        return
    for y in G[x]:
        if not visited[y]:
            visited[y] = True
            dfs(y)
            visited[y] = False
dfs(0)
print(ans)

Solution (Python):
from collections import defaultdict
vertices, edges = map(int, input().split(" "))
connect = defaultdict(set)
for e in range(edges):
    a, b = map(lambda n:n - 1, map(int, input().split(" ")))
    connect[a] |= {b}
    connect[b] |= {a}
queue = [[0, set()]]
answer = 0
while queue:
    next_queue = []
    
    for q in queue:
        here, visited = q
        new_visited = set()
        new_visited |= visited | {here}
        if len(new_visited) == vertices:
            
            answer += 1
        for conn in connect[here]:
            if conn not in new_visited:
                next_queue.append([conn, new_visited])
    queue = next_queue
print(answer)

Solution (Python):
import itertools

n,m=map(int,input().split())
L=[list(map(int,input().split())) for i in range(m)]
LL=[]
cnt=0
for i in range(len(L)):
    LL.append([L[i][1],L[i][0]])
Node=L+LL
Ans=[int(i)+1 for i in range(n)]
for v in itertools.permutations(Ans):
    v=list(v)
    if v[0]!=1:
        break
    tmp=0
    for i in range(n-1):
        if [v[i],v[i+1]] in Node:
            tmp+=1
    if tmp==n-1:
        cnt+=1
print(cnt)

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


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

ans = 0

def dfs(u, visited):
  global ans
  stack = [u]

  while stack:
    u = stack.pop()
    visited.add(u)

    e = list(filter(lambda x: x not in visited, edges[u]))
    l = len(e)
    if l == 0:
      if len(visited) == N:
        ans += 1
    elif l == 1:
      stack.append(e[0])
    else:
      for next in e:
        dfs(next, copy.copy(visited))


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

Solution (Python):
n, m = map(int, input().split())
adjacent_list = [[] for i in range(n+1)]
for i in range(m):
    a, b = map(int, input().split())
    adjacent_list[a].append(b)
    adjacent_list[b].append(a)
ans = 0
def dfs(node,f):
    global ans
    if len(f) == n:
        ans += 1
    else:
        for i in adjacent_list[node]:
            if i not in f:
                k = f | set([i])
                dfs(i,k)
dfs(1,set([1]))
print(ans)

Solution (Python):
import copy
n, m = map(int, input().split())
adjacent_list = [[] for i in range(n+1)]
for i in range(m):
    a, b = map(int, input().split())
    adjacent_list[a].append(b)
    adjacent_list[b].append(a)
ans = 0
def dfs(node,f):
    f.add(node)
    global ans
    if len(f) == n:
        ans += 1
    else:
        for i in adjacent_list[node]:
            if i not in f:
                k = copy.deepcopy(f)
                dfs(i,k)
dfs(1,set())
print(ans)

Solution (Python):

from bisect import *
from collections import *
from heapq import *
import copy
N,M=map(int,input().split())
AB=[list(map(int,input().split())) for i in range(M)]
data=[[] for i in range(N+1)]
for a,b in AB:
    data[a].append(b)
    data[b].append(a)

count=0
stack=[[1,set([1])]]
while stack:
    point,visited=stack.pop()
    for p in data[point]:
        if not p in visited:
            if len(visited)+1==N:
                count+=1

            else:
                a=copy.copy(visited)
                a.add(p)
                stack.append([p,a])
print(count)

Solution (Python):

from bisect import *
from collections import *
from heapq import *

N,M=map(int,input().split())
AB=[list(map(int,input().split())) for i in range(M)]
data=[[] for i in range(N+1)]
for a,b in AB:
    data[a].append(b)
    data[b].append(a)

count=0
stack=[[1,set([1])]]
while stack:
    point,visited=stack.pop()
    for p in data[point]:
        if not p in visited:
            if len(visited)+1==N:
                count+=1

            else:
                a=set(list(visited))
                a.add(p)
                stack.append([p,a])
print(count)

Solution (Python):

from bisect import *
from collections import *
from heapq import *

N,M=map(int,input().split())
AB=[list(map(int,input().split())) for i in range(M)]
data=[[] for i in range(N+1)]
for a,b in AB:
    data[a].append(b)
    data[b].append(a)

count=0
stack=[[1,"1"]]
while stack:
    point,visited=stack.pop()
    for p in data[point]:

        if not str(p) in visited:
            vis=visited+str(p)
            if len(vis)==N:
                count+=1
            else:
                stack.append([p,visited+str(p)])
print(count)

Solution (Python):
import itertools
n,m=map(int,input().split())
node=[[0 for i in range(n)] for j in range(n)]
for i in range(m):
  a,b=[int(x)-1 for x in input().split()]
  node[a][b]=1
  node[b][a]=1
ct=0
for order in itertools.permutations(range(n),n):
  if order[0]==0:
    for j in range(n):
      if j==n-1:
        ct+=1
        break
      if not node[order[j]][order[j+1]]:
        break
    
print(ct)

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

Solution (Python):
from itertools import permutations

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

ans = 0
for p in permutations(range(N), r=N):
    if p[0] != 0:
        continue
    for i in range(1, N):
        f, t = p[i-1:i+1]
        if adjacent[f][t] != 1:
            break
    else:
        ans += 1
print(ans)

Solution (Python):
def search(node, searched, goal):
  if searched == goal:
    return 1
  v = 0
  for nei in edges[node]:
    if searched & (1 << nei):
      continue
    v += search(nei, searched | (1<<nei), goal)
    
  return v

n, m = map(int, input().split())
edges = [[] for _ in range(n)]
for i in range(m):
  a, b = map(lambda x: int(x) - 1, input().split())
  edges[a].append(b)
  edges[b].append(a)
print(search(0, 1, (1<<n) - 1))

Solution (Python):
from itertools import permutations, tee

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

for _ in range(M):
    edges.add(tuple(map(int, input().split())))


def each_cons(iterable):
    a, b = tee(iterable)
    next(b, None)
    return zip(a, b)


def is_available(edge):
    return edge in edges or edge[::-1] in edges


cases = permutations(range(2, N + 1), N - 1)

count = 0

for numbers in cases:
    if all(map(is_available, each_cons((1,) + numbers))):
        count += 1


print(count)

Solution (Python):
from itertools import permutations
n,m=map(int,input().split())
l=[list(map(int,input().split())) for i in range(m)]
p=[i for i in range(1,n+1)]
np=list(permutations(p))
edge=[[] for i in range(n)]
for i in range(m):
  edge[l[i][0]-1].append(l[i][1]-1)
  edge[l[i][1]-1].append(l[i][0]-1)
ans=0
for i in range(len(np)):
  if np[i][0]!=1:
    continue
  else:
    ok=True
    for j in range(n-1):
      if np[i][j]-1 not in edge[np[i][j+1]-1]:
        ok=False
    if ok:
      ans+=1
print(ans)

Solution (Python):
import sys
import copy
sys.setrecursionlimit(1000000000)

def dfs(start, total, usedNodes):
    if start in usedNodes:
        return 0
    
    if total <= 1:
        return 1
    
    indices = findNodeIndex(start)
    if len(indices) == 0:
        return 0

    count = 0
    for i in indices:
        nextNode = PATHS[i][1] if PATHS[i][0] == start else PATHS[i][0]
        count += dfs(nextNode, total - 1, usedNodes + [start])
    return count

def findNodeIndex(node):
    return [i for (i, row) in filter(lambda x: (x[1][0] == node or x[1][1] == node), [(i, row) for i, row in enumerate(PATHS)])]

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


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

Solution (Python):
def check_path(dots_list,dot,golist):
	List = dots_list[:]
	List.remove(dot)

	c = 0

	if len(List) > 0:
		for i in golist[dot-1]:
			if List.count(i) > 0:
				c += check_path(List, i, golist)
			else:
				c += 0
	else:
		c = 1

	return c



if __name__ == '__main__':

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

	golist = []
	dots_list = []

	
	for i in range(1,N+1):
		golist_each = []
		dots_list.append(i)
		for j in range(0,M):
			if ms[j][0] == i:
				golist_each.append(ms[j][1])
			elif ms[j][1] == i:
				golist_each.append(ms[j][0])

		golist.append(golist_each)

	ans = check_path(dots_list, 1, golist)
	print(ans)

Solution (Python):
def get_args():
    N, M = map(int, input().split())
    A, B = [], []

    for _ in range(M):
        a, b = map(int, input().split())
        A.append(a)
        B.append(b)

    
    

    return N, M, A, B


class Graph:
    def __init__(self, vertex_size):
        self.VERTEX_SIZE = vertex_size
        self.adjacency = [set() for i in range(self.VERTEX_SIZE)]

    def add_edge(self, a_i, b_i):
        self.adjacency[a_i].add(b_i)
        self.adjacency[b_i].add(a_i)

    def get_adj(self, i):
        return self.adjacency[i]

    def vertexes_size(self):
        return self.VERTEX_SIZE

    def edges_size(self):
        raise NotImplemented()


def solve(N, M, A, B):
    g = Graph(8 + 2)

    for i in range(M):
        g.add_edge(A[i], B[i])

    marked = [False for _ in range(N + 1)]

    def dfs(i):
        marked[i] = True

        c = 0
        if marked.count(True) == N:
            c += 1

        for a in g.get_adj(i):
            if not marked[a]:
                c += dfs(a)

        marked[i] = False
        return c

    res = dfs(1)
    return res


if __name__ == '__main__':
    res = solve(*get_args())
    print(res)

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

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

for a, b in AB:
    a -= 1
    b -= 1
    graph[a][b] = True
    graph[b][a] = True

VISITED = [None] * N

count = 0

def dfs(v):
    global count
    if all(VISITED):
        count += 1
        return

    edges = graph[v]
    for i, ei in enumerate(edges):
        if ei and not VISITED[i]:
            VISITED[i] = True
            dfs(i)
            VISITED[i] = False

VISITED[0] = True
dfs(0)
print(count)

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

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

for a, b in AB:
    a -= 1
    b -= 1
    graph[a][b] = True
    graph[b][a] = True

VISITED = [None] * N

count = 0

def dfs(v):
    global count
    
    if all(VISITED):
        count += 1
        return

    edges = graph[v]
    for i, ei in enumerate(edges):
        if ei and not VISITED[i]:
            VISITED[i] = True
            dfs(i)
            VISITED[i] = False

    return 0


VISITED[0] = True
dfs(0)
print(count)

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

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

for a, b in AB:
    a -= 1
    b -= 1
    graph[a][b] = True
    graph[b][a] = True




from itertools import permutations
l = [i for i in range(1, N)]
patterns = list(permutations(l))



cnt = 0
for pi in patterns:
    cur = 0
    ok = True
    
    for t in pi:
        if not graph[cur][t]:
            ok = False
        cur = t
    if ok:
        cnt += 1


print(cnt)

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

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

for a, b in AB:
    a -= 1
    b -= 1
    graph[a][b] = True
    graph[b][a] = True




from itertools import permutations
l = [i for i in range(1, N)]
patterns = list(permutations(l))



cnt = 0
for pi in patterns:
    cur = 0
    ok = True
    
    for t in pi:
        if not graph[cur][t]:
            ok = False
        cur = t
    if ok:
        cnt += 1


print(cnt)

Solution (Python):



def solve(*args: str) -> str:
    n, m = map(int, args[0].split())
    edges = [set() for _ in range(n)]
    for AB in args[1:]:
        a, b = map(int, AB.split())
        edges[a-1].add(b-1)
        edges[b-1].add(a-1)

    count = 0
    stack = [(0, 0)]
    while stack:
        node, visited = stack.pop()
        visited |= 1 << node

        if visited+1 == 1 << n:
            count += 1

        for dist in edges[node]:
            if visited & (1 << dist) == 0:
                stack.append((dist, visited))

    return str(count)


if __name__ == "__main__":
    print(solve(*(open(0).read().splitlines())))

Solution (Python):
from itertools import permutations
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())
    path[a-1][b-1] = True
    path[b-1][a-1] = True
ans = 0
for ss in permutations(range(n)):
    s = list(ss)
    key = 1
    if s[0] != 0:
        key = 0
    for i in range(n-1):
        if path[s[i]][s[i+1]] == False:
            key = 0
    if key:
        ans += 1
print(ans)

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

ans=[]

def dfs(num,count,visit):
    
    if count==N:
        if len(visit)==N:
            ans.append(num)
        
    else:
        for index,item in enumerate(l[num]):
            if item==1 and visit.count(index)==0:
                dfs(index,count+1,visit+[index])
    return 0

            
        

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

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

dfs(0,1,[0])

print(len(ans))

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

isVisited = [False]*n
isVisited[0] = True

def dfs(v: int) -> int:
    if all(isVisited):
        return 1

    ret = 0

    for i in g[v]:
        if isVisited[i]:
            continue

        isVisited[i] = True
        ret += dfs(i)
        isVisited[i] = False

    return ret

print(dfs(0))

Solution (Python):
def dfs(n,G,visited,cnt):
    visited[n] = True
    if not False in visited:
        visited[n] = False
        return cnt + 1
    for x in G[n]:
        if visited[x] == True:
            continue
        cnt = dfs(x,G,visited,cnt)
    visited[n] = False
    return cnt


def main():
    N,M = map(int ,input().split())
    G = [list() for x in range(N)]
    for i in range(M):
        a,b = map(int,input().split())
        a = a - 1
        b = b - 1
        G[a].append(b)
        G[b].append(a)
    visited = [False] * N
    ans = dfs(0,G,visited,0)
    print(ans)

if __name__ == '__main__':
    main()

Solution (Python):
from itertools import permutations

N, M = map(int, input().split())
E = {i: set() for i in range(1, 1 + N)}
for _ in range(M):
    a, b = map(int, input().split())
    E[a].add(b)
    E[b].add(a)
ans = 0
for perm in permutations([i for i in range(2, 1 + N)]):
    perm = [1] + list(perm)
    ok = True
    for i in range(len(perm) - 1):
        prv = perm[i]
        nxt = perm[i + 1]
        if nxt not in E[prv]:
            ok = False
    if ok:
        ans += 1
print(ans)

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


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

Solution (Python):
from itertools import permutations

n,m = map(int,input().split())
t = []
for _ in range(m):
    a,b = map(int,input().split())
    t.append([a, b])
    t.append([b, a])
l = [i for i in range(2,n+1)]
p = permutations(l)
cnt = 0
for v in p:
    if [1, v[0]] not in t:
        continue
    for i in range(n-2):
        if [v[i], v[i+1]] in t:
            continue
        else:
            break
    else:
        cnt += 1
print(cnt)

Solution (Python):

import itertools
N,M=map(int,input().split())
edges={tuple(sorted(map(int,input().split()))) for i in range(M)}

ans=0
for i in itertools.permutations(range(2,N+1),N-1):
    l=[1]+list(i)
    ans+=sum(1 for edge in zip(l,l[1:]) if tuple(sorted(edge)) in edges)==N-1

print(ans)

Solution (Python):
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):
from itertools import permutations

n, m = map(int, input().split())
g = {i: set() for i in range(1, n+1)}

for _ in range(m):
    a, b = map(int, input().split())
    g[a].add(b)
    g[b].add(a)

res = 0
visited = {1}
def dfs(v):
    global res
    global visited
    if len(visited) == n:
        res += 1
        return
    for i in g[v] - visited:
        visited.add(i)
        dfs(i)
        visited.remove(i)

dfs(1)

print(res)

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

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

def dfs(v):
   if (len(v) == n):
      return 1

   ans = 0
   for u in set(g[v[-1]]) - set(v):
      ans += dfs(v + [u])

   return ans

print(dfs([0]))

Solution (Python):
from itertools import permutations

n, m = map(int, input().split())
g = {i: [] for i in range(1, n+1)}

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

p = permutations([x for x in range(2, n+1)])

res = 0
for l in p:
    tmp = g[1]
    for x in l:
        if x in tmp:
            tmp = g[x]
        else:
            break
    else:
        res += 1

print(res)

Solution (Python):

from itertools import permutations
from collections import defaultdict

n,m = map(int, input().split())
edge = defaultdict(lambda: set([]))
for _ in range(m):
    a,b = map(int, input().split())
    edge[a].add(b)
    edge[b].add(a)

def check(p):
    for i in range(n-1):
        if p[i+1] not in edge[p[i]]:
            return False
    return True

res = 0
for r in permutations(range(2,n+1), n-1):
    if check([1]+list(r)):
        res += 1
print(res)

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

cnt = 0
def dfs(graph, v, seen):
    if not False in seen:
        global cnt
        cnt += 1
        return

    for i in graph[v]:
        if seen[i]:
            continue
        seen[i] = True
        dfs(graph, i, seen)
        seen[i] = False
    return cnt

n, m = map(int, input().split())
graph = [[] for i in range(n)]
for i in range(m):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    graph[a].append(b)
    graph[b].append(a)
    seen = [False for _ in range(n)]
    seen[0] = True



print(dfs(graph, 0, seen))

Solution (Python):
import itertools

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

if n ==2:
    print(1)
    exit()

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

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



route=list(itertools.permutations(range(1,n)))

ans=0
for i in route:
    chk0=0
    chk=True
    if i[0] in arr[0]:
        chk0 =True
        
        for j in range(1,n-1):
            if i[j] in arr[i[j-1]]:
                chk0+=1
                
                pass
            else:
                
                break
                
    if chk0==n-1:
        
        ans+=1

print(ans)

Solution (Python):
from collections import deque

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

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

Q = deque()
Q.append(0)
visited = [0]*N

def DFS(x):
    global ans
    if visited[x] == 1:
        return
    visited[x] = 1
    if all(visited):
        ans += 1
        visited[x] = 0
        return
    for nx in table[x]:
        if visited[nx] == 0:
            DFS(nx)
    visited[x] = 0
DFS(0)
print(ans)

Solution (Python):
import sys
import itertools
 
 
def check(i,array):
    now=0
    while True:
        flag=0
        if(now==len(i)-1):
            return 1
        for x in array:
            if(i[now]==x[0] and i[now+1]==x[1] or \
                i[now]==x[1] and i[now+1]==x[0]):
 
                flag=1
                now+=1
                break
 
        if(flag==0):
            return 0
 
 
def main():
    N, M = map(int,input().split())
 
    array=[]
    sum=0
 
    for _ in range(0, M):
        array.append(list(map(int,input().split())))
 
 
    for i in itertools.permutations(range(1,N+1),N):
        if(i[0]==1):
            sum += check(i,array)
    print(sum)
 
main()

Solution (Python):
import sys
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)
from itertools import permutations
P=list(permutations(range(n)))

cnt=0
for p in P:
    if p[0]!=0:
        continue
    flg=True
    for i in range(len(p)-1):
        
        if p[i] not in g[p[i+1]]:
            flg=False
    if flg:
        cnt+=1
print(cnt)