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:
import itertools

n,m = map(int,input().split())
path=[[False]*n for _ in range(n)]
for _ in range(m):
  a,b = map(int,input().split())
  a-=1
  b-=1
  path[a][b]=True
  path[b][a]=True
ans=0
for i in itertools.permutations(range(n),n):
  if i[0]==0:
    for j in rannge(n-1):
      if j ==n-1:
        ans+=1
      if not path[i[j]][i[j+1]]:
        break
print(ans)

Submission status: Runtime Error

Solution code:
import itertools

n,m = map(int,input().split())
path=[[False]*n for _ in range(m)]
for _ in range(m):
  a,b = map(int,input().split())
  a-=1
  b-=1
  path[a][b]=True
  path[b][a]=True
ans=0
for i in itertools.permutations(range(n),n):
  if i[0]==0:
    for j in rannge(n-1):
      if j ==n-1:
        ans+=1
      if not path[i[j]][i[j+1]]:
        break
print(ans)

Submission status: Runtime Error

Solution code:
def main():
    _, __ = map(int, input().split())
    ___ = [[] for _ in range(_)]
    for _ in range(__):
        ____, _____ = map(lambda ______: int(_____) - 1, input().split())
        ___[____].append(_____)
        ___[_____].append(____)

    _______ = [False] * _
    ________ = ___________(0, ___, _______, 0)

    print(________)


def ___________(_____, ___, _______, _________):
    _______[_____] = True
    if all(_______):
        return _________ + 1

    for __________ in ___[_____]:
        if _______[__________]:
            continue
        _________ = ___________(__________, ___, _______, _________)
        _______[__________] = False

    return _________


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
from itertools import *

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

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

ans = 0

for p in permutations(range(N)):
    if p[0]!=1:
        continue
    
    flag = True
    
    for i in range(N-1):
        if p[i+1] not in G[p[i]]:
            flag = False
    
    if flag:
        ans += 1

print(ans)

Submission status: Runtime Error

Solution code:
from sys import setrecursionlimit
setrecursionlimit(4100000)
n, m = map(int, input().split())
P = [[] for i in range(m)]   #Pass
for i in range(m):
    a, b = map(int, input().split())
    a, b = a - 1, b - 1  
    P[a].append(b)
    P[b].append(a)
#print(P)

c = 0   #cursol
R = [0 for i in range(m)]  #Record
tm = 1  #time

def all_search_dfs(c:int, tm:int, R:list):
    if R[c] == 0:
        R[c] = 1
        if  tm < n:
            return point_calculate(c, tm, R)
        elif tm == n:
            return 1
        else:
            return 0
    else:
        return 0

def point_calculate(c:int, tm:int, R:list):
    #print('c = ', c)
    p = 0
    #print('check = ', P[c])
    for i in range(len(P[c])):
        R2 = R[:]
        #print('before = ', R2)
        tmp = all_search_dfs(P[c][i], tm + 1, R2)
        #print('after = ', R2)
        #print('tmp = ', tmp)
        p += tmp
        #print('p = ', p)
    return p

print(all_search_dfs(c, tm, R))

Submission status: Runtime Error

Solution code:
from sys import setrecursionlimit
setrecursionlimit(10 ** 10)
n, m = map(int, input().split())
P = [[] for i in range(m)]   #Pass
for i in range(m):
    a, b = map(int, input().split())
    a, b = a - 1, b - 1  
    P[a].append(b)
    P[b].append(a)
#print(P)

c = 0   #cursol
R = [0 for i in range(m)]  #Record
tm = 1  #time

def all_search_dfs(c:int, tm:int, R:list):
    if R[c] == 0:
        R[c] = 1
        if  tm < n:
            return point_calculate(c, tm, R)
        elif tm == n:
            return 1
        else:
            return 0
    else:
        return 0

def point_calculate(c:int, tm:int, R:list):
    #print('c = ', c)
    p = 0
    #print('check = ', P[c])
    for i in range(len(P[c])):
        R2 = R[:]
        #print('before = ', R2)
        tmp = all_search_dfs(P[c][i], tm + 1, R2)
        #print('after = ', R2)
        #print('tmp = ', tmp)
        p += tmp
        #print('p = ', p)
    return p

