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 = map(int, input().split())

a = [[0] * n for i in range(n)]

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

def dfs(v, n, visited):
    all_visited = 1
    for i in range(n):
        if visited[i] == 0:
            all_visited = 0

    if all_visited == 1:
        return 1

    ret = 0
    for i in range(n):
        if a[v][i] == 0:
            continue
        if visited[i] == 1:
            continue

        visited[i] = 1
        ret += dfs(i, n, visited)
        visited[i] = 0

    return ret

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

Solution (Python):
def dfs(now,depth):
    ans=0
    if vis[now]:
        return 0
    if depth==n:
        return 1
    vis[now]=1
    for i in range(n):
        if graph[now][i]:
            ans+=dfs(i,depth+1)
    vis[now]=0
    return ans
n,m=map(int,input().split())
edge=[[int(i) for i in input().split()]for i in range(m)]
graph=[[0 for i in range(n)]for i in range(n)]
for i in range(m):
    graph[edge[i][0]-1][edge[i][1]-1]=1
    graph[edge[i][1]-1][edge[i][0]-1]=1
vis=[0]*n
print(dfs(0,1))

Solution (Python):
def dfs(now,depth):
    if visited[now]:
        return 0
    if depth==n:
        return 1
    visited[now]=1
    ans=0
    for i in range(n):
        if connect[now][i]==1:
            ans+=dfs(i,depth+1)
    visited[now]=0
    return ans
n,m=map(int,input().split())
visited=[0]*n
edge=[[int(i)for i in input().split()]for i in range(m)]
connect=[[0 for i in range(n)]for i in range(n)]
for i in range(m):
    connect[edge[i][0]-1][edge[i][1]-1]=1
    connect[edge[i][1]-1][edge[i][0]-1]=1
print(dfs(0,1))

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

graph  = [[] for _ in range(N+1)]
for _ in range(M):
    x,y = map(int,input().split())
    graph[x].append(y)
    graph[y].append(x)

visited = [0]*(N)
ans = 0

def DFS(pos):
    global visited
    global ans
    if sum(visited) == N:
        ans += 1
        return

    for i in graph[pos]:
        if visited[i-1]:
            continue
        visited[i-1] = 1
        DFS(i)
        visited[i-1] = 0
    return

visited[0] = 1
DFS(1)
print(ans)

Solution (Python):
import itertools

N, M = map(int, input().split())
patterns = list(itertools.permutations(range(2, N+1)))
path = [[0]*(N+1) for _ in range(N+1)]
for _ in range(M):
    a, b = map(int, input().split())
    path[a][b] = 1
    path[b][a] = 1

ans = 0
for pattern in patterns:
    p = 1
    ok = True
    for x in pattern:
        if path[p][x] == 0:
            ok = False
            break
        p = x
    if ok:
        ans += 1
print(ans)

Solution (Python):
E_DICT = {}


def search_pass(v_idx, v_set, cnt):
    v_set2 = v_set.copy()
    v_set2.remove(v_idx)

    if len(v_set2) == 0:
        return cnt + 1

    e_tup = E_DICT[v_idx]

    for i in range(len(e_tup)):
        if e_tup[i] in v_set2:
            cnt = search_pass(e_tup[i], v_set2, cnt)

    return cnt


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

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

        if a in E_DICT:
            E_DICT[a].append(b)
        else:
            E_DICT[a] = [b]

        if b in E_DICT:
            E_DICT[b].append(a)
        else:
            E_DICT[b] = [a]

    if m == 0:
        comb = 0
    else:
        comb = search_pass(1, v, 0)

    print(comb)


if __name__ == '__main__':
    main()

Solution (Python):
N, M = map(int, input().split())
edges = [input().split() for i in range(M)]
searched_edge = [0 for i in range(M)]
searched = [0 for i in range(N)]
stack = ['1']

count = 0
searched[0] = 1
def search(stack, searched, edges, searched_edge):
	global count
	
	while (stack):
		now = stack.pop()
		searched[int(now)-1] = 1
		
		if 0 not in searched:
			count += 1
			return
		
		for edge in edges:
			if now in edge:
				next = edge[1] if edge[0] == now else edge[0]
				searched_edge[edges.index(edge)] = 1
				if searched[int(next)-1] == 0:
					stack += [next]
					searched[int(next)-1] = 1
					search(stack, searched, edges, searched_edge)
					searched_edge[edges.index(edge)] = 0
					searched[int(next)-1] = 0

	return

