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

G = {k: set() for k in range(N+1)}
for _ in range(N):
    a, b = map(int, input().split())
    # 無向グラフ
    G[a].add(b)
    G[b].add(a)

ans = 0
for p in itertools.permutations(range(2, N+1)):
    c = 1
    for n in p:
        if n not in G[c]:
            break
        c = n
    else:
        ans += 1

print(ans)

Submission status: Runtime Error

Solution code:
def resolve():

    N,M = map(int,input().split())
    ab =[map(int,input().split()) for _ in range(N)]
    branch = [[] for _ in range(N)]
    for a,b in ab:
        branch[a-1].append(b-1)
        branch[b-1].append(a-1)
    
    bit = 0
    count = 0
    def walk(p):
        nonlocal bit,N
        bit |= (1 << p)
        if bit == 2 ** N - 1:
            nonlocal count
            count += 1
        for n in branch[p]:
            if not(bit & (1 << n)):
                walk(n)
        bit &= ~(1 << p)

    walk(0)
    print(count)
resolve()

Submission status: Runtime Error

Solution code:
#C One-stroke Path
import itertools
import numpy as np

n,m=map(int,input().split( ))
adj_matrix=np.zeros((n,n))

for i in range(m):
    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)): #頂点の全ての並べ方(permutation)
    if each[0] != 0:#始点が1ではないものを除外した。breakすることで次のeachに変わる。
        break
    factor=1
    for i in range(n-1):　#全経路があれば全て１になるのでfactor=1となりcntに足される。
        factor *=adj_matrix[each[i],each[i+1]]
    cnt += factor
    
print(int(cnt))

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
uselist=[]
for _ in range(m):
    ad=list(map(int,input().split()))
    uselist.append(ad)
cnt=0
for i in itertools.permutations(range(1,n+1)):
    if i[0]==1:
        flag=True
        for j in range(n-1):
            if [i[j],i[j+1]]  not in uselist and [i[j+1], i[j]] not in uselist:
                flag =False
                break
            else:
                continue
        if flag==True:
            cnt+=1
        else:
            continue
        
print(cnt)

Submission status: Runtime Error

Solution code:
import itertools
n,m=map(int,input().split())
edge=[[]for i in range(m+1)]

for i in range(m):
    a,b=map(int,input().split())
    edge[a].append(b)
    edge[b].append(a)
    
ans=0
for i in itertools.permutations(range(1,n+1)):
    if i[0]!=1:
        continue
    for j in range(n-1):
        if i[j+1] not in edge[i[j]]:
            break
    else:
        ans+=1
print(ans)

Submission status: Runtime Error

Solution code:

import sys
input = sys.stdin.readline
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
# A = [ int(input()) for _ in range(N) ]
##############################

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

A = [ [0 for _ in range(N)] for _ in range(N) ]
visited = [False] * N

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

#print(A)

def dfs(node, count):
    if all(visited):
        return 1

    count = 0
    for i in range(M):
        if A[node][i] == 0:
            continue
        if visited[i]:
            continue

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

    return count


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

Submission status: Runtime Error

Solution code:

import sys
input = sys.stdin.readline
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
# A = [ int(input()) for _ in range(N) ]
##############################

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

A = [ [0 for _ in range(N)] for _ in range(N) ]
visited = [False] * N

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

#print(A)

def dfs(node, count):
    if all(visited):
        return count+1

    for i in range(M):
        if A[node][i] == 0:
            continue
        if visited[i]:
            continue

        visited[i] = True
        count = dfs(i, count)
        visited[i] = False

    return count


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

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
from operator import itemgetter
import itertools

def main():
    n, m = map(int, input().strip().split())
    lis = [[] for _ in range(n)]
    for _ in range(m):
        a, b = list(map(lambda x: x-1, map(int, input().strip().split())))
        lis[a].append(b)
        lis[b].append(a)
    ans = 0
    for path in itertools.permutations(range(8), 8):
        if all(path[i+1] in lis[path[i]] for i in range(n-1)):
            ans += 1
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
edgelist = []
for i in range(N):
    edgelist.append(set(map(int, input().split())))

