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: Runtime Error

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

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

check = [False] * N

def dfs(now):
    global cnt
    global ans
    if cnt == N:
        ans += 1
    else:
        for i in line[now]:
            if check[i] == False:
                check[i] = True
                cnt += 1
                dfs(i)
                check[i] = False
                cnt -= 1

check[0] = True
cnt = 1
ans = 0
dfs(0)
print(ans)

Submission status: Runtime Error

Solution code:
import bisect, collections, copy, heapq, itertools, math, string, sys
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = float('inf')
def I(): return int(input())
def F(): return float(input())
def SS(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LSS(): return input().split()

def resolve():
    N, M = LI()
    G = [[] for _ in range(N)]
    for _ in range(M):
        a, b = LI_()
        G[a].append(b)
        G[b].append(a)

    ans = [0]
    visited = [False] * N
    def dfs(depth, c):
        visited[c] = True
        if depth == N - 1:
            ans[0] += 1
        else:
            for n in G[c]:
                if not visited[n]:
                    dfs(n, depth + 1)
                    visited[n] = False

    dfs(0, 0)

    print(ans[0])

if __name__ == '__main__':
    resolve()

Submission status: Runtime Error

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

c = [i for i in range(2, n + 1)]
b = []
for x in itertools.permutations(c):
  b.append([1] + list(x))
  
cnt = 0
for x in b:
  exist = True
  for i in range(n-1):
    if not sorted(x[i:i+2]) in a:
      exist = False
      break
  if exist:
    cnt += 1

print(cnt)

Submission status: Runtime Error

Solution code:
import itertools as it

n,m=map(int,input().split())
ans=[]
for i in range(n):
    a,b=map(int,input().split())
    ans.append([a,b])
    ans.append([b,a])
  
a=0
for e in it.permutations(range(n)):
    #print(e)
    count=1
    if e[0]!=0:
        break
    
    for i in range(n-1):
        if [e[i]+1,e[i+1]+1] in ans:
            count*=1
        else:
            count*=0
            break
            
    a+=count
    
print(a)

Submission status: Runtime Error

Solution code:
import itertools as it

n,m=map(int,input().split())
ans=[]
for i in range(n):
    a,b=map(int,input().split())
    ans.append([a,b])
    ans.append([b,a])
  
a=0
for e in it.permutations(range(n)):
    #print(e)
    count=1
    if e[0]!=0:
        break
    
    for i in range(len(e)-1):
        if [e[i]+1,e[i+1]+1] in ans:
            count*=1
        else:
            count*=0
            break
            
    a+=count
    
print(a)

Submission status: Runtime Error

Solution code:
import itertools as it

n,m=map(int,input().split())
ans=[]
for i in range(n):
    a,b=map(int,input().split())
    ans.append([a,b])
    ans.append([b,a])
  
a=0
for e in it.permutations(range(n)):
    count=0
    if e[0]!=0:
        break
    
    for i in range(len(e)-1):
        if [e[i]+1,e[i+1]+1] in ans:
            count*=1
        else:
            count*=0
            break
            
    a+=count
    
print(a)

Submission status: Runtime Error

Solution code:
import itertools as it

n,m=map(int,input().split())
ans=[]
for i in range(n):
    a,b=map(int,input().split())
    ans.append([a,b])
    ans.append([b,a])
  
a=0
for e in it.permutations(range(n)):
    count=0
    if e[0]!=0:
        break
    
    for i in range(len(e)-1):
        if [e[i]+1,e[i+1]+1] in ans:
            count=1
        else:
            count*=0
            
    a+=count
    
print(a)

Submission status: Runtime Error

Solution code:
import itertools as it

n,m=map(int,input().split())
ans=[]
for i in range(n):
    a,b=map(int,input().split())
    ans.append([a,b])
    ans.append([b,a])
  
a=0
for e in it.permutations(range(n)):
    count=0
    if e[0]!=0:
        break
    
    for i in range(len(e)-1):
        if [e[i]+1,e[i+1]+1] in ans:
            count=1
        else:
            count=0
            
    a+=count
    
print(a)

Submission status: Runtime Error

Solution code:
import itertools as it

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

for e in it.permutations(range(n)):
    count,a=0,0
    if e[0]!=0:
        break
    
    for i in range(len(e)-1):
        if [e[i]+1,e[i+1]+1] in ans:
            count=1
        else:
            count=0
            
    a+=count
    
print(a)

Submission status: Runtime Error

Solution code:
import itertools as it

n,m=map(int,input().split())
ans=[]
for i in range(n):
    a,b=map(int,input().split())
    ans.append([a,b])
    ans.append([b,a])
  
count,a=0,0
for e in it.permutations(range(n)):
    if e[0]!=0:
        break
    
    for i in range(len(e)-1):
        if [e[i]+1,e[i+1]+1] in ans:
            count=1
        else:
            count=0
            
    a+=count
    
print(a)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10000000)
n,m = map(int,input().split())
graph = [list(input().split(" ")) for i in range(n)]