print(all_search_dfs(c, tm, R))

Submission status: Runtime Error

Solution code:
from sys import setrecursionlimit
setrecursionlimit(10 ** 7)
n, m = map(int, input().split())
P = [[] for i in range(m)]   #Pass
for i in range(m):
    a, b = map(int, input().split())
    a, b = a - 1, b - 1  
    P[a].append(b)
    P[b].append(a)
#print(P)

c = 0   #cursol
R = [0 for i in range(m)]  #Record
tm = 1  #time

def all_search_dfs(c:int, tm:int, R:list):
    if R[c] == 0:
        R[c] = 1
        if  tm < n:
            return point_calculate(c, tm, R)
        elif tm == n:
            return 1
        else:
            return 0
    else:
        return 0

def point_calculate(c:int, tm:int, R:list):
    #print('c = ', c)
    p = 0
    #print('check = ', P[c])
    for i in range(len(P[c])):
        R2 = R[:]
        #print('before = ', R2)
        tmp = all_search_dfs(P[c][i], tm + 1, R2)
        #print('after = ', R2)
        #print('tmp = ', tmp)
        p += tmp
        #print('p = ', p)
    return p

print(all_search_dfs(c, tm, R))

Submission status: Runtime Error

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][j+1]]:
        break
        
print(ans)

Submission status: Runtime Error

Solution code:
import itertools
import sys

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

if M < N-1:
  print(0)
  sys.exit()

p = [i for i in range(N)] #0スタート
root = []

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

#print(root)
pattern = list(itertools.permutations(p))

ans = 0
for i in range(len(pattern)):
  Flag = [0]*N
  Flag[0] = 1
  now = 0
  last = False
  for j in range(N-1):
    if now == root[pattern[i][j]][0]:
      now = root[pattern[i][j]][1]
    elif now == root[pattern[i][j]][1]:
      now = root[pattern[i][j]][0]
    else:
      break
    if Flag[now] != 0:
      break
    else:
      Flag[now] = 1
      if j == N-2:
        last = True
  if last:
    ans += 1
print(ans)

Submission status: Runtime Error

Solution code:
import itertools

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

p = [i for i in range(N)] #0スタート
root = []

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

#print(root)
pattern = list(itertools.permutations(p))

ans = 0
for i in range(len(pattern)):
  Flag = [0]*N
  Flag[0] = 1
  now = 0
  last = False
  for j in range(N-1):
    if now == root[pattern[i][j]][0]:
      now = root[pattern[i][j]][1]
    elif now == root[pattern[i][j]][1]:
      now = root[pattern[i][j]][0]
    else:
      break
    if Flag[now] != 0:
      break
    else:
      Flag[now] = 1
      if j == N-2:
        last = True
  if last:
    ans += 1
print(ans)

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())
color = [0] * n 
path = [[] for _ in range(m)]

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

print(path)
def rec(c, p, crnt, d):
    d += 1
    if c[crnt] == 1:
        if len(list(filter(lambda x: x == 1, c))) == m and d == m+1:
            return 1
        else:
            return 0
    elif c[crnt] > 1:
        return 0
    else:
        c[crnt] += 1
        sm = 0
        for i in p[crnt]:
            sm += rec(c, p, i-1, d)
        return sm

print(rec(color, path, 0, 0))

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())
color = [0] * n 
path = [[] for _ in range(m)]

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

def rec(c, p, crnt, d):
    d += 1
    if c[crnt]:
        if len(list(filter(lambda x: x == 1, c))) == m and d == m+1:
            return 1
        else:
            return 0
    else:
        c[crnt] = 1
        sm = 0
        for i in p[crnt]:
            sm += rec(c, p, i-1, d)
        return sm

print(rec(color, path, 0, 0))

Submission status: Runtime Error

Solution code:
def DFS(num):
    global ans,color
    color[num]="black"
    if "white" not in color:
        ans +=1
    for i in M[num]:
        DFS(i)
    color[num]="white"


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

M=[[] for _ in range(n)]
color=["white" for _ in range(n)]
for a,b in AB:
    M[a-1].append(b-1)
    M[b-1].append(a-1)

