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:
                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 == 1:
                ans += 1
                break
            if not path[i[j]][i[j+1]]:
                break
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 not path[i[j]][i[j+1]]:
                break
            if j == n-1:
                ans += 1
                break
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)]
#ab=Input.split()
#d：隣接行列
print(ab)
print(type(ab))
d = [[] for i in range(n)]
for i in range(m):
    a = ab[i][0]
    b = ab[i][1]
    d[a-1].append(b-1)
    d[b-1].append(a-1)
    
#per：順列列挙
per= list(itertools.permutations(range(1,n)))
cnt=0
for i in range(len(per)):
    x = [0]+per[i]
    for j in range(n):
        #隣接していなければ終了
        if not x[j+1] in d[x[j]]:
            break
        cnt+=1
print(cnt)

Submission status: Runtime Error

Solution code:
import itertools

n,m=map(int, input().split()) 
ab=[list(map(int, input().split())) for _ in range(m)]
#ab=Input.split()
#d：隣接行列
print(ab)
print(type(ab))
d = [[] for i in range(n)]
for i in range(m):
    a = ab[i][0]
    b = ab[i][1]
    d[a-1].append(b-1)
    d[b-1].append(a-1)
    
#per：順列列挙
per= list(itertools.permutations(range(1,n)))
cnt=0
for i in range(len(graph)):
    x = [0]+per[i]
    for j in range(n):
        #隣接していなければ終了
        if not x[j+1] in d[x[j]]:
            break
        cnt+=1
print(cnt)

Submission status: Runtime Error

Solution code:
import itertools

n,m=map(int, input().split()) 
ab=[list(map(int, input().split())) for _ in range(m)]
#ab=Input.split()
#d：隣接行列
print(ab)
print(type(ab))
d = [[] for i in range(n)]
for i in range(m):
    a = ab[i][0]
    b = ab[i][1]
    d[a-1].append(b-1)
    d[b-1].append(a-1)
    
#per：順列列挙
per= list(itertools.permutations(range(1,n)))
cnt=0
for i in range(len(graph)):
    x = [0]+graph[i]
    for j in range(n):
        #隣接していなければ終了
        if not x[j+1] in d[x[j]]:
            break
        cnt+=1
print(cnt)

Submission status: Runtime Error

Solution code:
n,m=map(int, input().split()) 
ab=[list(map(int, input().split())) for _ in range(m)]
#ab=Input.split()
#d：隣接行列
d = [[] for i in range(n)]
for i in range(m):
    a = ab[i][0]
    b = ab[i][1]
    d[a-1].append(b-1)
    d[b-1].append(a-1)
    
#per：順列列挙
per= list(itertools.permutations(range(1,n)))
cnt=0
for i in range(len(graph)):
    x = [0]+graph[i]
    for j in range(n):
        #隣接していなければ終了
        if not x[j+1] in d[x[j]]:
            break
        cnt+=1
print(cnt)

Submission status: Runtime Error

Solution code:
N,M = map(int, input().split())
L = [list(map(int,input().split())) for _ in range(M)]
graph = [[False] * (N + 1) for _ in range(N + 1)]
#%%

for i in L:
    graph[i[0]][i[1]] = True
    graph[i[1]][i[0]] = True

graph[0][1] = True
graph[1][0] = True
#%%
ans = 0
for i in permutations(range(1, N + 1)):
    if i[0] != 1:
        continue
    for j in range(1, N):
        if not graph[i[j - 1]][i[j]]:
            break
    else:
       ans += 1 

print(ans)

Submission status: Runtime Error

Solution code:
import itertools
import sys
N,M=map(int,input().split())
dic={}
for _ in range(N):
    a,b=map(int,input().split())
    if(a in dic.keys()):
        if((b in dic[a])==False):
            dic[a].append(b)
    else:
        dic[a]=[b]
    if(b in dic.keys()):
        if((a in dic.values())==False):
            dic[b].append(a)
    else:
        dic[b]=[a]

if(M==0):
    print(0)
    sys.exit()