result=0

def dfs(a, list, graph,  result):
  if len(list) == n:
    result = result + 1

  for g in graph:
    if g[0] == a and g[1] not in list:
      list.append(g[1])
      result = dfs(g[1], list, graph, result)
    if g[1] == a and g[0] not in list:
      list.append(g[0])
      result = dfs(g[0], list, graph, result)

  return result

for g in graph:
  list = []
  if g[0] == "1":
    list.append(1)
    result += dfs("1", list, graph, 0)

print(result)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(100000)
n,m = map(int,input().split())
graph = [list(input().split(" ")) for i in range(n)]

result=0

def dfs(a, list, graph,  result):
  if len(list) == n:
    result = result + 1

  for g in graph:
    if g[0] == a and g[1] not in list:
      list.append(g[1])
      result = dfs(g[1], list, graph, result)
    if g[1] == a and g[0] not in list:
      list.append(g[0])
      result = dfs(g[0], list, graph, result)

  return result

for g in graph:
  list = []
  if g[0] == "1":
    list.append(1)
    result += dfs("1", list, graph, 0)

print(result)

Submission status: Runtime Error

Solution code:
import sys
n,m = map(int,input().split())
graph = [list(input().split(" ")) for i in range(n)]

result=0

def dfs(a, list, graph,  result):
  print(list)
  if len(list) == n:
    result = result + 1

  for g in graph:
    if g[0] == a and g[1] not in list:
      list.append(g[1])
      result = dfs(g[1], list, graph, result)
    if g[1] == a and g[0] not in list:
      list.append(g[0])
      result = dfs(g[0], list, graph, result)

  return result

for g in graph:
  list = []
  if g[0] == "1":
    list.append(1)
    result += dfs("1", list, graph, 0)

print(result)

Submission status: Runtime Error

Solution code:
import itertools as it
import sys

N, M = map(int, input().split())
if N==0 or M==0:
    print(0)
    sys.exit()
a=[]

for i in range(N):
    x,y=map(int,input().split())
    a.append([x,y])
    a.append([y,x])

ans=0
for e in it.permutations(range(N)):
    if e[0]!=0:
        break
        
    count=1
    for j in range(N-1):
        if [e[j]+1,e[j+1]+1] in a:
            count*=1
        else:
            count*=0
            break
            
    ans+=count

print(ans)

Submission status: Runtime Error

Solution code:
import itertools as it
import sys

N, M = map(int, input().split())
if N==0 or M==0:
    print(0)
    sys.exit()
a=[]

for i in range(N):
    x,y=map(int,input().split())
    a.append([x,y])
    a.append([y,x])

ans=0
for e in it.permutations(range(N)):
    if e[0]!=0:
        break
        
    count=1
    for j in range(M-1):
        if [e[j]+1,e[j+1]+1] in a:
            count*=1
        else:
            count*=0
            break
            
    ans+=count

print(ans)

Submission status: Runtime Error

Solution code:
import itertools as it

N, M = map(int, input().split())
a=[]

for i in range(N):
    x,y=map(int,input().split())
    a.append([x,y])
    a.append([y,x])

ans=0
for e in it.permutations(range(N)):
    if e[0]!=0:
        break
        
    count=1
    for j in range(M-1):
        if [e[j]+1,e[j+1]+1] in a:
            count*=1
        else:
            count*=0
            break
            
    ans+=count

print(ans)

Submission status: Runtime Error

Solution code:
from collections import defaultdict
n, m = map(lambda x: int(x), input().split())

links = defaultdict(set)

for _ in range(m):
    a, b = map(lambda x: int(x), input().split())
    links[a].add(b)
    links[b].add(a)
    