search(stack, searched, edges, searched_edge)
print(count)

Solution (Python):
def c_one_stroke_path(N, M, E):
    import itertools
    edge = [[] for j in range(N + 1)]
    for a, b in E:
        edge[a].append(b)
        edge[b].append(a)

    ans = 0
    
    route = itertools.permutations(range(2, N + 1), N - 1)
    for r in route:
        if not r[0] in edge[1]:
            
            continue
        count = 0
        for i in range(len(r) - 1):
            if not r[i + 1] in edge[r[i]]:
                
                break
        else:  
            ans += 1
    return ans

N,M = [int(i) for i in input().split()]
E = [[int(i) for i in input().split()] for j in range(M)]
print(c_one_stroke_path(N, M, E))

Solution (Python):
N, M = map(int, input().split())
P = [list(map(int, input().split())) for k in range(M)]
G = [[0 for k in range(N)] for k in range(N)]
for p in P:
    G[p[0]-1][p[1]-1] = G[p[1]-1][p[0]-1] = 1

def dfs(ima,itta):
    if len(itta)==N:
        return 1
    ans = 0
    for k in range(N):
        if ima[k]==1 and k not in itta:
            itta.append(k)
            ans += dfs(G[k],itta)
            itta.remove(k)
    return ans

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

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

visited = [1]
rest = [i for i in range(2, n + 1)]
ans = 0

def dfs(num):
    if rest == []:
        
        global ans
        ans += 1
    for i in range(m):
        if num in paths[i]:
            other = paths[i][1 - paths[i].index(num)]
            if other in rest:
                
                visited.append(other)
                rest.remove(other)
                
                dfs(other)
                visited.remove(other)
                rest.append(other)

dfs(1)
print(ans)

Solution (Python):
N,M=map(int,input().split())
edges = [input().split() for x in range(M)]
path = []
for i in range(M):
  if '1' == edges[i][0]:
    path.append('1' + edges[i][1])

while 0 < len(path):
  if len(path[0]) == N:
    break 
  work = path.pop(0)
  for j in range(M):
    if (work[-1] == edges[j][0]) and edges[j][1] not in work:
      path.append(work + edges[j][1])
    elif (work[-1] == edges[j][1]) and edges[j][0] not in work:
      path.append(work + edges[j][0])

print(len(path))

Solution (Python):
n,m=map(int,input().split())
def dfs(now,depth):
    if used[now]:
        return 0
    if depth==n:
        return 1
    used[now]=1
    ans=0
    for i in range(n):
        if connect[now][i]:
            ans+=dfs(i,depth+1)
    used[now]=0
    return ans
edge=[[int(i)for i in input().split()]for i in range(m)]
connect=[[0 for i in range(n)]for i in range(n)]
for i in range(m):
    connect[edge[i][0]-1][edge[i][1]-1]=1
    connect[edge[i][1]-1][edge[i][0]-1]=1
used=[0]*n
print(dfs(0,1))

Solution (Python):
n,m=map(int,input().split())
def dfs(now,depth):
    if used[now]:
        return 0
    if depth==n:
        return 1
    used[now]=1
    ans=0
    for i in range(n):
        if connect[now][i]:
            ans+=dfs(i,depth+1)
    used[now]=0
    return ans
edge=[[int(i)for i in input().split()]for i in range(m)]
connect=[[0 for i in range(n)]for i in range(n)]
for i in range(m):
    connect[edge[i][0]-1][edge[i][1]-1]=1
    connect[edge[i][1]-1][edge[i][0]-1]=1
used=[0]*n
print(dfs(0,1))

Solution (Python):
N,M=map(int,input().split())
s=[[]for i in range(N)]
w=0
for i in range(M):
    x,y=map(int,input().split())
    x,y=x-1,y-1
    s[x].append(y)
    s[y].append(x)
from itertools import permutations
for j in permutations(range(1,N)):
    j=[0]+list(j)
    for k in range(1,N):
        if j[k] not in s[j[k-1]]:
            break
    else:
        w+=1
print(w)