s = [1]
count = 0
L = [[i for i in edgelist if (len(i&set([1]))!=0)]]
while s != []:
    if len(s) == M:
        count = count + 1
        L.pop()
        s.pop()
    elif L[-1] == []:
        L.pop()
        s.pop()
    else:
        p = L[-1].pop()
        r = list(p - set([s[-1]]))
        L.append([i for i in edgelist if (len(i&set(r))!=0)*(len(i&set(s))==0)])
        s.append(r[0])
print(count)

Submission status: Runtime Error

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

import itertools

M = [[0] * (n+1) for i in range(n+1)]
for i in range(m):
    M[A[i][0]][A[i][1]] = 1
    M[A[i][1]][A[i][0]] = 1

B = list(itertools.permutations(range(2, n+1)))

#print(B)

ans = 0
for i in range(len(B)):
    pt = 0
    if M[1][B[i][0]] == 1:
        pt += 1
    else:
        continue

    for j in range(len(B[i])-1):
        if M[B[i][j]][B[i][j+1]] == 1:
            pt += 1
    # print(B[i],pt)
    if pt == n-1:
        ans += 1
print(ans)

Submission status: Runtime Error

Solution code:
import itertools

N,M = map(int,input().split())
Data = []
for _ in range(M+1):
    Data.append([0]*(M+1))
for _ in range(M):
    a,b = map(int,input().split())
    Data[a][b] = 1
    Data[b][a] = 1

ans = 0
for r in itertools.permutations(range(2,N+1)):
    Rlist = list(r)
    a = 1
    b = Rlist[0]
    if Data[a][b] == 0:
        continue
    else:
        flag = True 
        for i in range(len(Rlist)-1):
            a = Rlist[i]
            b = Rlist[i+1]
            if Data[a][b] == 0:
                flag = False
                break
        if flag:
            ans += 1

print(ans)

Submission status: Runtime Error

Solution code:
import itertools

n,m = map(int, input().split())
path = [[False]*n for _ in range(n)]
for i in range(n):
    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 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 sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

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

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

def dfs(n, index, v, ans):
    vLst[index] = 1
    if n == N - 1:
        ans += 1
        return ans
    for i in tLst[index]:
        if v == i:
            continue
        elif vLst[i] == 1:
            continue
        ans = dfs(n + 1, i, index, ans)
        vLst[i] = 0
    return ans
print(dfs(0, 0, 0, 0))

Submission status: Runtime Error

Solution code:
import copy

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

graph = [[-1 for _ in range(N)] for __ in range(N)]
cnt = 0


def solve(current: int, traversed: set):
    global cnt
    traversed = copy.copy(traversed)

    # fail
    if current in traversed:
        return
    else:
        traversed.add(current)

    # success
    if len(traversed) == N:
        cnt += 1
        return

    # traverse
    for node_ix in range(N):
        if graph[current][node_ix] == 1:
            solve(node_ix, traversed)

# Create adjcent graph

for _ in range(N):
    a, b = list(map(lambda x: int(x)-1, input().split()))
    graph[a][b] = 1
    graph[b][a] = 1

solve(0, set())
print(cnt)

Submission status: Runtime Error

Solution code:
# import sys
# sys.setrecursionlimit(10**9)

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

Map = [[] for _ in range(M)]
reached = [False]*N

for _ in range(M):
    aa, bb = map(int, input().split())
    Map[aa-1].append(bb-1)
    Map[bb-1].append(aa-1)

cnt = 0

def DFS(x):
    global cnt
    global reached

    reached[x] = True

    if all(reached):
        cnt += 1
        reached[x] = False

        return

    for i in Map[x]:
        if reached[i]:
            continue

        else:
            DFS(i)

    reached[x] = False


DFS(0)
print(cnt)

Submission status: Runtime Error

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

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

Map = [[] for _ in range(M)]
reached = [False]*N