path_counter = 0
    
def path_patterns_number(current_node, remaining_nodes):#, remaining_links):
#     print(current_node, remaining_nodes)
    if len(remaining_nodes) == 0:
        return 1
    
    patterns = 0
    
    for next_node in (links[current_node] & remaining_nodes):
#         remaining_links_copy = remaining_links.copy()
#         remaining_links_copy[current_node].remove(next_node) <=浅いコピーなので元のからもremoveされてる
        patterns += path_patterns_number(
            next_node,
            remaining_nodes.copy() - {next_node}
#             remaining_links_copy
        )
    
    return patterns
    
print(path_patterns_number(1, set(range(2,n+1)))#, links))

Submission status: Runtime Error

Solution code:
import itertools
from math import factorial as fa
P = itertools.permutations(list(range(n)))
n, m = map(int, input().split())
G = [set() for _ in range(n)]
for _ in range(m):
    a,b = map(lambda x:int(x)-1, input().split())
    G[a].add(b)
    G[b].add(a)

ans = 0
for _ in range(fa(n)):
    p = next(P)
    if p[0] != 0:
        break
    f = True
    for pnw,pnx in zip(p,p[1:]):
        if not pnx in G[pnw]:
            f = False
            break
    if f:
        ans += 1
print(ans)

Submission status: Runtime Error

Solution code:

#入力

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

graph = [ ]
for _ in range(N+1):
    graph.append([])

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

visited = []
for _ in range(N+1):
    visited.append(False)


def dfs(dep,cur):
    global N,visited,graph

    if dep == N:
        ans += 1
        return 1

        ans = 0

    for dist in graph[cur]:
        if visited[dist] == False:
            visited[dist] = True
            ans += dfs(dep + 1,dist)
            visited[dist] = False
    return ans

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

Submission status: Runtime Error

Solution code:
from itertools import permutations
import copy
def resolve():
    N, M = list(map(int, input().split()))
    G = [[0]*N for _ in range(M)]
    for i in range(M):
        a, b = list(map(int, input().split()))
        G[a-1][b-1] = 1
        G[b-1][a-1] = 1

    ls = list(permutations(range(1, N)))
    ans = 0
    for l in ls:
        h = copy.deepcopy(G)
        cnt = 1
        p = 0 
        for k in l:
            if h[p][k] == 0:
                break
            else:
                cnt += 1
                p = k
        if cnt == N:
            ans += 1
    print(ans)
    return
resolve()

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-

# 関数定義
def dfs(now_p, visited, comb_p, p_num):
    # N頂点と同じ数のルートを通ったら有効なパスとして1を返す
    if len(visited) == p_num:
        return 1

    ans = 0

    # now_pの検索
    for tmp_p in comb_p:
        if tmp_p[0] == now_p and tmp_p[1] not in visited:
            # visitedのtmp
            tmp_visited = visited[:]
            tmp_visited.append(tmp_p[1])
            #print(*tmp_visited)
            # 次の頂点
            next_p = tmp_p[1]
            #print('next_p: ', next_p)
            # comb_pのtmp
            tmp_comb = comb_p[:]
            tmp_comb.remove(tmp_p)
            # 往復対象の削除
            tmp_p_r = [tmp_p[1], tmp_p[0]]
            tmp_comb.remove(tmp_p_r)
            #print(*tmp_comb)
            # dfsの再起呼び出し
            ans += dfs(next_p, tmp_visited, tmp_comb, p_num)

    return ans

## 入力読み取り
N, M = map(int, input().split())
a_b = []
tmp = []
tmp_r = []

# 辺読み取り
for i in range(N):
    tmp = list(map(int, input().split()))
    tmp_r = [tmp[1], tmp[0]]
    a_b.append(tmp)
    a_b.append(tmp_r)

visited = [1]

# 再起関数の実施
pass_num = dfs(1, visited, a_b, N)
print(pass_num)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-

# 関数定義
def dfs(now_p, visited, comb_p, p_num):
    # N頂点と同じ数のルートを通ったら有効なパスとして1を返す
    if len(visited) == p_num:
        return 1

    ans = 0

    # now_pの検索
    for tmp_p in comb_p:
        if tmp_p[0] == now_p:
            # visitedのtmp
            tmp_visited = visited[:]
            tmp_visited.append(tmp_p[1])
            #print(*tmp_visited)
            # 次の頂点
            next_p = tmp_p[1]
            #print('next_p: ', next_p)
            # comb_pのtmp
            tmp_comb = comb_p[:]
            tmp_comb.remove(tmp_p)
            # 往復対象の削除
            tmp_p_r = [tmp_p[1], tmp_p[0]]
            tmp_comb.remove(tmp_p_r)
            #print(*tmp_comb)
            # dfsの再起呼び出し
            ans += dfs(next_p, tmp_visited, tmp_comb, p_num)

    return ans

## 入力読み取り
N, M = map(int, input().split())
a_b = []
tmp = []
tmp_r = []

# 辺読み取り
for i in range(N):
    tmp = list(map(int, input().split()))
    tmp_r = [tmp[1], tmp[0]]
    a_b.append(tmp)
    a_b.append(tmp_r)

visited = [1]

# 再起関数の実施
pass_num = dfs(1, visited, a_b, N)
print(pass_num)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-

# 関数定義
def dfs(now_p, visited, comb_p, p_num):
    # N頂点と同じ数のルートを通ったら有効なパスとして1を返す
    if len(set(visited)) == p_num - 1:
        return 1

    ans = 0

    # now_pの検索
    for tmp_p in comb_p:
        if tmp_p[0] == now_p:
            # comb_pのtmp
            tmp_comb = comb_p[:]
            tmp_comb.remove(tmp_p)
            # 往復対象の削除
            tmp_p_r = [tmp_p[1], tmp_p[0]]
            tmp_comb.remove(tmp_p_r)
            # visitedのtmp
            tmp_visited = visited[:]
            tmp_visited.append(tmp_p[0])
            #print(*tmp_visited, sep='')
            # 次の頂点
            next_p = tmp_p[1]
            #print('next_p: ', next_p)
            # dfsの再起呼び出し
            ans += dfs(next_p, tmp_visited, tmp_comb, p_num)

    return ans

## 入力読み取り
N, M = map(int, input().split())
a_b = []
tmp = []
tmp_r = []

# 辺読み取り
for i in range(N):
    tmp = list(map(int, input().split()))
    tmp_r = [tmp[1], tmp[0]]
    a_b.append(tmp)
    a_b.append(tmp_r)

visited = []

# 再起関数の実施
pass_num = dfs(1, visited, a_b, N)
print(pass_num)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-

# 関数定義
def dfs(now_p, visited, comb_p, p_num):
    # N頂点と同じ数のルートを通ったら有効なパスとして1を返す
    if len(visited) == p_num - 1:
        #print('get the paass!!')
        return 1

    ans = 0

    # now_pの検索
    for tmp_p in comb_p:
        if tmp_p[0] == now_p and tmp_p[0] not in visited:
            # comb_pのtmp
            tmp_comb = comb_p[:]
            tmp_comb.remove(tmp_p)
            # 往復対象の削除
            tmp_p_r = [tmp_p[1], tmp_p[0]]
            tmp_comb.remove(tmp_p_r)
            # visitedのtmp
            tmp_visited = visited[:]
            tmp_visited.append(tmp_p[0])
            #print(*tmp_visited, sep='')
            # 次の頂点
            next_p = tmp_p[1]
            #print('next_p: ', tmp_p[1])
            # dfsの再起呼び出し
            ans += dfs(next_p, tmp_visited, tmp_comb, p_num)

    return ans

## 入力読み取り
N, M = map(int, input().split())
a_b = []
tmp = []
tmp_r = []

# 辺読み取り
for i in range(N):
    tmp = list(map(int, input().split()))
    tmp_r = [tmp[1], tmp[0]]
    a_b.append(tmp)
    a_b.append(tmp_r)

visited = []

# 再起関数の実施
pass_num = dfs(1, visited, a_b, N)
print(pass_num)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-

# 関数定義
def dfs(now_p, visited, comb_p, p_num):
    # N頂点と同じ数のルートを通ったら有効なパスとして1を返す
    if len(visited) == p_num - 1:
        return 1

    ans = 0

    # now_pの検索
    for tmp_p in comb_p:
        if tmp_p[0] == now_p and tmp_p[0] not in visited:
            # comb_pのtmp
            tmp_comb = comb_p[:]
            tmp_comb.remove(tmp_p)
            # 往復対象の削除
            tmp_p_r = [tmp_p[1], tmp_p[0]]
            tmp_comb.remove(tmp_p_r)
            # visitedのtmp
            tmp_visited = visited[:]
            tmp_visited.append(tmp_p[0])
            next_p = tmp_p[1]
            # dfsの再起呼び出し
            ans += dfs(next_p, tmp_visited, tmp_comb, p_num)

    return ans

## 入力読み取り
N, M = map(int, input().split())
a_b = []
tmp = []
tmp_r = []

# 辺読み取り
for i in range(N):
    tmp = list(map(int, input().split()))
    tmp_r = [tmp[1], tmp[0]]
    a_b.append(tmp)
    a_b.append(tmp_r)

visited = []

# 再起関数の実施
pass_num = dfs(1, visited, a_b, N)
print(pass_num)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-

# 関数定義
def dfs(now_p, visited, comb_p, p_num):
    # N頂点と同じ数のルートを通ったら有効なパスとして1を返す
    if len(visited) == p_num - 1:
        return 1

    ans = 0

    # now_pの検索
    for tmp_p in comb_p:
        if tmp_p[0] == now_p and tmp_p[0] not in visited and tmp_p[1] not in visited:
            # comb_pのtmp
            tmp_comb = comb_p[:]
            tmp_comb.remove(tmp_p)
            # visitedのtmp
            tmp_visited = visited[:]
            tmp_visited.append(tmp_p[0])
            next_p = tmp_p[1]
            # dfsの再起呼び出し
            ans += dfs(next_p, tmp_visited, tmp_comb, p_num)

    return ans

## 入力読み取り
N, M = map(int, input().split())
a_b = []
tmp = []
tmp_r = []

# 辺読み取り
for i in range(N):
    tmp = list(map(int, input().split()))
    tmp_r = [tmp[1], tmp[0]]
    a_b.append(tmp)
    a_b.append(tmp_r)

visited = []

# 再起関数の実施
pass_num = dfs(1, visited, a_b, N)
print(pass_num)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-

# 関数定義
def dfs(now_p, visited, comb_p, p_num):
    # N頂点と同じ数のルートを通ったら有効なパスとして1を返す
    if len(visited) == p_num - 1:
        return 1

    ans = 0

    # now_pの検索
    for tmp_p in comb_p:
        if tmp_p[0] == now_p and tmp_p[0] not in visited and tmp_p[1] not in visited:
            # comb_pのtmp
            tmp_comb = comb_p[:]
            tmp_comb.remove(tmp_p)
            #print(*tmp_comb)
            # visitedのtmp
            tmp_visited = visited[:]
            tmp_visited.append(tmp_p[0])
            #print('visited :', tmp_p[0])
            next_p = tmp_p[1]
            #print('next :', next_p)
            # dfsの再起呼び出し
            ans += dfs(next_p, tmp_visited, tmp_comb, p_num)

    return ans

## 入力読み取り
N, M = map(int, input().split())
a_b = []
tmp = []
tmp_r = []

# 辺読み取り
for i in range(N):
    tmp = list(map(int, input().split()))
    tmp_r = [tmp[1], tmp[0]]
    a_b.append(tmp)
    a_b.append(tmp_r)

visited = []

# 再起関数の実施
pass_num = dfs(1, visited, a_b, N)
print(pass_num)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10**8)
n, m = map(int, input().split())
g = [[] for i in range(n)]
for  i in range(n):
    a, b = map(int, input().split())
    a-=1; b-=1
    g[a].append(b)
    g[b].append(a)