node=[i for i in range(N)]
ans=0
strokes=itertools.permutations(node,M)

def judge(A,B):
    values=dic[A]
    if(B in values):
        return True
    else:
        return False

for stroke in strokes:
    stroke=list(stroke)
    if(stroke[0]==0):
        pre=stroke.pop(0) + 1
        for s in stroke:
            if(judge(pre,s+1)==False):
                break
            pre=s+1
        else:
            ans+=1
    
print(ans)

Submission status: Runtime Error

Solution code:
import itertools
import sys
N,M=map(int,input().split())
dic={}
for _ in range(N):
    a,b=map(int,input().split())
    if(a in dic.keys()):
        dic[a].append(b)
    else:
        dic[a]=[b]
    if(b in dic.keys()):
        dic[b].append(a)
    else:
        dic[b]=[a]


if(M==0):
    print(0)
    sys.exit()
    
node=[i for i in range(N)]
ans=0
strokes=itertools.permutations(node,M)

def judge(A,B):
    values=dic[A]
    if(B in values):
        return True
    else:
        return False

for stroke in strokes:
    stroke=list(stroke)
    if(stroke[0]==0):
        pre=stroke.pop(0) + 1
        for s in stroke:
            if(judge(pre,s+1)==False):
                break
            pre=s+1
        else:
            ans+=1
    
print(ans)

Submission status: Runtime Error

Solution code:
import itertools
N,M=map(int,input().split())
dic={}
for _ in range(N):
    a,b=map(int,input().split())
    if(a in dic.keys()):
        dic[a].append(b)
    else:
        dic[a]=[b]
    if(b in dic.keys()):
        dic[b].append(a)
    else:
        dic[b]=[a]
        
node=[i for i in range(N)]
ans=0
strokes=itertools.permutations(node,M)

def judge(A,B):
    values=dic[A]
    if(B in values):
        return True
    else:
        return False

for stroke in strokes:
    stroke=list(stroke)
    if(stroke[0]==0):
        pre=stroke.pop(0) + 1
        for s in stroke:
            if(judge(pre,s+1)==False):
                break
            pre=s+1
        else:
            ans+=1
    
print(ans)

Submission status: Runtime Error

Solution code:
from collections import defaultdict
# dfs, check path len, count paths                                                                                                                           
# test = 2                                                                                                                                                   
n, m = map(int, input().split())
edges = [map(int, input().split()) for i in range(n)]
graph = defaultdict(list)
for k,v in edges:
    graph[k].append(v)
    graph[v].append(k)

cnt = 0
# dfs                                                                                                                                                        
def dfs(node, visited):
    global cnt
    if node in visited:
        return None
    elif len(visited) + 1 == n:
        cnt += 1
        return None
    else:
        for v in graph[node]:
            dfs(v, visited+[node])
dfs(1, [])
print(cnt)

Submission status: Runtime Error

Solution code:
Not found

Submission status: Runtime Error

Solution code:
import math
import itertools


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

    result = 0
    for L in itertools.permutations(list(range(M))):
        remain = list(range(1, N+1))
        next = 1
        for j in range(len(L)):
            if next == P[L[j]][0]:
                remain.remove(next)
                next = P[L[j]][1]
            elif next == P[L[j]][1]:
                remain.remove(next)
                next = P[L[j]][0]
            else:
                break
            if len(remain) == 0:
                result += 1
                break
    print(result)


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
import math
import itertools
N, M = map(int, input().split())
P = [list(map(int, input().split())) for i in range(M)]

result = 0
for L in itertools.permutations(list(range(M))):
    remain = list(range(1, N+1))
    next = 1
    for j in range(len(L)):
        if next == P[L[j]][0]:
            remain.remove(next)
            next = P[L[j]][1]
        elif next == P[L[j]][1]:
            remain.remove(next)
            next = P[L[j]][0]
        else:
            break
        if len(remain) == 0:
            result += 1
            break
print(result)

Submission status: Runtime Error

Solution code:
import math
import copy
from copy import deepcopy
import sys
import fractions
# import numpy as np
from functools import reduce
# import statistics
import decimal
import heapq
import collections
import itertools
from operator import mul