for _ in range(M):
    aa, bb = map(int, input().split())
    Map[aa-1].append(bb-1)
    Map[bb-1].append(aa-1)

cnt = 0

def DFS(x):
    global cnt
    global reached

    reached[x] = True

    if all(reached):
        cnt += 1
        reached[x] = False

        return

    for i in Map[x]:
        if reached[i]:
            continue

        else:
            DFS(i)

    reached[x] = False


DFS(0)
print(cnt)

Submission status: Runtime Error

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

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

Map = [[] for _ in range(M)]
reached = [False]*N

for _ in range(M):
    aa, bb = map(int, input().split())
    Map[aa-1].append(bb-1)
    Map[bb-1].append(aa-1)

cnt = 0

def DFS(x):
    global cnt
    reached[x] = True

    if all(reached):
        cnt += 1

    for i in range(N):
        if reached[i]:
            continue

        if i in Map[x]:
            DFS(i)

    reached[x] = False
    return

DFS(0)
print(cnt)

Submission status: Runtime Error

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

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

Map = [[] for _ in range(M)]
reached = [False]*N

for _ in range(M):
    aa, bb = map(int, input().split())
    Map[aa-1].append(bb-1)
    Map[bb-1].append(aa-1)

cnt = 0

def DFS(x):
    global cnt
    reached[x] = True

    if all(reached):
        cnt += 1

    for i in range(N):
        if reached[i]:
            continue

        if i in Map[x]:
            DFS(i)

    reached[x] = False
    return

DFS(0)
print(cnt)

Submission status: Runtime Error

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

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

Map = [[] for _ in range(M)]
reached = [False]*N

for _ in range(M):
    aa, bb = map(int, input().split())
    Map[aa-1].append(bb-1)
    Map[bb-1].append(aa-1)

cnt = 0

def DFS(x, pre):
    global cnt
    reached[x] = True

    if all(reached):
        cnt += 1

    for i in range(N):
        if i==pre or reached[i]:
            continue

        if i in Map[x]:
            DFS(i, x)

    reached[x] = False

DFS(0,-1)
print(cnt)

Submission status: Runtime Error

Solution code:
N, M = [int(x) for x in input().split()]
P = [[False] * M for m in range(M)]
dict={}
for m in range(M):
  a, b = [int(x) for x in input().split()]
  P[a-1][b-1] = True
  P[b-1][a-1] = True

def dp(x, past):
  past[x] = True
  if (x, tuple(past)) in dict:
    return dict[(x, tuple(past))]
  if False not in past:
    return 1
  ret = 0
  for i,p in enumerate(P[x]):
    if not p or x == i or past[i]:
      continue
    else:
      ret += dp(i, past[:])
  dict[(x, tuple(past))] = ret
  return ret

if M < N - 1:
  print(0)
else:
  print(dp(0, [False] * N))

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(1000000)
N, M = [int(x) for x in input().split()]
P = [[False] * M for m in range(M)]
dict={}
for m in range(M):
  a, b = [int(x) for x in input().split()]
  P[a-1][b-1] = True
  P[b-1][a-1] = True

def dp(x, past):
  if (x, tuple(past)) in dict:
    return dict[(x, tuple(past))]
  past[x] = True
  if False not in past:
    return 1
  ret = 0
  for i,p in enumerate(P[x]):
    if not p or x == i or past[i]:
      continue
    else:
      ret += dp(i, past[:])
  dict[(x, tuple(past))] = ret
  return ret

print(dp(0, [False] * N))

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10000)
N, M = [int(x) for x in input().split()]
P = [[False] * M for m in range(M)]
dict={}
for m in range(M):
  a, b = [int(x) for x in input().split()]
  P[a-1][b-1] = True
  P[b-1][a-1] = True

def dp(x, past):
  if (x, tuple(past)) in dict:
    return dict[(x, tuple(past))]
  past[x] = True
  if False not in past:
    return 1
  ret = 0
  for i,p in enumerate(P[x]):
    if not p or x == i or past[i]:
      continue
    else:
      ret += dp(i, past[:])
  dict[(x, tuple(past))] = ret
  return ret