used = [False] * n
ans = 0
def dfs(itr, n, cnt=0):
    ans = 0
    if len(itr)==n:
        return 1
    else:
        ans = cnt
        for e in g[itr[-1]]:
            if used[e]:
                continue
            used[e] = True
            ans+=dfs(itr+[e], n)
            used[e] = False
    return ans

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

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10**8)
n, m = map(int, input().split())
g = [[] for i in range(n)]
for  i in range(n):
    a, b = map(int, input().split())
    a-=1; b-=1
    g[a].append(b)
    g[b].append(a)

used = [False] * n
ans = 0
def dfs(itr, n, cnt=0):
    if len(itr)==n:
        return 1
    else:
        ans = cnt
        for e in g[itr[-1]]:
            if used[e]:
                continue
            used[e] = True
            ans+=dfs(itr+[e], n)
            used[e] = False
        return ans

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

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10**8)
n, m = map(int, input().split())
g = [[] for i in range(n)]
for  i in range(n):
    a, b = map(int, input().split())
    a-=1; b-=1
    g[a].append(b)
    g[b].append(a)

used = [False] * n
ans = 0
def dfs(itr, n, cnt=0):
    if len(itr)==n:
        return 1
    elif len(itr)==0:
        ans = cnt
        for i in range(n):
            used[i] = True
            ans += dfs([i], n)
        return ans
    else:
        ans = cnt
        for e in g[itr[-1]]:
            if used[e]:
                continue
            used[e] = True
            ans+=dfs(itr+[e], n)
            used[e] = False
        return ans

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