sys.setrecursionlimit(100001)


# input = sys.stdin.readline
# sys.setrecursionlimit(10**6)

# ===FUNCTION===

def getInputInt():
    inputNum = int(input())
    return inputNum


def getInputListInt():
    outputData = []
    inputData = input().split()
    outputData = [int(n) for n in inputData]

    return outputData


def getSomeInputInt(n):
    outputDataList = []
    for i in range(n):
        inputData = int(input())
        outputDataList.append(inputData)

    return outputDataList


def getSomeInputListInt(n):
    inputDataList = []
    outputDataList = []
    for i in range(n):
        inputData = input().split()
        inputDataList = [int(n) - 1 for n in inputData]
        outputDataList.append(inputDataList)

    return outputDataList


# ===CODE===

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

d = getSomeInputListInt(n)

path = []
for p in itertools.permutations(range(1, n), n-1):
    tmp = (0,) + p
    path.append(tmp)


def pathsearch(a, b):
    flga = False
    for tmp_d in d:
        if a in tmp_d and b in tmp_d:
            flga = True
            break

    return flga


ans = 0
for p in path:
    flg = True
    for i in range(1, n, 1):
        tmp = pathsearch(p[i - 1], p[i])
        if not tmp:
            flg = False
            break

    if flg:
        ans += 1

print(ans)

Submission status: Runtime Error

Solution code:
import math
import copy
from copy import deepcopy
import sys
import fractions
# import numpy as np
from functools import reduce
# import statistics
import decimal
import heapq
import collections
import itertools
from operator import mul

sys.setrecursionlimit(100001)


# input = sys.stdin.readline
# sys.setrecursionlimit(10**6)

# ===FUNCTION===

def getInputInt():
    inputNum = int(input())
    return inputNum


def getInputListInt():
    outputData = []
    inputData = input().split()
    outputData = [int(n) for n in inputData]

    return outputData


def getSomeInputInt(n):
    outputDataList = []
    for i in range(n):
        inputData = int(input())
        outputDataList.append(inputData)

    return outputDataList


def getSomeInputListInt(n):
    inputDataList = []
    outputDataList = []
    for i in range(n):
        inputData = input().split()
        inputDataList = [int(n) - 1 for n in inputData]
        outputDataList.append(inputDataList)

    return outputDataList


# ===CODE===

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

d = getSomeInputListInt(n)

path = []
for p in itertools.permutations(range(1, n), n-1):
    tmp = (0,) + p
    path.append(tmp)


def pathsearch(a, b):
    flg = False
    for tmp_d in d:
        if a in tmp_d and b in tmp_d:
            flg = True
            break

    return flg


ans = 0
for p in path:
    flg = True
    for i in range(1, n, 1):
        tmp = pathsearch(p[i - 1], p[i])
        if not tmp:
            flg = False
            break

    if flg:
        ans += 1

print(ans)

Submission status: Runtime Error

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

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

ans = 0


def dfs(pos, cnt, his):
    global ans
    his[pos] = 1
    if cnt == n:
        if sum(his) == n:
            ans += 1
        return

    for next in data[pos]:
        dfs(next, cnt+1, his[:])
    return


dfs(0, 1, [0]*n)
print(ans)

Submission status: Runtime Error

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

n, m = list(map(int, input().split()))
data = [[] for _ in range(n)]
done = [False for _ in range(n)]
for i in range(n):
    a, b = map(int, input().split())
    data[a-1].append(b-1)
    data[b-1].append(a-1)

ans = 0


def dfs(pos, cnt, his):
    global ans
    his[pos] = 1
    if cnt == n:
        if sum(his) == n:
            ans += 1
        return

    for next in data[pos]:
        dfs(next, cnt+1, his[:])


dfs(0, 1, [0]*n)
print(ans)

Submission status: Runtime Error

Solution code:
n, m = list(map(int, input().split()))
data = [[] for _ in range(n)]
done = [False for _ in range(n)]
for i in range(n):
    a, b = map(int, input().split())
    data[a-1].append(b-1)