print(dp(0, [False] * N))

Submission status: Runtime Error

Solution code:
N, M = [int(x) for x in input().split()]
P = [[False] * M for m in range(M)]
dict={}
for m in range(M):
  a, b = [int(x) for x in input().split()]
  P[a-1][b-1] = True
  P[b-1][a-1] = True

def dp(x, past):
  if (x, tuple(past)) in dict:
    return dict[(x, tuple(past))]
  past[x] = True
  if False not in past:
    return 1
  ret = 0
  for i,p in enumerate(P[x]):
    if not p or x == i or past[i]:
      continue
    else:
      ret += dp(i, past[:])
  dict[(x, tuple(past))] = ret
  return ret

print(dp(0, [False] * N))

Submission status: Runtime Error

Solution code:
N, M = [int(x) for x in input().split()]
P = [[False] * M for m in range(M)]
for m in range(M):
  a, b = [int(x) for x in input().split()]
  P[a-1][b-1] = True
  P[b-1][a-1] = True

def dp(x, past):
  past[x] = True
  if False not in past:
    return 1
  ret = 0
  for i,p in enumerate(P[x]):
    if not p or x == i or past[i]:
      continue
    else:
      ret += dp(i, past[:])
  return ret

print(dp(0, [False] * N))

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(1000000)

N, M = map(int, input().split())
edge = [[] for _ in range(N + 1)]
ab = [list(map(int, input().split())) for _ in range(M)]
for i in range(M):
    a, b = ab[i][0], ab[i][1]
    edge[a].append(b)
    edge[b].append(a)


def f(now, v):
    v = v & (1 << now)
    for to in edge[now]:
        if v >> to == 0:
            f(to, v)
    if v == int('0b11111111', 0):
        ans += 1

ans = 0
f(1, 1)

print(ans)

Submission status: Runtime Error

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

def DFS(s):
    global visited
    #ret=1 if all(visited) else 0
    if all(visited):
        ret = 1
    else:
        ret = 0
    for e in edge[s]:
        #print("e",e)
        if visited[e] == True:
            continue
        visited[e] = True
        ret += DFS(e)
        visited[e] = False
    return ret

ans = 0
visited = [False] * n
visited[0] = True
ans += DFS(0)
print(ans)

Submission status: Runtime Error

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

def DFS(s):
    global visited
    #ret=1 if all(visited) else 0
    if all(visited):
        ret = 1
    else:
        ret = 0
    for e in edge[s]:
        #print("e",e)
        if visited[e] == True:
            continue
        visited[e] = True
        ret += DFS(e)
        visited[e] = False
    return ret

visited = [False] * n
visited[0] = True
print(DFS[0])

Submission status: Runtime Error

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

def DFS(s):
    global visited
    #ret=1 if all(visited) else 0
    if all(visited):
        ret = 1
    else:
        ret = 0
    for e in edge[s]:
        print("e",e)
        if visited[e] == True:
            continue
        visited[e] = True
        ret += DFS(e)
        visited[e] = False
    return ret

visited = [False] * n
visited[0] = True
print(DFS[0])

Submission status: Runtime Error

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

for _ in range(m):
    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 range(itertools.permutations(range(n))):
    if each[0] != 0:
        break
    flag = 1
    for i in range(n-1):
        flag *= adj_matrix[each[i]][each[i+1]]
    cnt += flag
print(cnt)

Submission status: Runtime Error

Solution code:

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

# N = 頂点の数(= 数字の数)
# M = 辺の数(= aの行数)

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

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

#print(graph)

# u は 0-index
def dfs(u):
    visited[u] = True
    if False in visited:
        pass
    else:
        return 1

    count = 0
    for i in range(N):
        if graph[u][i] == False: continue
        if visited[i]: continue

        visited[i] = True
        count += dfs(i)
        visited[i] = False

    return count

count = dfs(0)
print(count)