Submission status: Runtime Error

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

used = [False] * n
ans = 0
def dfs(itr, n, cnt=0):
    if len(itr)==n:
        return 1
    elif len(itr)==0:
        ans = cnt
        for i in range(n):
            used[i] = True
            ans += dfs([i], n)
        return ans
    else:
        ans = cnt
        for e in g[itr[-1]]:
            if used[e]:
                continue
            used[e] = True
            ans+=dfs(itr+[e], n)
            used[e] = False
        return ans

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

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
import numpy as np

n,m = map(int, input().split())
graph = [[] for j in range(n)]
graph = np.array(graph)

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

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

def DFS(v,used):
    if all(used):
        return 1
    ans = 0
    for i in graph(v):
        if used[i]:
            continue
        used[i] = True
        ans += DFS(i,used)
        used[i] = False
    return ans
  
print(DFS(0,used))

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
import numpy as np

n,m = map(int, input().split())
graph = [[0 for i in range(n)] for j in range(n)]
graph = np.array(graph)

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

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

def DFS(v,used):
    if all(used):
        return 1
    ans = 0
    for i in graph(v):
        if used[i]:
            continue
        used[i] = True
        ans += DFS(i,used)
        used[i] = False
    return ans
  
print(DFS(0,used))

Submission status: Runtime Error

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