Solution (Python):
def dfs(x,c):
	if x==N-1:
		if all(visited):
			global ans
			ans += 1
		return

	for i in range(N):
		if neighbor[c][i] and not visited[i]:
			visited[i] = True
			dfs(x+1,i)
			visited[i] = False
		
N, M = map(int,input().split())
edge = [[int(i) for i in input().split()] for i in range(M)]
neighbor = [[False for i in range(N)] for i in range(N)]
visited = [False for i in range(N)]
for i in range(M):
	neighbor[edge[i][0]-1][edge[i][1]-1] = True
	neighbor[edge[i][1]-1][edge[i][0]-1] = True
	
ans = 0
visited[0] = True
dfs(0,0)
print(ans)

Solution (Python):


def dfs(v, N, visited):
  for i in range(1,N+1):
    if not visited[i]: break
    
    if i == N: return 1

  ret = 0
  for i in range(1, N+1):
    if not graph[v][i]: continue
    if visited[i]: continue

    visited[i] = 1
    ret += dfs(i, N, visited)
    visited[i] = 0

  return ret

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

graph = [[0]*(N+1) for i in range(N+1)]

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

visited = [0] + [0 for _ in range(N)]

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

Solution (Python):

n, m = [int(x) for x in input().split()]
adj = [[0]*n for i in range(n)]
visited = [0]*n
for i in range(m):
    a, b = [int(x) for x in input().split()]
    adj[a-1][b-1] = 1
    adj[b-1][a-1] = 1

ans = 0
def dfs(v):
    global ans
    if sum(visited) == n:
        ans += 1
    for i in range(n):
        if adj[v-1][i] == 1 and visited[i] == 0:
            visited[i] = 1
            dfs(i+1)
            visited[i] = 0

visited[0] = 1
dfs(1)
print(ans)

Solution (Python):
def bfs(g, n):
	tovisit = []
	for i in range(0, n):
		tovisit.append(i)
	queue = []
	tovisit.remove(0)
	queue.append([0, tovisit])
	cnt = 0

	while queue != []:
		status = queue.pop(0)
		now = status[0]
		currenttovisit = status[1]
		if currenttovisit == []: cnt = cnt + 1
		else:
			for i in range(0, n):
				newtovisit = []
				for j in range(0, len(currenttovisit)):
					newtovisit.append(currenttovisit[j])
				if i in currenttovisit and graph[now][i]:
					newtovisit.remove(i)
					queue.append([i, newtovisit])
	return cnt

N, M = map(int, raw_input().split())
graph = []
for i in range(0, N):
	arrow = []
	for j in range(0, N):
		arrow.append(False)
	graph.append(arrow)

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

print bfs(graph, N)

Solution (Python):
def dfs(now,flags):
    global graph
 
    if len(flags) == len(graph)-1:
        return 1

    flags.add(now)
    ans = 0
    for vis in graph[now]:
        if not vis in flags:
            
            ans += dfs(vis,flags)
    flags.remove(now)
    return ans



ans = 0
nums = [int(x) for x in input().split()]
N, M = nums[0], nums[1]
graph = {i:[] for i in range(1,N+1)}

for i in range(M):
    nums = [int(x) for x in input().split()]
    graph[nums[0]].append(nums[1])
    graph[nums[1]].append(nums[0])

print(dfs(1,set()))

Solution (Python):
def count_path(graph, node, visited):
    if node in visited: return 0
    if len(visited)==len(graph)-1: return 1
    visited.add(node)
    res=0
    for i in range(len(graph)):
        if graph[node][i]:
            res+=count_path(graph, i, visited)
    visited.remove(node)
    return res

def main():
    n, m=[int(w) for w in input().split()]
    graph=[[False for i in range(n)] for j in range(n)]
    for i in range(m):
        a, b=[int(w) for w in input().split()]
        a-=1
        b-=1
        graph[a][b]=True
        graph[b][a]=True

    res=count_path(graph, 0, set())
    print(res)

if __name__=="__main__":
    main()

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

E = [[] for _ in range(N)]
visited = [False]*N
visited_all = [True]*N

def DFS(V):
    if visited == visited_all:
        return 1
    count = 0
    for e in E[V]:
        if not visited[e]:
            visited[e] = True
            count += DFS(e) 
            visited[e] = False
    else:
        return count

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

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

Solution (Python):