ans = 0


def dfs(pos, cnt):
    global ans
    done[pos] = True
    if cnt >= n-1:
        ans += 1
    for next in data[pos]:
        if not done[next]:
            dfs(next, cnt+1)


dfs(0, 0)
print(ans+1)

Submission status: Runtime Error

Solution code:
n, m = list(map(int, input().split()))
data = [[] for _ in range(n)]
done = [False for _ in range(n)]
for i in range(n):
    a, b = map(int, input().split())
    data[a-1].append(b-1)


def dfs(pos, cnt):
    done[pos] = True
    if cnt >= n-1:
        return 1
    ans = 0
    for next in data[pos]:
        if not done[next]:
            ans += dfs(next, cnt+1)
    return ans


ans = dfs(0, 0)
print(ans+1)

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
A=[["."]*n for i in range(n)]
B=[["."]*m for i in range(m)]
for i in range(n):
  A[i]=list(input())
for i in range(m):
  B[i]=list(input())
for i in range(n-m+1):
  for j in range(n-m+1):
    a=0
    for x in range(m):
      for y in range(m):
        if A[i+x][j+y]!=B[x][y]:
          a=1
          break
    if a==0:
      print("Yes")
      exit()
print("No")

Submission status: Runtime Error

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

def onestrokepath(start,visited=[]):
    flag=0
    count=0
    for next in hen[start]:
        if not next in visited:
            flag=1
            count+=onestrokepath(next,visited+[next])
    if flag==0:
        check=[i for i in range(0,N)]
        visited.sort()
        if check==visited:
            return 1
        else:
            return 0
    return count

print(onestrokepath(0,[0]))

Submission status: Runtime Error

Solution code:
def bit_DP(N.Adj):
    dp=[[0]*N for i in range(1<<N)]
    dp[1][0]=1
    for S in range(1<<N):
        for v in range(N):
            if (S&(1<<v))==0:
                continue
            sub=S^(1<<v)
            
            for u in range(N):
                if (sub&(1<<u)) and (Adj[u][v]):
                    dp[S][v]+=dp[sub][u]
    ans=sum(dp[(1<<N)-1][u] for u in range(1,N))
    return ans
def main():
    N,M=map(int,input().split())
    Adj=[[0]*N for i in range(N)]
    for _ in range(M):
        a,b=map(int,input().split())
        Adj[a-1][b-1]=1
        Adj[b-1][a-1]=1
    ans=bit_dp(N,Adj)
    print(ans)
if __name__=='__main__':
    main()

Submission status: Runtime Error

Solution code:
# https://img.atcoder.jp/abc054/editorial.pdf

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

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

def dfs(v, visited):
  all_visited = True
  for i in range(N):
    if not visited[i]:
      all_visited = False
      
  if all_visited:
    return 1
  
  ret = 0
  for i in range(N):
    if not graph[v][i]: continue
    if visited[i]: continue
    
    visited[i] = True
    ret += dfs(i, visited)
    visited[i] = False
  
  return ret

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

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
l=[list(map(int,input().split())) for _ in range(m)]
l.sort(key=lambda l:(l[0]))
c=0
used=[]
def find_num(itr,target):
    for j in range(itr, m):
        if target in l[j]:
            next_target=[k for k in l[j] if k!=target][0]
            used.append(next_target)
            if len(used) == n:
                return True
            if find_num(j,next_target):
                return True
            else:
                return False
    return False

for i in range(m):
    used=[]
    if 1 in l[i]:
        used.append(1)
        next_target = [k for k in l[i] if k != 1][0]
        used.append(next_target)
        rtn=find_num(i, next_target)
        if rtn:
            c+=1
print(c)

Submission status: Runtime Error

Solution code:
import itertools

def resolve():
    n, m = map(int, input().split())
    S = [[0] * n for i in range(n)]

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

    ans = 0
    for p in itertools.permutations(range(n)):
        if p[0] != 0:
            break
        tmp = 1
        for i, v in enumerate(n-1):
            tmp *= S[p[i]][p[i + 1]]
        ans += tmp

    print(ans)