ans=0
DFS(0)
print(ans)

Submission status: Runtime Error

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

A = [list(map(int, input().split()))  for i in range(M)]

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

for i in range(M):
    if A[i][0] > A[i][1]: A[i][0], A[i][1] = A[i][1], A[i][0]
    graph_data[A[i][0]-1][A[i][1]-1] = graph_data[A[i][1]-1][A[i][0]-1] = 1
    
visited = [False] * N

def dfs(now, depth):
    if visited[now]:
        return 0
    if depth == N - 1:
        return 1
    
    visite[now] = True
    total_path = 0
    for i in range(0,N):
        if graph_data[now][i] == 1: 
            total_path +=  dfs(i, depth + 1)
    visited[now] = False
    
    return total_path

print(dfs(0,0))

Submission status: Runtime Error

Solution code:

def dfs(node, paths, visited, n):
  # 全て訪問済みだったら全部を訪問できる経路として1を返す
  if not False in visited:
    return 1

  count = 0

  for nn in paths[node]:
    # 既に訪問済みなら処理をしない
    if(visited[nn]):
      continue

    visited[nn] = True
    count += dfs(nn, paths, visited, n)
    visited[nn] = False

  return count

def main():
  N, M = list(map(int, input().split()))
  paths = [[] for i in range(M)]
  visited = [False] * M

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

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


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
from itertools import permutations
n,m = map(int,input().split())
#rel = [list(map(int,input().split())) for i in range(n)]
rel_t = [[False for i in range(n)] for j in range(n)]

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

cnt=0
n_list = [i for i in range(n)]
for l in permutations(n_list,len(n_list)):
    if(l[0]!=1):
        continue
    judge=[rel_t[l[i]][l[i+1]] for i in range(n-1)]
    if all(judge):
        cnt+=1

print(cnt)

Submission status: Runtime Error

Solution code:
import itertools

n,m = map(int,input().split())
path=[[False]*n for _ in range(n)]
for _ 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(6), 6):
   if i[0] == 0:
     for j in range(n):
       if j==n-1:
         ans+=1
         break
       if not path[i[j]][i[j+1]]:
         break

print(ans)

Submission status: Runtime Error

Solution code:
import itertools

n,m = map(int,input().xplit())
path=[[False]*n for _ in range(n)]
for _ 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(6), 6):
   if i[0] == 0:
     for j in range(n):
       if j==n-1:
         ans+=1
         break
       if not path[i[j]][i[j+1]]:
         break

print(ans)

Submission status: Runtime Error

Solution code:
import itertools

n,m = map(int,input().xplit())
path=[[False]*n for _ in range(n)]
for _ 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(6), 6):
   if i[0] == 0:
     for j in range(n):
       if j==n-1:
         ans+=1
         break
       if not path[i[j-1]][i[j]]:
         break

print(ans)

Submission status: Runtime Error

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

import itertools
li = [i for i in range(1,n)]
count = 0
for p in itertools.permutations(li, len(li)):
    for i in range(len(p) -1)
        if l[p[i]][p[i + 1]] == 0:
            break
        count += 1

print(count)

Submission status: Runtime Error

Solution code:
def dfs(g, seen, n):
    all_seen = True

    for si in seen:
        if si == False:
            all_seen = False

    if all_seen:
        return 1

    ans = 0

    for m in g[n]:
        if seen[m]:
            continue

        seen[m] = True
        ans += dfs(g, seen, m)
        seen[m] = False

    return ans


def main():
    n, m = map(int, stdin.readline().split())
    ab = [map(int, stdin.readline().split()) for _ in range(n)]
    g = [[] for _ in range(n)]
    for abi in ab:
        a, b = abi
        g[a - 1].append(b - 1)
        g[b - 1].append(a - 1)
    seen = [False for _ in range(n)]
    seen[0] = True

    ans = dfs(g, seen, 0)

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
from sys import stdin


def dfs(g, seen, n, ans):
    all_seen = True

    for si in seen:
        if si == False:
            all_seen = False

    if all_seen:
        ans += 1
        return ans

    for m in g[n]:
        if seen[m]:
            continue

        seen[m] = True
        ans = dfs(g, seen, m, ans)
        seen[m] = False

    return ans