Submission status: Runtime Error

Solution code:

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

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

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

#print(graph)

# u は 0-index
def dfs(u):
    visited[u] = True
    if False in visited:
        pass
    else:
        return 1

    count = 0
    for i in range(N):
        if graph[u][i] == False: continue
        if visited[i]: continue

        visited[i] = True
        count += dfs(i)
        visited[i] = False

    return count

count = dfs(0)
print(count)

Submission status: Runtime Error

Solution code:

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

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

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

#print(graph)

# u は 0-index
def dfs(u):
    visited[u] = True
    if False in visited:
        pass
    else:
        return 1

    count = 0
    for i in range(M):
        if graph[u][i] == False: continue
        if visited[i]: continue

        visited[i] = True
        count += dfs(i)
        visited[i] = False

    return count

count = 0
count = dfs(0)
print(count)

Submission status: Runtime Error

Solution code:

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

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

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

#print(graph)

# u は 0-index
count = 0
def dfs(u, count):
    visited[u] = True
    if False in visited:
        pass
    else:
        count += 1

    for i in range(M):
        if graph[u][i] == False: continue
        if visited[i]: continue

        visited[i] = True
        count = dfs(i, count)
        visited[i] = False

    return count

count = dfs(0, count)
print(count)

Submission status: Runtime Error

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

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
   
N, M = LI()
mat = [[0] * N for _ in range(M)]
for _ in range(M):
    a, b = LI_()
    mat[a][b] = 1
    mat[b][a] = 1 
seen = [0 for _ in range(N)]
ans = 0

def dfs(i, count):
    global ans
    import pdb
    # pdb.set_trace()
    if count == N:
        return True

    for j, reachable in enumerate(mat[i]):
        if reachable and not seen[j]:
            seen[j] = 1
            if dfs(j, count + 1):
                ans += 1
            seen[j] = 0

    return False

def main():
    seen[0] = 1
    dfs(0, 1)
    print(ans)
main()

Submission status: Runtime Error

Solution code:
from collections import deque

N, M = list(map(int, input().split()))
G = [[] for _ in range(N)]
for _ in range(M):
  a, b = list(map(int, input().split()))
  G[a-1].append(b-1)
  G[b-1].append(a-1)
  
ans = 0
v = 0
s = 1
l = 1
q = deque()
q.append((v, s, l))

while q:
  v, s, l = q.popleft()
  if l == N:
    ans += 1
    continue
  for nv in G[v]:
    if s&(1<<n) == 0:
      q.append((nv, s|(1<<n), l+1))
print(ans)

Submission status: Runtime Error

Solution code:

N, M = list(map(int,input().split()))
graph = [dict() for i in range(N)]
for i in range(N):
	graph[i]["edge"] = []
for i in range(M):
	a, b = list(map(int, input().split()))
	graph[a - 1]["edge"].append(b - 1)
	graph[b - 1]["edge"].append(a - 1)

def pow(N):
	ans = 1
	for i in range(N):
		ans *= i + 1
	return  ans

total = 0
for i in range(pow(N - 1)):
	node = [a+1 for a in range(N - 1)]
	num = i
	zyun = [0]
	for j in range(N - 1, 0 , -1):
		mod = num % j
		num -= num % j
		num = num//j
		zyun.append(copy.deepcopy(node[mod]))
		del node[mod]
	judge = 1
	for loc in range(N - 1):
		if not zyun[loc + 1] in graph[zyun[loc]]["edge"]:
			judge = 0
	total += judge

print(total)

Submission status: Runtime Error

Solution code:
n,m = map(int,input().split())
l=[[*map(int,input().split())] for _ in range(m)]
i=[[] for _ in range(max(n,m))]
i[0]=[1]
c=1
for i_1 in i:
    for i_2 in i_1:
        a=[]
        for k in l:
            if i_2 in k:
                a.append(k)
            else: continue
        for b in a:
            if b[0]==i_2:
                i[c].append(b[1])
            else:
                i[c].append(b[0])
    for k in l[:]:
        if i_2 in k:
            l.remove(k)
    c+=1