if __name__ == '__main__':
    resolve()

Submission status: Runtime Error

Solution code:
import itertools


def resolve():
    n, m = map(int, input().split())
    S = [[0] * m for i in range(n)]

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

    ans = 0
    for p in itertools.permutations(range(n)):
        if p[0] != 0:
            break
        tmp = 1
        for i in range(n-1):
            tmp *= S[p[i]][p[i + 1]]
        if tmp == 0:
            break
        ans += tmp

    print(ans)

if __name__ == '__main__':
    resolve()

Submission status: Runtime Error

Solution code:
import itertools


def resolve():
    n, m = map(int, input().split())
    S = [[0] * m for i in range(m)]

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

    ans = 0
    for p in itertools.permutations(range(n)):
        if p == (0, 2, 3, 4, 5, 6, 1):
            pass
        if p[0] != 0:
            break
        tmp = 1
        for i in range(n-1):
            tmp *= S[p[i]][p[i + 1]]
        if tmp == 0:
            break
        ans += tmp

    print(ans)

if __name__ == '__main__':
    resolve()

Submission status: Runtime Error

Solution code:
import itertools


def resolve():
    n, m = map(int, input().split())
    S = [[0] * m for i in range(m)]
    MOD = (10 ** 9) + 7

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

    ans = 0
    for p in itertools.permutations(range(m)):
        if p == (0, 2, 3, 4, 5, 6, 1):
            pass
        if p[0] != 0:
            break;
        tmp = 1
        for i, v in enumerate(p):
            if i + 1 < m:
                tmp *= S[v][p[i + 1]]
            if tmp == 0:
                break;
        ans += tmp

    print(ans % MOD)


if __name__ == '__main__':
    resolve()

Submission status: Runtime Error

Solution code:
import itertools

def resolve():
    n, m = map(int, input().split())
    S = [[0]*m for i in range(m)]

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

    ans = 0
    for p in itertools.permutations(range(n)):
        if p[0] != 0:
            break;
        tmp = 1
        for i, v in enumerate(p):
            if i > m:
                tmp *= S[[i+1]][p[i+1]]
        ans += tmp

    print(ans)

if __name__ == '__main__':
    resolve()

Submission status: Runtime Error

Solution code:
import itertools

def resolve():
    n, m = map(int, input().split())
    S = [[0]*m for i in range(m)]
    MOD = (10 ** 9) + 7

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

    ans = 0
    for p in itertools.permutations(range(0, m)):
        if p == (0,2,3,4,5,6,1):
            pass
        if p[0] != 0:
            break;
        tmp = 1
        for i, v in enumerate(p):
            if i + 1 < m:
                tmp *= S[v][p[i+1]]
            if tmp == 0:
                break;
        ans += tmp

    print(ans % MOD)

if __name__ == '__main__':
    resolve()

Submission status: Runtime Error

Solution code:
import itertools

def resolve():
    n, m = map(int, input().split())
    S = [[0]*m for i in range(m)]
    MOD = (10 ** 9) + 7

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

    ans = 0
    for p in itertools.permutations(range(0, m)):
        if p == (0,2,3,4,5,6,1):
            pass
        if p[0] != 0:
            break;
        tmp = 1
        for i, v in enumerate(p):
            if i + 1 < m:
                tmp *= S[v][p[i+1]]
        ans += tmp

    print(ans % MOD)

if __name__ == '__main__':
    resolve()

Submission status: Runtime Error

Solution code:
import itertools

def resolve():
    n, m = map(int, input().split())
    S = [[0]*m for i in range(m)]
    MOD = (10 ** 9) + 7

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

    ans = 0
    for p in itertools.permutations(range(0, m)):
        if p == (0,2,3,4,5,6,1):
            pass
        if p[0] != 0:
            break;
        tmp = 1
        for i, v in enumerate(p):
            if i + 1 < m:
                tmp *= S[v][p[i+1]]
        ans += tmp

    print(ans % MOD)
    