def main():
    n, m = map(int, stdin.readline().split())
    ab = [map(int, stdin.readline().split()) for _ in range(n)]
    g = [[] for _ in range(n)]
    for abi in ab:
        a, b = abi
        g[a - 1].append(b - 1)
        g[b - 1].append(a - 1)
    seen = [False for _ in range(n)]
    seen[0] = True

    ans = 0

    ans = dfs(g, seen, 0, ans)

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
def dfs(g, seen, n, ans):
    all_seen = True

    for si in seen:
        if si == False:
            all_seen = False

    if all_seen:
        ans += 1
        return ans

    for m in g[n]:
        if seen[m]:
            continue

        seen[m] = True
        ans = dfs(g, seen, m, ans)
        seen[m] = False

    return ans


def main():
    n, m = map(int, stdin.readline().split())
    ab = [map(int, stdin.readline().split()) for _ in range(n)]
    g = [[] for _ in range(n)]
    for abi in ab:
        a, b = abi
        g[a - 1].append(b - 1)
        g[b - 1].append(a - 1)
    seen = [False for _ in range(n)]
    seen[0] = True

    ans = 0

    ans = dfs(g, seen, 0, ans)

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
from sys import stdin


def dfs(g, seen, n):
    all_seen = True

    for si in seen:
        if si == False:
            all_seen = False

    if all_seen:
        return 1

    count = 0

    for m in g[n]:
        if seen[m]:
            continue

        seen[m] = True
        count += dfs(g, seen, m)
        seen[m] = False

    return count


def main():
    n, m = map(int, stdin.readline().split())
    ab = [map(int, stdin.readline().split()) for _ in range(n)]
    g = [[] for _ in range(n)]
    for abi in ab:
        a, b = abi
        g[a - 1].append(b - 1)
        g[b - 1].append(a - 1)
    seen = [False for _ in range(n)]
    seen[0] = True

    ans = dfs(g, seen, 0)

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
import itertools

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

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

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

count = 0
for i in itertools.permutations(list(range(1,N)),N-1):
    s = 0
    for j in range(N-1):
        if i[j] not in lis[s]:
            break
        
        s = i[j]
    else:
        count += 1
    

print(count)

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())  #頂点, 辺
g = [[] for _ in range(M)]  #iはjと繋がっている
for i in range(M):
    u, v = map(int, input().split())
    if u > v:
        u, v = v, u
    g[u-1].append(v-1)
    g[v-1].append(u-1)

is_checked = [False] * N

def dfs(i):
    cnt = 0
    is_checked[i] = True
    for j in g[i]:
        if not(is_checked[j]):
            dfs(j)
        if not(False in is_checked):
            cnt += 1
    return cnt
            
ans = dfs(0)
print(ans)

Submission status: Runtime Error

Solution code:
q=[]
qq=[]
def dfs(j,q,icnt,count,n,qq):
    if len(qq)==n:
        count+=1
#        print("1",n,j,icnt,count,q[j],qq)
        return count
    icnt+=1
    
    for j2 in q[j]:
        if not j2 in qq:
            qq.append(j2)
#            print("2",n,j,icnt,count,q[j],qq)
            count=dfs(j2,q,icnt,count,n,qq)
            qq.pop()
#        print("3",n,j,icnt,count,q[j],qq)
    return count

n,m=map(int,input().split())
q=[[0]*2 for i in range(m)]
for i in range(m):
    q[i]=list(map(int,input().split()))

#n=3
#m=3
#ab=[[1,2],[1,3],[2,3]]

#n=7
#m=7
#ab=[[1,3],[2,7],[3,4],[4,5],[4,6],[5,6],[6,7]]

q=[[]*2 for i in range(n)]
for i in range(m):
    if not q[ab[i][1]-1] in q[ab[i][0]-1]:
        q[ab[i][0]-1].append(ab[i][1]-1)    
    if not q[ab[i][0]-1] in q[ab[i][1]-1]:
        q[ab[i][1]-1].append(ab[i][0]-1)    
#print(q)    