line = input().split(" ")
n = int(line[0])
m = int(line[1])
edge = [[] for _ in range(n+1)]

for _ in range(m):
    line = input().split(" ")
    a = int(line[0])
    b = int(line[1])

    edge[a].append(b)
    edge[b].append(a)


visited = [False for _ in range(n+1)]
visited[0] = True
visited[1] = True

def solve(x):
    allVisited = True
    for e in visited:
        allVisited = allVisited and e
    if allVisited:
        return 1

    ret = 0
    for e in edge[x]:
        if not visited[e]:
            visited[e] = True
            ret += solve(e)
            visited[e] = False
    return ret


print(solve(1))

Solution (Python):
N,M = map(int,input().split())
dic = {i+1:[] for i in range(N)}

for i in range(M):
    f,g = map(int,input().split())
    dic[f].append(g)
    dic[g].append(f)


stack = [[1,1,[1]]]
root = 0
while len(stack) >0:
    now = stack[-1][0]
    length = stack[-1][1]
    visited = stack[-1][2]
    del stack[-1]
    for next in dic[now]:
        if next not in visited:
            temp = visited.copy()
            if length +1 <=N-1:
                temp.append(next)
                stack.append([next,length+1,temp])
            elif length +1 == N:
                root += 1


print(root)

Solution (Python):
import itertools
N,M=map(int,input().split())
m=[[0 for i in range(N)] for i in range(N)]
for i in range(M):
    a,b=map(int,input().split())
    m[a-1][b-1]+=1
    m[b-1][a-1]+=1
S=list(itertools.permutations(range(1,N),N-1))

T=0
for sg in S:
    root=[0]
    for i in sg:
        root.append(i)
    flag=0
    for i in range(N-1):
        if m[root[i+1]][root[i]]==0:
            flag=1
            break
    if flag==0:
        T+=1
print(T)

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

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

S = 1
G = (1 << N) - 1


def is_visited(v: int, path: int):
    return path & (1 << v)


def visit(v: int, path: int):
    return path ^ (1 << v)


def count(u: int, path: int):
    if path == G:
        return 1

    k = (u, path)
    if k in dp:
        return dp[k]

    s = sum(
        count(v, visit(v, path))
        for v in E[u]
        if not is_visited(v, path)
    )
    dp[k] = s
    return s


print(count(0, S))

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

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

S = 1
G = (1 << N) - 1


def is_visited(v: int, path: int):
    return path & (1 << v)


def visit(v: int, path: int):
    return path ^ (1 << v)


def count(u: int, path: int):
    if path == G:
        return 1

    if (u, path) in dp:
        return dp[(u, path)]

    return sum(
        count(v, visit(v, path))
        for v in E[u]
        if not is_visited(v, path)
    )


print(count(0, S))

Solution (Python):
from functools import lru_cache


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

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

S = 1
G = (1 << N) - 1


@lru_cache(2**N*N)
def is_visited(v, path):
    return path & (1 << v)


@lru_cache(2**N*N)
def count(u, path):
    if path == G:
        return 1

    return sum(
        count(v, path ^ (1 << v))
        for v in E[u]
        if not is_visited(v, path)
    )


print(count(0, S))

Solution (Python):
N, M = map(int, input().split())
E = {i: [] for i in range(N)}
for _ in range(M):
    u, v = map(int, input().split())
    E[u-1].append(v-1)
    E[v-1].append(u-1)

q = [(0, [0])]
c = 0
while q:
    x, p = q.pop()

    if len(p) == N:
        c += 1

    for v in E[x]:
        if v in p:
            continue
        q.append((v, p + [v]))

print(c)

Solution (Python):
from collections import defaultdict
from itertools import permutations
N, M = [int(i) for i in input().split()]

dd = defaultdict(list)
ans = 0
for _ in range(M):
    po = [int(i) for i in input().split()]
    dd[po[0]].append(po[1])
    dd[po[1]].append(po[0])
for route in permutations(range(1,N+1)):
    can = True
    if route[0] != 1:
        continue
    for i in range(N-1):
        if route[i+1] not in dd[route[i]]:
            can = False
            break
    if can:
        ans += 1

print(ans)