if __name__ == '__main__':
    resolve()

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())
G = [[] for _ 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)

flag = (1<<n)-1

def dfs(v=0, visited=1):
    if visited == flag:
        return 1

    cnt = 0
    for to in G[v]:
        if visited & 1<<to:
            continue
        cnt += dfs(to, visited^(1<<to))
    return cnt

print(dfs())

Submission status: Runtime Error

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

#無向行列
path_matrix = [[False]*N for _ in range(M)]

for _ in range(M):
  line = map(int, input().split())
  paths = [x-1 for x in line]
  path_matrix[paths[0]][paths[1]] = True
  path_matrix[paths[1]][paths[0]] = True
  
visited = [False]*N

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

Submission status: Runtime Error

Solution code:
from collections import deque

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

G=[[] for i in range(M+1)]

for i in range(M):
    n,m=map(int,input().split())
    G[n].append(m)
    G[m].append(n)

visited=[0]*(N+1)
ans=0
def dfs(now, num_visited=0):
    global ans
    visited[now] = 1
    num_visited+=1
    
    if num_visited==N:
        ans+=1
    
    for i in G[now]:
        next=i
        if visited[next]!=1:dfs(next,num_visited)
        
    visited[now] = 0

dfs(1)
print(ans)

Submission status: Runtime Error

Solution code:
N,M=map(int,input().split())
import copy
a=[0]*M
b=[0]*M
for i in range(M):
    a[i],b[i]=map(int,input().split())
D=[[1]]
def route(D):
    E=[]
    D1=copy.deepcopy(D)
    for j in range(len(D)):
        x=D[j][-1]
        for i in range(M):

            if a[i]==x:
                if not b[i] in D1[j]:
                    D=copy.deepcopy(D1)
                    D[j].append(b[i])
                    E.append(D[j])
            elif b[i]==x:
                if not a[i] in D1[j]:
                    D=copy.deepcopy(D1)
                    D[j].append(a[i])
                    E.append(D[j])
    return E
for i in range(N-1):
    D=copy.deepcopy(route(D))

if len(D[0])!=N:
    print(0)
    exit()
print(len(D))

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())
graph = {i: [] for i in range(1, m + 1)}
for _ in range(m):
    u, v = map(int, input().split())
    graph[u].append(v)
    graph[v].append(u)

def dfs(i):
    ret = 0
    if all(han):
        return 1
    for j in range(1, n + 1):
        if han[j] == False and j in graph[i]:
            han[j] = True
            ret += dfs(j)
            han[j] = False
    return ret

han = [False] * (n + 1)
han[0] = True
han[1] = True
ans = dfs(1)
    
print(ans)

Submission status: Runtime Error

Solution code:
[n,m] = [int(x) for x in input().split()]
data = [[int(x) for x in input().split()] for _ in range(m)]

total = 0
for x in itertools.permutations(range(2,n+1)):
    
    route = [1,]+list(x)
    
    for x in range(len(route)-1):
        flg = False
        
        for y in data:
            if {route[x],route[x+1]} == set(y):
                flg = True
                break
                
        if flg == False:
            break
            
    else:
        total += 1
        
print(total)

Submission status: Runtime Error

Solution code:
import itertools
n,m = map(int,input().split())
M = [[0] * n for i in range(m)]

for i in range(m):
  a,b = map(int,input().split())
  M[a-1][b-1] = 1
couse = list(itertools.permutations(range(n)))
result = 0
#M = np.array(M)
for c in couse:
  con = 0
  if(c[0] == 0):
    for i in range(len(c)-1):
      if(M[c[i]][c[i+1]] == 1 or M[c[i+1]][c[i]] == 1):
        con += 1
        #print(c[i],c[i+1])
    if (len(c)-1 == con):
      result += 1
print(result)

Submission status: Runtime Error

Solution code:
import itertools
import numpy as np
n,m = map(int,input().split())
M = [[0] * n for i in range(m)]

for i in range(m):
  a,b = map(int,input().split())
  M[a-1][b-1] = 1