count=0
j=0
qq=[j]
icnt=1
count=dfs(j,q,icnt,count,n,qq)
print(count)

Submission status: Runtime Error

Solution code:
q=[]
qq=[]
def dfs(j,q,icnt,count,n,qq):
    if len(qq)==n:
        count+=1
#        print("1",n,j,icnt,count,q[j],qq)
        return count
    icnt+=1
    
    for j2 in q[j]:
        if not j2 in qq:
            qq.append(j2)
#            print("2",n,j,icnt,count,q[j],qq)
            count=dfs(j2,q,icnt,count,n,qq)
            qq.pop()
#        print("3",n,j,icnt,count,q[j],qq)
    return count

n,m=map(int,input().split())
q=[[0]*2 for i in range(m)]
for i in range(m):
    q[i]=set(map(int,input().split()))

#n=3
#m=3
#ab=[[1,2],[1,3],[2,3]]

#n=7
#m=7
#ab=[[1,3],[2,7],[3,4],[4,5],[4,6],[5,6],[6,7]]

q=[[]*2 for i in range(n)]
for i in range(m):
    if not q[ab[i][1]-1] in q[ab[i][0]-1]:
        q[ab[i][0]-1].append(ab[i][1]-1)    
    if not q[ab[i][0]-1] in q[ab[i][1]-1]:
        q[ab[i][1]-1].append(ab[i][0]-1)    
#print(q)    

count=0
j=0
qq=[j]
icnt=1
count=dfs(j,q,icnt,count,n,qq)
print(count)

Submission status: Runtime Error

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

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

def dfs(v, used):
    if not False in used:
        return 1

    ans = 0
    for i in range(N):
        if not adj_matrix[v][i]:
            continue
        if used[i]:
            continue
        used[i] = True
        ans += dfs(i, used)
        used[i] = False        
    return ans

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

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
def add_node(a, b, dic):
    if a-1 in dic.keys():
        dic[a-1].append(b-1)
    else:
        dic[a-1] = [b-1]
def dfs(point, c):
    global count
    if c == N:
        count +=1
        return
    if passlist[point]  == 1:
        return
    passlist[point]  = 1
    for n in node[point]:
        dfs(n, c+1)
    passlist[point] = 0
node  = {}
for n in range(N):
    a, b = map(int, input().split())
    add_node(a, b, node)
    add_node(b, a, node)
passlist = [0]*N
count = 0
dfs(0, 0)
print(count)

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
def add_node(a, b, dic):
    if a-1 in dic.keys():
        dic[a-1].append(b-1)
    else:
        dic[a-1] = [b-1]
def dfs(point, c):
    global count
    if c == N:
        count +=1
        return
    if passlist[point]  == 1:
        return
    passlist[point]  = 1
    for n in node[point]:
        dfs(n, c+1)
node  = {}
for n in range(N):
    a, b = map(int, input().split())
    add_node(a, b, node)
    add_node(b, a, node)
passlist = [0]*N
count = 0
dfs(0, 0)
print(count)

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
def add_node(a, b, dic):
    if a in dic.keys():
        dic[a].append(b)
    else:
        dic[a] = [b]
def dfs(point, c):
    global count
    if c == N:
        count +=1
        return
    if passlist[point-1]  == 1:
        return
    passlist[point-1]  = 1
    for n in node[point]:
        dfs(n, c+1)
node  = {}
for n in range(N):
    a, b = map(int, input().split())
    add_node(a, b, node)
    add_node(b, a, node)
passlist = [0]*N
count = 0
dfs(1, 0)
print(count)

Submission status: Runtime Error

Solution code:
import itertools

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

# 隣接行列を作る
for i in range(N):
    a, b = map(int, input().split())
    adj_matrix[a-1][b-1] = 1
    adj_matrix[b-1][a-1] = 1

cnt = 0

for each in itertools.permutations(range(N)):
    if each[0] != 0:  # 始点は1でないといけないから
        break
    factor = 1
    for i in range(N-1):
        factor *= adj_matrix[each[i]][each[i+1]]
    cnt += factor

print(cnt)

Submission status: Runtime Error

Solution code:
import itertools

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