print(len(i[n-2]))

Submission status: Runtime Error

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

i=[[] for _ in range(m)]
i[0]=[1]
c=1
for i_1 in i:
    for i_2 in i_1:
        a=[]
        for k in l:
            if i_2 in k:
                a.append(k)
            else: continue
        for b in a:
            if b[0]==i_2:
                i[c].append(b[1])
            else:
                i[c].append(b[0])
    for k in l[:]:
        if i_2 in k:
            l.remove(k)
    c+=1
print(len(i[n-2]))

Submission status: Runtime Error

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

i=[[] for _ in range(m)]
i[0]=[1]
c=1
for i_1 in i:
    for i_2 in i_1:
        a=[]
        for k in l:
            if i_2 in k:
                a.append(k)
            else: continue
        for b in a:
            if b[0]==i_2:
                i[c].append(b[1])
            else:
                i[c].append(b[0])
    for k in l[:]:
        if i_2 in k:
            l.remove(k)
    c+=1
print(len(i[m-2]))

Submission status: Runtime Error

Solution code:

Submission status: Runtime Error

Solution code:
def main():
    n, m = map(int, input().split())
    mat = [[0]*n for i in range(n)]
    l = [list(map(int, input().split())) for _ in range(m)]

    for i in range(n):
        mat[l[i][0]-1][l[i][1]-1] = 1
        mat[l[i][1]-1][l[i][0]-1] = 1

    
    ver = [i for i in range(n)]

    cnt = 0

    def dfc(now, moved):
        
        nonlocal cnt

        moved.sort()
        if moved == ver:
            cnt += 1
        
        for i in range(n):
            if (mat[now][i] == 0) or (i in moved):
                continue
            
            dfc(i, moved + [i])

    dfc(0, [0])
    print(cnt)
    
if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
def main():
 
    n, m = map(int, input().split())
    mat = [[0]*n for i in range(n)]
    l = [list(map(int, input().split())) for _ in range(m)]

    for i in range(n):
        mat[l[i][0]-1][l[i][1]-1] = 1
        mat[l[i][1]-1][l[i][0]-1] = 1

    
    ver = [i for i in range(n)]

    cnt = 0

    def dfc(now, moved):
        
        nonlocal cnt

        moved.sort()
        if moved == ver:
            cnt += 1
        
        for i in range(n):
            if (mat[now][i] == 0) or (i in moved):
                continue
            
            dfc(i, moved + [i])

    dfc(0, [0])
    print(cnt)
    
if __name__ == "__main__":
    main()
def main():

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

    ver = [i for i in range(n)]

    cnt = 0

    def dfc(now, moved):
        
        nonlocal cnt
     
        moved.sort()
        if moved == ver:
            cnt += 1

        for i in tree[now]:
            if i in moved:
                continue
            dfc(i, moved + [i])

    dfc(0, [0])
    print(cnt)
    
if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
n, m = map(int,input().split())
ab = [[0 for i in range(n)] for j in range(n)]
for i in range(m):
    ai,bi = map(int,input().split())
    ab[ai-1][bi-1] = 1
    ab[bi-1][ai-1] = 1

count = 0

def dfs(x,v):
    l = v.copy()
    l.append(x)
    if len(l)==n:
        global count
        count += 1
    for i in range(n):
        if ab[x][i] == 1 and not i in l:
            dfs(i,l)
    
dfs(0,[])
print(count)

Submission status: Runtime Error

Solution code:
N,M=map(int,input().split())
tbl=[[0]*(N+1) for _ in range(N+1)]
for i in range(M):
  a,b=map(int,input().split())
  tbl[a][b]=1
  tbl[b][a]=1            # グラフの行列を用いた表現
def dfs(s,visited):
  if len(visited)==N:
    return 1
  
  ans=0
  for i in range(1,N+1):
    if i==s: continue     #自己閉路は関係ない。
    if tbl[s][i]==1 and (i not in visited):
      visited.append(i)
      ans+=dfs(i,visited)
      visited.pop()　　　　　#dfsを考えているからiをpopする。
  return ans 