couse = list(itertools.permutations(range(n)))
result = 0
M = np.array(M)
for c in couse:
  con = 0
  if(c[0] == 0):
    for i in range(len(c)-1):
      if(M[c[i]][c[i+1]] == 1 or M[c[i+1]][c[i]] == 1):
        con += 1
        #print(c[i],c[i+1])
    if (len(c)-1 == con):
      result += 1
print(result)

Submission status: Runtime Error

Solution code:
import itertools
import numpy as np
n,m = map(int,input().split())
M = [[0] * n for i in range(m)]

for i in range(m):
  a,b = map(int,input().split())
  M[a-1][b-1] = 1
couse = list(itertools.permutations(range(n)))
result = 0
M = np.array(M)
for c in couse:
  con = 0
  if(c[0] == 0):
    for i in range(len(c)-1):
      if(M[c[i]][c[i+1]] == 1 or M[c[i+1]][c[i]] == 1):
        con += 1
        print(c[i],c[i+1])
    if (len(c)-1 == con):
      result += 1
print(result)

Submission status: Runtime Error

Solution code:
import itertools
for i in range(m):
  a,b=map(int,input().split())
  link[a-1].append(b-1)
  link[b-1].append(a-1)
s=list(range(1,n))
res=0
for perm in list(itertools.permutations(s)):
  last=0
  ok=True
  for i in range(n-1):
    if perm[i] not in link[last]:
      ok=False
      break
    else:
      last=perm[i]
  if ok==True:
    res=res+1
print(res)

Submission status: Runtime Error

Solution code:
for i in range(m):
  a,b=map(int,input().split())
  link[a-1].append(b-1)
  link[b-1].append(a-1)
s=list(range(1,n))
res=0
for perm in list(itertools.permutations(s)):
  last=0
  ok=True
  for i in range(n-1):
    if perm[i] not in link[last]:
      ok=False
      break
    else:
      last=perm[i]
  if ok==True:
    res=res+1
print(res)

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())
l = [list(map(int, input().split())) for i in range(m)]
r = [[] for i in range(n + 1)]
ans = 0
for i in range(m):
    r[l[i][0]].append(l[i][1])
    r[l[i][1]].append(l[i][0])
p = []
for i in range(n):
    p.append(i + 1)
p = list(itertools.permutations(p))
for i in range(len(p)):
    check = True
    t = list(p[i])
    if t[0] != 1:
        check = False
    for j in range(len(t)-1):
        if not t[j + 1] in r[t[j]]:
            check = False
    if check:
        ans += 1
print(ans)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10**7) #再帰関数の呼び出し制限
N, M = map(int, input().split())
A = [[0]* N for _ in range(N)]
for i in range(M):
    a, b = map(int, input().split())
    A[a-1][b] = 1
    A[b-1][a] = 1
visited=[0]*N
ans = 0
def DFS(x):
    if not 0 in visited:
        return 1
    for i in range(N):
        if not 1 in A[x][i]:
            return
        if visited[x] == 1:
            return
        visited[x] = 1
        ans += DFS(i)
    return ans
print(DFS(0))

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10**7) #再帰関数の呼び出し制限
N, M = map(int, input().split())
A = [0]*(N+1)
for i in range(M):
    a, b = map(int, input().split())
    A[a-1][b] = 1
    A[b-1][a] = 1
visited=[0]*N
ans = 0
def DFS(x):
    if not 0 in visited:
        return 1
    for i in range(N):
        if not 1 in A[x][i]:
            return
        if visited[x] == 1:
            return
        visited[x] = 1
        ans += DFS(i)
    return ans
print(DFS(0))

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10**7) #再帰関数の呼び出し制限
N, M = map(int, input().split())
A = [0]*(N+1)
for i in range(M):
    a, b = map(int, input().split())
    A[a].append([b])
    A[b].append([a])
visited=[1]+[0]*N
ans = 0
def DFS(x):
    if visited[x] == 1:
        return
    if sum(visited) == N:
        ans += 1
    visited[x] = 1
    for i in range(N):
        DFS(A[x][i])
    return ans
print(DFS(1))