# 隣接行列を作る
for i in range(N):
  a, b = map(int, input().split())
  adj_matrix[a-1][b-1] = 1
  adj_matrix[b-1][a-1] = 1
  
cnt = 0

for each in itertools.permutations(range(N)):
  if each[0] != 0:  # 始点は1でないといけないから
    break
  factor = 1
  for i in range(N-1):
    factor *= adj_matrix[each[i]][each[i+1]]
  cnt += factor

print(cnt)

Submission status: Runtime Error

Solution code:
from collections import defaultdict
import itertools

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

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

ans = 0
l = [i for i in range(1,n)]
for p in itertools.permutations(l):
  p = [0] + p
  reach = 1
  for i in range(n-1):
    if not e[p[i]][p[i+1]]:
      reach = 0
      break
  ans += reach

print(ans)

Submission status: Runtime Error

Solution code:
from itertools import permutations

nim,mike = list(map(int,input().split()))
array = [list(map(int,input().split())) for i in range(mike)]
counter = 0
for i in permutations(range(1,nim+1)):
  boo = True
  if i[0]==1:
    for i in range(nim-1):
      if sorted([i[i],i[i+1]]) not in array:
        boo = False
    if boo:
      counter+=1
print(counter)

Submission status: Runtime Error

Solution code:
N,M=map(int,input().split())
G=[[False]*(M+1) for _ in range(N+1)]
for i in range(M):
    a,b=map(int,input().split())
    G[a][b]=True
    G[b][a]=True

visited=[False]*(N+1)

visited[1]=True
def dfs(start):
    global N
    global visited
    all_visited=True
    sum=0

    for p in range(1,N+1):
        if not visited[p]:
            all_visited=False

    if all_visited:
        return 1
    else:
        for next in range(1,N+1):#N小より全探索
            if not G[start][next]:
                continue
            if visited[next]:
                continue
            visited[next]=True
            sum+=dfs(next)
            visited[next]=False   #backtrack

        return sum

print(dfs(1))

Submission status: Runtime Error

Solution code:
N,M=map(int,input().split())
G=[[False]*(M+1) for _ in range(N+1)]
for i in range(M):
    a,b=map(int,input().split())
    G[a][b]=True
    G[b][a]=True

visited=[False]*(N+1)

visited[1]=True
def dfs(start):
    global N
    global visited
    all_visited=True
    sum=0

    for p in range(1,N+1):
        if not visited[p]:
            all_visited=False

    if all_visited:
        return 1
    else:
        for next in range(1,N+1):#N小より全探索
            if not G[start][next]:
                continue
            if visited[next]:
                continue
            visited[next]=True
            sum+=dfs(next)
            visited[next]=False   #backtrack

    return sum

print(dfs(1))

Submission status: Runtime Error

Solution code:
import itertools

n,m = list(map(int,input().split()))
AB = [list(map(int,input().split())) for _ in range(m)]
ab = [[False]*n for _ in range(n)] 
for i in range(n):
  ab[AB[i][0]-1][AB[i][1]-1] = 1
  ab[AB[i][1]-1][AB[i][0]-1] = 1

ans = 0
for que in itertools.permutations(range(n), n):
  if que[0] == 0:
    for k in range(n):
      if k == n-1:
        ans += 1
      else:
        if ab[que[k]][que[k+1]] != 1:
          break
      

print(ans)

Submission status: Runtime Error

Solution code:
import itertools

n,m = list(map(int,input().split()))
AB = [list(map(int,input().split())) for _ in range(m)]
ab = [[False]*n for _ in range(n)] 
for i in range(n):
  ab[AB[i][0]-1][AB[i][1]-1] = 1
  ab[AB[i][1]-1][AB[i][0]-1] = 1

ans = 0
for i in itertools.permutations(range(n), n):
  if i[0] == 0:
    que = i
    cnt = 1
    for k in range(n-1):
      if ab[que[k]][que[k+1]] == 1:
        cnt += 1
    if cnt == n:
      ans += 1

print(ans)

Submission status: Runtime Error

Solution code:
import itertools

