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.



Sample input:
3 3
1 2
1 3
2 3


Sample output:
2

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
# input = sys.stdin.readline
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)

Submission status: Accepted

Solution code:
# input = sys.stdin.readline
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)

Submission status: Accepted

Solution code:
# input = sys.stdin.readline
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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))

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)]
#start = findNodeIndex(1, PATHS)

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

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

    # print(N, M)
    # print(A, 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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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
    # print(v, VISITED)
    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)

Submission status: Accepted

Solution code:
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

# for gi in graph:
#     print(gi)

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

# print(patterns)

cnt = 0
for pi in patterns:
    cur = 0
    ok = True
    # t: 次の目的地
    for t in pi:
        if not graph[cur][t]:
            ok = False
        cur = t
    if ok:
        cnt += 1


print(cnt)

Submission status: Accepted

Solution code:
# coding: utf-8


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())))

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

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

ans=[]

def dfs(num,count,visit):
    #print(num,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))
#print(ans)

Submission status: Accepted

Solution code:
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))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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))

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:

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)

Submission status: Accepted

Solution code:
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):
    # 頂点1が始点
    if i[0] == 0:
        # 生成した順列の中をさらにループ
        for j in range(n):
            # n - 1 まで続いたら条件を満たすパスが存在する
            if j == n - 1:
                ans += 1
                break
            # i[j] から i[j + 1] に行くパスがなければ終了
            if not path[i[j]][i[j + 1]]:
                break

print(ans)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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]))

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
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)

Submission status: Accepted

Solution code:
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))

Submission status: Accepted

Solution code:
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())
    #print(a,b)
    
    arr[a-1].append(b-1)
    arr[b-1].append(a-1)

#print("arr",arr)

route=list(itertools.permutations(range(1,n)))
#print("route",route) 
ans=0
for i in route:
    chk0=0
    chk=True
    if i[0] in arr[0]:
        chk0 =True
        #print(i)
        for j in range(1,n-1):
            if i[j] in arr[i[j-1]]:
                chk0+=1
                
                pass
            else:
                #print(1,i[j],arr[i[j-1]])
                break
                
    if chk0==n-1:
        
        ans+=1

print(ans)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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)))
#print(P)
cnt=0
for p in P:
    if p[0]!=0:
        continue
    flg=True
    for i in range(len(p)-1):
        #print(p)
        if p[i] not in g[p[i+1]]:
            flg=False
    if flg:
        cnt+=1
print(cnt)

Submission status: Accepted

Solution code:
import itertools
n,m=map(int,input().split())
p=[[0]*n for i in range(n)]#隣接行列
for i in range(m):
    a,b=map(int,input().split())
    p[a-1][b-1]=1
    p[b-1][a-1]=1
seq=(i for i in range(n))
x=list(itertools.permutations(seq))
#print(x[0])
l=len(x)
ans=0
for i in range(l):
    k=x[i]
    if k[0]==0:
        for j in range(n-1):
            if p[k[j]][k[j+1]]!=1:
                break
        else:
            ans+=1
            #print(k)
    else:
        break
print(ans)

Submission status: Accepted

Solution code:
class Solver:
    def __init__(self, N, M, edges) -> None:
        self.N = N
        self.M = M
        self.edges = edges

    def find_next_node(self, current, visited):
        candidates = []
        for edge in self.edges:
            if edge[0] == current:
                candidates.append(edge[1])
            if edge[1] == current:
                candidates.append(edge[0])
        ret = []
        for node in candidates:
            bit = 2**(node - 1)
            if visited & bit == 0:
                # AND演算でゼロの場合は未訪問ノード
                ret.append(node)
        return ret

    def dfs(self, node, visited):
        """
        visitedのn番目のビットでノードnを訪ずれたか管理する
        """
        visited += 2**(node - 1)
        if visited == 2**self.N - 1:
            return 1
        movable_nodes = self.find_next_node(node, visited)
        return sum([self.dfs(next_node, visited) for next_node in movable_nodes])


    def solve(self) -> int:
        return self.dfs(1, 0)


if __name__ == "__main__":
    N, M = list(map(int, input().split()))
    edges = []
    for _ in range(M):
        edges.append(list(map(int, input().split())))

    s = Solver(N, M, edges)
    print(s.solve())

Submission status: Accepted

Solution code:
import itertools

n, m = map(int, input().split())
li = [list(map(int, input().split())) for i in range(m)]
iter_list = itertools.permutations(range(1, n + 1), n)


def checker(tup):
    if tup[0] != 1:
        return False
    for i in range(len(tup)-1):
        path = [tup[i], tup[i + 1]]
        re_path = [tup[i+1], tup[i]]
        if not (path in li or re_path in li):
            return False
    return True


res = 0
for i in iter_list:
    if checker(i):
        res += 1

print(res)

Submission status: Accepted

Solution code:
from itertools import permutations
#N = int(input())
N,M = map(int,input().split())
ab=[[]for i in range(N)]
for i in range(M):
    a,b = list(map(int,input().split()))
    ab[a-1].append(b-1)
    ab[b-1].append(a-1)
num = [i+1 for i in range(N-1)]
count = 0
for i in permutations(num):
    flag = True
    if i[0] not in ab[0]:
        continue
    for j in range(len(i)-1):
        if i[j+1] not in ab[i[j]]:
            flag = False
    if flag:
        count += 1
print(count)

Submission status: Accepted