Solution (Python):
def dfs(g, v, i):
    if len(v) == len(g) - 1: return 1
    v.add(i)
    c = 0
    for u in g[i]:
        if u not in v: c += dfs(g, v, u)
    v.remove(i)
    return c

n, m = map(int, input().split())
g = [list() for _ 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)
print(dfs(g, set(), 0))

Solution (Python):

from itertools import permutations

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

t=list(permutations(list(range(1,n+1))))
for i in range(len(t)):
    flag=True
    if t[i][0]!=1: continue
    for j in range(n-1):
        a=sorted([t[i][j],t[i][j+1]])
        if a not in s: flag=False
    if flag: ans+=1
print(ans)

Solution (Python):
import itertools

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

d=[int(x)+1 for x in range(N-1)]
ans=0
for exam in itertools.permutations(d):
  cnt=list(exam)
  cnt.insert(0,0)
  flg=True
  for i in range(N-1):
    if not(cnt[i+1] in C[cnt[i]]):
      flg=False
      break
  if flg:
    ans+=1
print(ans)

Solution (Python):
import itertools
n,m = (int(i) for i in input().split())
a = [[int(i) for i in input().split()] for i in range(m)]
b,c,answer = [],[],0
for i in range(2,n+1):
	c.append(i)
for i in range(n):
	x = []
	for j in a:
		if j[0]==i+1:
			x.append(j[1])
		elif j[1]==i+1:
			x.append(j[0])
	b.append(x)
for i in list(itertools.permutations(c,n-1)):
	if i[0] in b[0] and all(i[j+1] in b[i[j]-1] for j in range(n-2)):
		answer += 1
print(answer)

Solution (Python):
n,m=map(int,input().split())
path=[[0]*n for i in range(n)]
for i in range(m):
    a,b=map(int,input().split())
    path[a-1][b-1]=1
    path[b-1][a-1]=1
visited=[0]*n
visited[0]=1
def dfs(position,visited,n):
    all_visited=1
    for i in range(n):
        if visited[i]==0:
            all_visited=0
            break
    if all_visited==1:
        return 1
    count=0
    for next in range(n):
        if path[position][next]==0:
            continue
        if visited[next]==1:
            continue
        visited[next]=1
        count+=dfs(next,visited,n)
        visited[next]=0
    visited[position]=0

    return count
print(dfs(0,visited,n))

Solution (Python):
n,m=map(int,input().split())
path=[[0]*n for i in range(n)]
for i in range(m):
    a,b=map(int,input().split())
    path[a-1][b-1]=1
    path[b-1][a-1]=1
visited=[0]*n
visited[0]=1
def dfs(position,visited,n):
    all_visited=1
    for i in range(n):
        if visited[i]==0:
            all_visited=0
            break
    if all_visited==1:
        return 1
    count=0
    for next in range(n):
        if path[position][next]==0:
            continue
        if visited[next]==1:
            continue
        visited[next]=1
        count+=dfs(next,visited,n)
        visited[i]=0
    visited[position]=0

    return count
print(dfs(0,visited,n))

Solution (Python):
n,m=map(int,input().split())
path=[[0]*n for i in range(n)]
for i in range(m):
    a,b=map(int,input().split())
    path[a-1][b-1]=1
    path[b-1][a-1]=1
visited=[0]*n
visited[0]=1
def dfs(position,visited,n):
    all_visited=1
    for i in range(n):
        if visited[i]==0:
            all_visited=0
            break
    if all_visited==1:
        return 1
    count=0
    for next in range(n):
        if path[position][next]==0:
            continue
        if visited[next]==1:
            continue
        visited[next]=1
        count+=dfs(next,visited,n)
        visited[i]=0
    visited[position]=0

    return count
print(dfs(0,visited,n))

Solution (Python):
def dfs(v,n,visited):
    all_visted=1
    for i in range(n):
        if visited[i]==0:
            all_visted=0
    if all_visted==1:
        return 1
    count=0
    for i in range(n):
        if path[v][i]==0 or visited[i]==1:
            continue
        visited[i]=1
        count+=dfs(i,n,visited)
        visited[i]=0
    return count
n,m=map(int,input().split())
path=[[0]*n for i in range(n)]
for i in range(m):
    a,b=map(int,input().split())
    path[a-1][b-1]=1
    path[b-1][a-1]=1
visited=[0]*n
visited[0]=1
print(dfs(0,n,visited))