n,m = list(map(int,input().split()))
AB = [list(map(int,input().split())) for _ in range(m)]
ab = [[] for _ in range(n)] 
for i in range(n):
  ab[AB[i][0]-1].append(AB[i][1]-1)
  ab[AB[i][1]-1].append(AB[i][0]-1)

ans = 0
for i in itertools.permutations(range(n), n):
  if i[0] == 0:
    que = i
    cnt = 1
    for k in range(n-1):
      if que[k+1] in ab[que[k]]:
        cnt += 1
    if cnt == n:
      ans += 1

print(ans)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10**6)
n,m = map(int,(input().split()))

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

ans = [0]

def dfs(v):
    if all(flg):
        ans[0] +=1
        return 0
    
    for i in graph[v]:
        flg[v] = 1
        if flg[i] == 0:
            flg[i] = 1
            dfs(i)
            flg[i] = 0
    
    return 0

dfs(0)
print(ans[0])

Submission status: Runtime Error

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

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

ans = [0]

def dfs(v):
    if all(flg):
        ans[0] +=1
        return 0
    
    for i in graph[v]:
        flg[v] = 1
        if flg[i] == 0:
            flg[i] = 1
            dfs(i)
            flg[i] = 0
    
    return 0

dfs(0)
print(ans[0])

Submission status: Runtime Error

Solution code:
#最初に置いておくもの
import copy
import sys
sys.setrecursionlimit(50000000) 

#入出力関係
N, M = map(int, input().split())
l = []

for i in range(N):
    l.append(list(map(lambda x: int(x)-1 , input().split())))

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

for i in range(M):
    lis[l[i][0]].append(l[i][1])
    lis[l[i][1]].append(l[i][0])

def dfs():
    re=0
    q1 =[[0]*N]
    q2=[0]
    while len(q1) != 0:
         
        visited=q1.pop()
        v=q2.pop()
        visited[v]=1
        if all(visited[c]==1 for c in range(N)):
            re += 1
        elif len(lis[v]) != 0:
            for i in lis[v]:
                if visited[i] == 0:
                    hoge=copy.deepcopy(visited)                    
                    q1.append(hoge)
                    q2.append(i)
    return re

print(dfs())

Submission status: Runtime Error

Solution code:
#最初に置いておくもの
import queue
import copy
import sys
from astropy.io.fits.convenience import append
sys.setrecursionlimit(50000000) 
input=sys.stdin.readline

#入出力関係
N, M = map(int, input().split())
l = []

for i in range(M):
    l.append(list(map(lambda x: int(x)-1 , input().split())))

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

for i in range(M):
    lis[l[i][0]].append(l[i][1])
    lis[l[i][1]].append(l[i][0])


def dfs():
    re=0
    q1 =[[0]*N]
    q2=[0]
    while len(q1) != 0:
         
        visited=q1.pop()
        v=q2.pop()
        visited[v]=1
        if all(visited[c]==1 for c in range(N)):
            re += 1
        elif len(lis[v]) != 0:
            for i in lis[v]:
                if visited[i] == 0:
                    hoge=copy.deepcopy(visited)                    
                    q1.append(hoge)
                    q2.append(i)
    return re

print(dfs())

Submission status: Runtime Error

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

input=sys.stdin.readline

n,m=map(int,input().split())
G=[[False]*n for _ in range(n)]
used=[False]*n

def dfs(now,depth):
    if used[now]:
        return 0
    if n==depth:
        return 1
    used[now]=True
    ans=0
    for i in range(n):
        if G[now][i]:
            ans+=dfs(i,depth+1)
    used[now]=False
    return ans

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

print(dfs(0,1))

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
edge=[n*[0]for _ 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
from itertools import permutations
ans=0
for i in permutations([j for j in range(1,n)],n-1):
	f=True
	t=[0]+i
	for j in range(1,n):
		if edge[t[j-1]][t[j]]==0:f=False
	if f:ans+=1
print(ans)

Submission status: Runtime Error

Solution code:
                from itertools import permutations

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

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

for i in permutations(range(n), n):
    if i[0] == 0:
        for j in range(n):
            if j == n - 1:
                ans += 1
                break
            if not path[i[j]][i[j+1]]:
                break
print(ans)