Solution code:
import itertools
import numpy as np
n,m = map(int,input().split())
a = [0] * m
b = [0] * m
ans = 0
for i in range(m):
    a[i], b[i] = map(int, input().split())
    
gudge = np.zeros((n, n), dtype = np.int64)
for i in range(m):
    gudge[a[i]-1][b[i]-1] = 1
    gudge[b[i]-1][a[i]-1] = 1

retsu = [i+2 for i in range(n-1)]
p = itertools.permutations(retsu, n-1)

for v in p:
    path = [1]+list(v)
    flag = 1
    for i in range(n-1):
        if gudge[path[i]-1][path[i+1]-1] != 1:
            flag = 0
            break
            
    ans += flag
    
print(ans)

Submission status: Accepted

Solution code:
import numpy as np
import itertools

n, m = map(int, input().split())
G = np.zeros((n, n), dtype = np.int64)
for i in range(m):
    u, v = map(int, input().split())
    G[u - 1][v - 1] = 1
    G[v - 1][u - 1] = 1

ans = 0
nums = [i for i in range(1, n)]
for perm in itertools.permutations(nums):
    path = [0] + list(perm)
    ok = True
    for i in range(n - 1):
        if G[path[i]][path[i + 1]] != 1:
            ok = False
            break
    ans += ok
print(ans)

Submission status: Accepted

Solution code:
import pprint

def dfs(v, n, visited):
    all_visited = True

    for i in range(n):
        if visited[i] is False:
            all_visited = False

    if all_visited:
        return 1

    ret = 0
    for i in range(n):
        if edges[v][i] is False:
            continue
        if visited[i]:
            continue

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


N, M = tuple(map(int, input().split()))
nmax = 8
edges = [[False] * nmax for _ in range(nmax)]
for _ in range(M):
    A, B = tuple(map(int, input().split()))
    edges[A-1][B-1] = True
    edges[B-1][A-1] = True

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

Submission status: Accepted

Solution code:
from itertools import permutations
N,M = map(int,input().split())
table=[[]for i in range(N)]
for i in range(M):
    a,b=map(int,input().split())
    table[a-1].append(b-1)
    table[b-1].append(a-1)
 
def f(L,k):
    for a in L:
        if a==k:
            return True
    return False
 
S=[i for i in range(1,N)]
ans =0
for s in permutations(S,N-1):
    flag =True
    if not f(table[0],s[0]):
        continue
    for i in range(N-2):
        if not f(table[s[i]],s[i+1]):
            flag =False
    if flag:
        ans+=1
print(ans)

Submission status: Accepted

Solution code:
from itertools import permutations

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

edges =[set() for _ in range(N)]
for _ in range(M):
    fr, to = map(int, input().split())
    fr -= 1
    to -= 1
    edges[fr].add(to)
    edges[to].add(fr)

ans = 0
for perm in permutations(range(1, N), r=N-1):
    for prev, now in zip((0,) + perm, perm):
        if not now in edges[prev]:
            break
    else:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
import sys 

sys.setrecursionlimit(10**6)

N, M = map(int, input().split())
G = [list(map(int, input().split())) for _ in range(M)]
visited = [True if v == 0 else False for v in range(N)]
adj = {i+1:[] for i in range(N)}

# init
for g in G:
  adj[g[0]].append(g[1])
  adj[g[1]].append(g[0])
  
def dfs(adj, visited, x):
  if all(visited):
    return 1
  count = 0
  for v in adj[x]:
    if visited[v-1]:
      continue
    visited[v-1] = True
    count += dfs(adj, visited, v)
    visited[v-1] = False
  return count

print(dfs(adj, visited, 1))

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
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 I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

nmax=8
graph=[[False for __ in range(nmax)]for _ in range(nmax)]

def dfs(v,n,visited):
  visited[v]=True

  all_visited=True
  for i in range(n):
    if visited[i]==False:
      all_visited=False
  if all_visited:
    return 1

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

  return ret

def main():
  n,m=LI()
  for _ in range(m):
    a,b=LI()
    graph[a-1][b-1]=True
    graph[b-1][a-1]=True

  visited=[False for _ in range(n)]
  visited[0]=True
  return dfs(0,n,visited)

# main()
print(main())

Submission status: Accepted

Solution code:
import itertools

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

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

num = [i for i in range(1,n)]
ans = 0


for v in itertools.permutations(num):
    bre = False
    if li[0][v[0]] == 0:
        continue
    for i in range(len(v)-1):
        if li[v[i]][v[i+1]] == 0:
            bre = True
            break
    if bre:
        continue
    else:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
conn = [[False]*n for _ in range(n)]
visited = [False] * n
v = []
for _ in range(m):
    i, j = map(int, input().split())
    v.append([i-1, j-1])

for s, e in v:
    conn[s][e] = conn[e][s] = True
def search(now, depth):
    if visited[now] is True:
        return 0
    if depth == n-1:
        return 1
    visited[now] = True
    ret = 0
    for i in range(n):
        if conn[now][i] is True:
            ret += search(i, depth+1)
    visited[now] = False
    return ret

print(search(0, 0))

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10**6)

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


def dfs(graph, visited, v):
    if all(visited):
        return 1

    cnt = 0
    for u in graph[v]:
        if visited[u]:
            continue
        visited[u] = True
        cnt += dfs(graph, visited, u)
        visited[u] = False

    return cnt


visited = [False] * len(graph)
visited[0] = True
ans = dfs(graph, visited, 0)
print(ans)