def dfs(v, seen):
    if all(seen):
        return 1
    ans=0
    for vv in graph[v]:
        if seen[vv]:
            continue
        seen[vv]=True
        ans+=dfs(vv, seen)
        seen[vv]=False
    return ans

seen=[False]*n
seen[0]=True
print(dfs(0, seen))

Submission status: Runtime Error

Solution code:
import itertools
N,M = map(int,input().split())
L=[]
for i in range(M):
    a,b=map(int,input().split())
    L.append([a,b])
 
number=[]
for i in range(1,N+1):
    number.append(i)
    
ans=0
 
for v in itertools.permutations(number,N):
    a=0
    v=list(v)
    for j in range(N-1):
        if ([v[j],v[j+1]] not in L ) and ([v[j+1],v[j]] not in L):
            a=1
    if a==0 and v[0]==1:
        ans+=1
 
print(ans)
import itertools
N,M = map(int,input().split())
L=[]
for i in range(M):
    a,b=map(int,input().split())
    L.append([a,b])
 
number=[]
for i in range(1,N+1):
    number.append(i)
    
ans=0
 
for v in itertools.permutations(number,N):
    a=0
    v=list(v)
    for j in range(N-1):
        if ([v[j],v[j+1]] not in L ) and ([v[j+1],v[j]] not in L):
            a=1
    if a==0 and v[0]==1:
        ans+=1
 
print(ans)

Submission status: Runtime Error

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

route = itertools.permutations([i for i in range(2,N+1)])


ans = 0
for i in route:
    count = 0
    for j in range(M):
        a,b = ab[j][0],ab[j][1]
        if i.index(a) == i.index(b)+1 or i.index(a) == i.index(b)-1:
            count += 1
            if count == M-1:
                ans +=1
            if count == M-1:
                ans +=1
    

print(ans)

Submission status: Runtime Error

Solution code:
import itertools

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

print(ab)
route = itertools.permutations([i for i in range(2,N+1)])

print(list(route_1))

ans = 0
for i in route:
    count = 0
    for j in range(M):
        a,b = ab[j][0],ab[j][1]
        if i.index(a) == i.index(b)+1 or i.index(a) == i.index(b)-1:
            count += 1
            print(count,i)
            if count == M-1:
                ans +=1