Solution (Python):
def dfs(v,n,visited):
    all_visted=1
    for i in range(n):
        if visited[i]==0:
            all_visted=0
    if all_visted==1:
        return 1
    count=0
    for i in range(n):
        if path[v][i]==0:
            continue
        if visited[i]==1:
            continue
        visited[i]=1
        count+=dfs(i,n,visited)
        visited[i]=0
    return count

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

Solution (Python):
def dfs(v,n,visited):
    all_visted=1
    for i in range(n):
        if visited[i]==0:
            all_visted=0
    if all_visted==1:
        return 1
    count=0
    for i in range(n):
        if path[v][i]==0:
            continue
        if visited[i]==1:
            continue
        visited[i]=1
        count+=dfs(i,n,visited)
        visited[i]=0
    return count

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

Solution (Python):
n,m=[int(i) for i in input().split()]
es=set()
for _ in range(m):
    u,v=map(int,input().split())
    u,v=u-1,v-1
    es|={(u,v),(v,u)}


p=[[0]]
x=0
while p:  
  p1=p.pop()
  if len(p1)==n:
    x+=1
  else:
    for l0,l1 in es:
      if l0==p1[len(p1)-1] and l1 not in p1:
          p.append(p1+[l1])

print(x)

Solution (Python):
def dfs(v,n,visited):
    all_visted=1
    for i in range(n):
        if visited[i]==0:
            all_visted=0
    if all_visted==1:
        return 1
    ret=0
    for i in range(n):
        if path[v][i]==0:
            continue
        if visited[i]==1:
            continue
        visited[i]=1
        ret+=dfs(i,n,visited)
        visited[i]=0
    return ret
n,m=map(int,input().split())
path=[[0]*n for i in range(n)]
for i in range(m):
    a,b=map(int,input().split())
    path[a-1][b-1]=1
    path[b-1][a-1]=1
visited=[0]*n
visited[0]=1
print(dfs(0,n,visited))

Solution (Python):
def dfs(v,n,visited):
    all_visted=True
    for i in range(n):
        if visited[i]==False:
            all_visted=False
    if all_visted==True:
        return 1
    ret=0
    for i in range(n):
        if path[v][i]==False:
            continue
        if visited[i]==True:
            continue
        visited[i]=True
        ret+=dfs(i,n,visited)
        visited[i]=False
    return ret
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
visited=[False]*n
visited[0]=True
print(dfs(0,n,visited))

Solution (Python):
n,m=map(int,input().split())
if m==0:
    print(0)
    exit()
ans=[[] for i in range(n)]
for i in range(m):
    a,b=map(int,input().split())
    ans[a-1].append((b-1))
    ans[b-1].append((a-1))
v=[]
def dfs(now,visited=[]):
    
    if len(visited)==n:
        v.append([visited])
        return
    for j in ans[now]:
        if j not in visited:
            dfs(j,visited+[j])
dfs(0,[0])
print(len(v))

Solution (Python):
def dfs(t):
    if 0 not in already:
        return 1
    allReach=0
    for i in range(n):
        if connect[t][i]==1 and already[i]==0:
            already[i]=1
            allReach+=dfs(i)
            already[i]=0
    return allReach

n,m=map(int,input().split())
connect=[[0 for i in range(n)]for j in range(n)]
for i in range(m):
    a,b=map(int,input().split())
    
    connect[a-1][b-1]=1
    connect[b-1][a-1]=1
already=[0 for i in range(n)]
already[0]=1
print(dfs(0))

Solution (Python):
def dfs(t):
    if 0 not in already:
        return 1
    allReach=0
    for i in range(n):
        if connect[t][i]==1 and already[i]==0:
            already[i]=1
            allReach+=dfs(i)
            already[i]=0
    return allReach

n,m=map(int,input().split())
connect=[[0 for i in range(n)]for j in range(n)]
for i in range(m):
    a,b=map(int,input().split())
    
    connect[a-1][b-1]=1
    connect[b-1][a-1]=1
already=[0 for i in range(n)]
already[0]=1
print(dfs(0))

Solution (Python):
def dfs(t):
    if 0 not in already:
        return 1
    allReach=0
    for i in range(n):
        if connect[t][i]==1 and already[i]==0:
            already[i]=1
            allReach+=dfs(i)
            already[i]=0
    return allReach