answer=dfs(1,[1,])
print(answer)

Submission status: Runtime Error

Solution code:
import copy
def dfs(cur_node, pre_node, Node_num, map, l):
    #全てのノードを見たとき

    if Node_num == N or cur_node <= 0 or cur_node >= N:
        return
    elif l[pre_node][cur_node]==0: #飛んだ先が、Trueの時
        return
    elif map[cur_node]==True:
        return

    map[cur_node]=True
    for i in range(N):
        if i != cur_node:
            dfs(i, cur_node, Node_num+1, map, l)


S = input()
S = list(map(int, S.split()))

N = S[0]
M = S[1]


map = [False]*N
map[0] = True

lst = []

for i in range(M):
    lst.append([0]*N)

for i in range(M):
    S = input()
    S = list(S.split())
    idx1 = int(S[0])
    idx2 = int(S[1])
    lst[idx1-1][idx2-1] = 1
    lst[idx2-1][idx1-1] = 1


graph_count = 0
#全探索
for i in range(1, N, 1):
    map_copy = copy.copy(map)
    lst_copy = copy.copy(lst)

    dfs(i, 0, 0, map_copy, lst_copy)
    count = 0

    for i in map_copy:
        if i == True:
            count = count + 1
    if count == N:
        graph_count = graph_count + 1

print(graph_count)

Submission status: Runtime Error

Solution code:
import copy
def dfs(cur_node, pre_node, Node_num, map, l):
    #全てのノードを見たとき

    if Node_num == N or cur_node <= 0 or cur_node >= N:
        return
    elif l[pre_node][cur_node]==0: #飛んだ先が、Trueの時
        return
    elif map[cur_node]==True:
        return

    map[cur_node]=True
    for i in range(N):
        if i != cur_node:
            dfs(i, cur_node, Node_num+1, map, l)


S = input()
S = list(map(int, S.split()))

N = S[0]
M = S[1]


map = [False]*N
map[0] = True

lst = []

for i in range(N):
    lst.append([0]*N)

for i in range(N):
    S = input()
    S = list(S.split())
    idx1 = int(S[0])
    idx2 = int(S[1])
    lst[idx1-1][idx2-1] = 1
    lst[idx2-1][idx1-1] = 1


graph_count = 0
#全探索
for i in range(1, N, 1):
    map_copy = copy.copy(map)
    lst_copy = copy.copy(lst)

    dfs(i, 0, 0, map_copy, lst_copy)
    count = 0

    for i in map_copy:
        if i == True:
            count = count + 1
    if count == N:
        graph_count = graph_count + 1

print(graph_count)

Submission status: Runtime Error

Solution code:
import copy
def dfs(cur_node, pre_node, Node_num, map, l):
    #全てのノードを見たとき

    if Node_num == N or cur_node <= 0 or cur_node >= N:
        return
    elif l[pre_node][cur_node]==0: #飛んだ先が、Trueの時
        return
    elif map[cur_node]==True:
        return

    map[cur_node]=True
    print(cur_node)
    print(pre_node)
    for i in range(N):
        if i != cur_node:
            dfs(i, cur_node, Node_num+1, map, l)


S = input()
S = list(map(int, S.split()))

N = S[0]
M = S[1]


map = [False]*N
map[0] = True

lst = []

for i in range(N):
    lst.append([0]*N)

for i in range(N):
    S = input()
    S = list(S.split())
    idx1 = int(S[0])
    idx2 = int(S[1])
    lst[idx1-1][idx2-1] = 1


graph_count = 0
#全探索
for i in range(1, N, 1):
    map_copy = copy.copy(map)
    lst_copy = copy.copy(lst)

    dfs(i, 0, 0, map_copy, lst_copy)
    count = 0

    for i in map_copy:
        if i == True:
            count = count + 1
    if count == N:
        graph_count = graph_count + 1

print(graph_count)