Submission status: Runtime Error

Solution code:
import itertools
N,M=map(int,input().split())
edges={tuplec(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: Runtime Error

Solution code:
import itertools
N,M=map(int,input().split())
edges={tuplec(sorted(map(int,input().split()))) for i in range(M)}
ans=0
for i in itertools.permutations(range(2,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: Runtime Error

Solution code:
import sys
import copy

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline

in_n = lambda: int(readline())
in_nn = lambda: map(int, readline().split())
in_nl = lambda: list(map(int, readline().split()))
in_na = lambda: map(int, read().split())
in_s = lambda: readline().rstrip().decode('utf-8')

sys.setrecursionlimit(1000000)


ans = 0


def bfs(N, edge, v, search):

    search |= {v}

    global ans
    if len(search) == N:
        ans += 1
        return

    for e in edge[v]:
        if e not in search:
            #print('test:{},{},{}'.format(e, v, search))
            bfs(N, edge, e, copy.copy(search))


def main():

    N, M = in_nn()

    edge = [[] for _ in range(M)]

    for i in range(M):
        a, b = in_nn()
        a, b = a - 1, b - 1
        edge[a].append(b)
        edge[b].append(a)

    bfs(N, edge, 0, set())

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0; i<(n); i++)
using namespace std;
using vi = vector<int>;
using vv = vector<vi>;

int main(){
    int n,m;
    cin>>n>>m;
    
    vv road(n, vi (n,0));
    
    rep(i,m){
        int a,b;
        cin >> a >> b;
        a--;b--;
        road[a][b] = 1;
        road[b][a] = 1;
    }
    
    vi p(n);
    rep(i,n)p[i]=i;
    
    int ans = 0;
    
    do{
        bool ok = true;
        if(p[0]!=0)continue;
        for(int i=1; i<n; i++){
            if(road[p[i-1]][p[i]])continue;
            ok = false;
            break;
        }
        if(ok)ans++;
    } while(next_permutation(p.begin(), p.end()));
    
    cout << ans << endl;
    
    return 0;
}

Submission status: Runtime Error

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

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

for _ in range(M):
	a,b = map(int,input(),split())
	path[a-1],append(b-1)
    path[b-1],append(a-1)
vis = [0 for i in range(N)]
cnt = 0

def dfs(now,path):
	global cnt
  	if depth == N: cnt+=1
	for new in path[now]:
    	if vis[new] == 0:
			vis[new] = 1
        	dfs(new,depth+1)
          	vis[new] = 0

vis[0] = 1
dfs(0,1)
print(cnt)

Submission status: Runtime Error

Solution code:
import itertools as it
n,m=map(int,input().split())
path={[] for _ in range(m)}
for i in range(m): path[i]=list(map(int,input().split()))
ls=list(it.permutations(range(1,n+1)))
cnt=0
for l in ls:
    if l[0]==1: break
    for i in range(n-1):
        if [i,i+1] in path: cnt+=1
print(cnt)

Submission status: Runtime Error

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

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

count = 0

def dfs(i, now, done):
    global count
    if i == N-1:
        count += 1
        return

    for j in ab[now]:
        if j not in done:
            dfs(i+1, j, done + [j])
    return

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

Submission status: Runtime Error

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

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

count = 0

def dfs(i, now, done):
    global count
    if i == N-1:
        count += 1
        return

    for j in ab[now]:
        if j not in done:
            dfs(i+1, j, done + [j])
    return

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

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
ab = []
for _ in range(n):
  a,b=map(int,input().split())
  a,b=a-1,b-1
  ab.append({a,b})
import itertools

cnt = 0
for v in itertools.permutations(range(1,n)):
  l = 0
  ok = True
  for v2 in v:
    if {l,v2} not in ab:
      ok = False
      break
    l = v2
  if ok:
    #print(v)
    cnt += 1
  
print(cnt)

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
ab = []
for _ in range(n):
  a,b=map(int,input().split())
  a,b=a-1,b-1
  ab.append({a,b})
import itertools

cnt = 0
for v in itertools.permutations(range(1,n)):
  l = 0
  ok = True
  for v2 in v:
    if {l,v2} not in ab:
      ok = False
      break
    l = v2
  if ok:
    print(v)
    cnt += 1
  
print(cnt)