n,m=map(int,input().split())
connect=[[0 for i in range(n)]for j in range(n)]
for i in range(m):
    a,b=map(int,input().split())
    connect[a-1][b-1]=1
    connect[b-1][a-1]=1
already=[0 for i in range(n)]
already[0]=1
print(dfs(0))

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==True:
        return 1

    ret=0
    for i in range(N):
        if graph[v][i]==False:
            continue
        if visited[i]==True:
            continue

        visited[i]=True
        ret+=dfs(i,N,visited)
        visited[i]=False

    return ret

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

visited = [False]*N

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

Solution (Python):
def dfs(t):
    
    if (0 not in already): return 1
    
    allReach=0
    for i in range(N):
        
        if connect[t][i]==1 and already[i]==0:
            already[i]=1
            allReach+=dfs(i)
            already[i]=0
    return allReach


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

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


already=[0 for i in range(N)]

already[0]=1

print(dfs(0))

Solution (Python):

count=0
def check(now,v,n):
    global count
    v[now]=1
    if sum(v)==n:
        count+=1
    else:
        for i in range(8):
            if v[i]==0 and g[now][i]==1:
                check(i,v[:],n)

n,m=map(int,input().split())
g=[[0 for i in range(8)]for i in range(8)]
for i in range(m):
    a,b=map(int,input().split())
    g[a-1][b-1]=1
    g[b-1][a-1]=1
check(0,[0,0,0,0,0,0,0,0][:],n)
print(count)

Solution (Python):
def dfs(v):
  if(0 not in already):return(1)
  allReach=0
  for i in range(n):
    if(connect[v][i]==1 and already[i]==0):
      already[i]=1
      allReach+=dfs(i)
      already[i]=0
  return(allReach)

n,m=map(int,input().split())
connect=[[0for i in range(n)]for j in range(n)]
for i in range(m):
  a,b=map(int,input().split())
  connect[a-1][b-1]=1
  connect[b-1][a-1]=1
  
already=[0for i in range(n)]
already[0]=1
print(dfs(0))

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

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


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


def dfs(x):
    global ans
    global visited
    
    if all(visited):
        ans += 1
        return
    
        
    for j in [j for j,v2 in enumerate(graph[x]) if v2 == 1 and not visited[j]]:
        visited[j] = True
        dfs(j)
        visited[j] = False

dfs(0)
print(ans)

Solution (Python):
from itertools import permutations
n,m = map(int,input().split())
edge = [[0]*n for i in range(n)]
for i in range(m):
    a,b = map(int,input().split())
    a-=1; b-=1
    edge[a][b] = edge[b][a] = 1
ret = 0
for i in permutations(range(n)):
    if i[0] != 0 : break
    for j in range(n-1):
        if edge[i[j]][i[j+1]] == 0: break
    else:
        ret += 1
print(ret)

Solution (Python):
n,m=map(int,input().split())
if m==0:
    print(0)
    exit()
ans=[[] for i in range(n)]
for i in range(m):
    a,b=map(int,input().split())
    ans[a-1].append((b-1))
    ans[b-1].append((a-1))
v=[]
def dfs(now,visited=[]):
    global v
    if len(visited)==n:
        v.append([visited])
        return
    for j in ans[now]:
        if j not in visited:
            dfs(j,visited+[j])
dfs(0,[0])
print(len(v))

Solution (Python):
import numpy as np
n,m=map(int,input().split())
if m==0:
    print(0)
    exit()
ans=[[] for i in range(n)]
for i in range(m):
    a,b=map(int,input().split())
    ans[a-1].append((b-1))
    ans[b-1].append((a-1))
v=[]
def dfs(now,visited=[]):
    global v
    if len(visited)==n:
        v.append([visited])
        return
    for j in ans[now]:
        if j not in visited:
            dfs(j,visited+[j])
dfs(0,[0])
print(len(v))

Solution (Python):
def dfs(ver, p):
    global visited, ans
    if p == N:
        ans += 1
        return
    for i in range(N):
        if graph[ver][i] == 1 and visited[i] != 1:
            visited[i] = 1
            dfs(i, p+1)
            visited[i] = 0

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

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

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

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

dfs(0, 1)

print(ans)