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 copy
def dfs(cur_node, pre_node, Node_num, map, l):
    #全てのノードを見たとき

    if Node_num == N or cur_node <= 0 or cur_node >= N-1:
        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
map[N-1] = 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)

Submission status: Runtime Error

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

    if Node_num == N-1 or cur_node <= 0 or cur_node >= N-1:
        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
map[N-1] = 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)

Submission status: Runtime Error

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

    if Node_num == N-1 or cur_node <= 0 or cur_node >= N-1:
        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
map[N-1] = 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-1:
        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-1:
        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
map[N-1] = 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-1:
        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-1:
        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

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-1:
        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

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-1:
        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-1 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

    dfs(cur_node+1, cur_node, Node_num+1, map, l)
    dfs(cur_node-1, 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)

Submission status: Runtime Error

Solution code:
N,M=map(int,input().split())
ab=[[0]*8]*8
a=[0]*M
b=[0]*M

reached=[0]*M

for i in range(M):
  a[i],b[i]=map(int,input().split())
  ab[a[i]-1][b[i]-1]=1
  ab[b[i]-1][a[i]-1]=1
    
def rootCount(pos,N,reached):
  count=0
  prev=0
  finish=1
  for i in range(N):
    if reached[i] == 0:
      finish=0
  if finish==1:
    return 1
    
  
  for i in range(1,N):
    if ab[pos][i]==0:
      continue
    if reached[i]==1:
      continue
    reached[i]=1
    count+=rootCount(i,N,reached)
    reached[i]=0
  return(count)

reached[0]=1
count=rootCount(0,N,reached)
print(count)

Submission status: Runtime Error

Solution code:
N,M=map(int,input().split())
ab=[[0]*8]*8
a=[0]*M
b=[0]*M

reached=[0]*M

for i in range(M):
  a[i],b[i]=map(int,input().split())
  ab[a[i]-1][b[i]-1]=1
  ab[b[i]-1][a[i]-1]=1
    
def rootCount(pos,N,reached):
  count=0
  prev=0
  finish=1
  for i in range(N):
    if reached[i] == 0:
      finish=0
  if finish==1:
    return 1
    
  
  for i in range(N):
    if ab[pos][i]==0:
      continue
    if reached[i]==1:
      continue
    reached[i]=1
    count+=rootCount(i,N,reached)
    reached[i]=0
  return(count)

reached[0]=1
count=rootCount(0,N,reached)
print(count)

Submission status: Runtime Error

Solution code:

N,M=map(int,input().split())
ab=[[0]*M]*M
a=[0]*M
b=[0]*M

reached=[0]*M

for i in range(M):
  a[i],b[i]=map(int,input().split())
  ab[a[i]][b[i]]=1
  ab[b[i]][a[i]]=1
    
def rootCount(pos,N,reached):
  count=0
  prev=0
  for i in range(N):
    if ab[pos][i]==0:
      continue
    if reached[i]==1:
      continue
    reached[i]=1
    count+=rootCount(i,N,reached)
    reached[i]=0
  return(count)

reached[0]=1
count=rootCount(0,N,reached)
print(count)

Submission status: Runtime Error

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

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

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

def dfs(v, visited, es, cnt):

    #print("--------------")
    #print((v, visited, cnt))

    if cnt == N-1:
        return 1
    ret = 0
    for i in es[v]:
        if visited[i] == True:
            continue

        visited[i] = True
        ret += dfs(i, visited, es, cnt+1)
        visited[i] = False

    return ret

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

ans = dfs(0,visited,es,0)
print(ans)

Submission status: Runtime Error

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

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

def dfs(v, visited, es, cnt):

    #print("--------------")
    #print((v, visited, cnt))

    if cnt == N-1:
        return 1
    ret = 0
    for i in es[v]:
        if visited[i] == True:
            continue

        visited[i] = True
        ret += dfs(i, visited, es, cnt+1)
        visited[i] = False

    return ret

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

ans = dfs(0,visited,es,0)
print(ans)

Submission status: Runtime Error

Solution code:
n, m = map(int,input().split())
lis = [0 for i in range(m)]
for i in range(m):
    lis[i] = list(map(int,input().split()))
    
seen = []
count = 0
visited = [0 for i in range(m)]
r = 0
def route(x=1):
    for i in range(m):
        if lis[i][0] == x and visited[i] == 0:
            visited[i] = 1
            r += 1
            route(lis[i][1])
            visited[i] = 0
            r -= 1
        elif lis[i][1] == x and visited[i] == 0:
            visited[i] = 1
            r += 1
            route(lis[i][0])
            visited[i] = 0
            r -= 1
        if r == n-1:
            global count
            count += 1
            return
        
            
        
route(1)
print(count)

Submission status: Runtime Error

Solution code:
n, m = map(int,input().split())
lis = [0 for i in range(m)]
for i in range(m):
    lis[i] = list(map(int,input().split()))
    
seen = []
count = 0
def route(x=1):
    for i in range(m):
        if lis[i][0] == x and visited[i] == 0:
            visited[i] = 1
            route(lis[i][1])
            visited[i] = 0
        elif lis[i][1] == x and visited[i] == 0:
            visited[i] = 1
            route(lis[i][0])
            visited[i] = 0
        r = 0
        for j in visited:
            r += j
        if r == n-1:
            global count
            count += 1
            return
        
            
        
route(1)
print(count)

Submission status: Runtime Error

Solution code:
def dfs(v,N,visit_list):

    all_visit = True

    for i in range(N):
        if visit_list[i] == False:
            all_visit = False
    
    if all_visit:
        return 1

    ret = 0

    for k in range(N):
        if Graph[v][k] == False:
            continue
        if visit_list[k] :
            continue
        
        visit_list[k] = True
        ret += dfs(k,N,visit_list)
        visit_list[k] = False
    return ret

visit_list = [False for i in range(N)]
visit_list[0] = True
print(dfs(0,N,visit_list))

Submission status: Runtime Error

Solution code:
N,M = map(int,input().split())
pat = [[int(i) for i in input().split()] for _ in range(M)]
Graph = [[0 for i in range(N)] for _ in range(N)]
for i,j in pat:
    Graph[i-1][j-1] = 1
    Graph[j-1][i-1] = 1

def dfs(v,N=N,visit_list):

    all_visit = True

    for i in range(N):
        if visit_list[i] == False:
            all_visit = False
    
    if all_visit:
        return 1

    ret = 0

    for k in range(N):
        if Graph[v][k] == False:
            continue
        if visit_list[k] :
            continue
        
        visit_list[k] = True
        ret += dfs(k,N,visit_list)
        visit_list[k] = False
    return ret

visit_list = [False for i in range(N)]
visit_list[0] = True
print(dfs(0,N,visit_list))

Submission status: Runtime Error

Solution code:

N,M = map(int,input().split())
lis = []
path = ["1"]

for i in range(M):

    a,b = map(int,input().split())
    lis.append([a,b])

for i in range(N-1):

    i += 1

    npath = []

    for p in path:


        for j in lis:

            if j[0] == int(p[-1]) and str(j[1]) not in p:

                npath.append(p + str(j[1]))

            if j[1] == int(p[-1]) and str(j[0]) not in p:

                npath.append(p + str(j[0]))

    path = npath.copy()


print (len(path))

Submission status: Runtime Error

Solution code:
N,M=map(int,input().split())
inp=[list(map(int,input().split())) for _ in range(N)]
g=[[] for _ in range(N)]
[g[a-1].append(b-1) for a,b in inp]
[g[b-1].append(a-1) for a,b in inp]
 
from itertools import permutations
seq=[i for i in range(N)]
test=list(permutations(seq))
cnt=0
for t in test:
    if t[0]==0:
        for i in range(len(t)-1):
            if t[i+1] not in g[t[i]]:
                break
        else:
            cnt+=1
print(cnt)

Submission status: Runtime Error

Solution code:
N,M=map(int,input().split())
inp=[list(map(int,input().split())) for _ in range(N)]
g=[[] for _ in range(N)]
[g[a-1].append(b-1) for a,b in inp]
[g[b-1].append(a-1) for a,b in inp]

from itertools import permutations
seq=[i for i in range(N)]
test=list(permutations(seq))
cnt=0
for t in test:
    if t[0]==0:
        for i in range(len(t)-1):
            if t[i+1] not in g[t[i]]:
                break
        cnt+=1
print(cnt)

Submission status: Runtime Error

Solution code:
N,M = map(int,input().split())
if M == 0:
    print(0)
else:
    l = [[0 for _ in range(M)] for _ in range(M)]
    for _ in range(M):
        a,b = map(int,input().split())
        l[a-1][b-1] = 1
        l[b-1][a-1] = 1
    g = 0
    def dfs(a,route):
        global g
        if len(route) == N:g += 1
        else:
            for i in range(N):
                if a == i:pass
                else:
                    if l[a][i] == 1 and (not i in route):
                        dfs(i,route+[i])
    dfs(0,[0])
print(g)

Submission status: Runtime Error

Solution code:
N,M = map(int,input().split())
l = [[0 for _ in range(M)] for _ in range(M)]
for _ in range(M):
    a,b = map(int,input().split())
    l[a-1][b-1] = 1
    l[b-1][a-1] = 1
g = 0
def dfs(a,route):
    global g
    if len(route) == N:g += 1
    else:
        for i in range(N):
            if a == i:pass
            else:
                if l[a][i] == 1 and (not i in route):dfs(i,route+[i])
dfs(0,[0])
print(g)

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())
d = {i+1 : [] for i in range(n)}
for _ in range(n):
  a, b = map(int, input().split())
  d[a].append(b)
  d[b].append(a)
ans = 0
def go(c, rem):
  global ans
  if not len(rem):
    ans += 1
    return
  for cand in d[c]:
    if cand in rem:
      i = rem.index(cand)
      go(cand, rem[:i] + rem[i+1:])
go(1, list(range(2, n+1)))
print(ans)

Submission status: Runtime Error

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

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

def dfs(v):
    n_visited = sum([1 if v else 0 for v in visited])
    if n_visited == N:
        return 1 
    
    ret = 0
    for u in to[v]:
        if not visited[u]:
            visited[u] = True
            ret += dfs(u)
            visited[u] = False  # 最も深い点から帰ってくる道中に、始点を除く全ての点を未訪問にする => 他のパスを辿ることが可能になる

    return ret


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

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

Submission status: Runtime Error

Solution code:
def inpl(): return list(map(int, input().split()))

N, M = inpl()
G = [[0]*(N+1) for _ in range(N+1)]

for _ in range(M):
    a, b = inpl()
    G[a][b] = 1
    G[b][a] = 1

ans = 0
for X in permutations(range(2, N+1)):
    a = 1
    for i in range(N-1):
        b = X[i]
        if G[a][b] == 0:
            break
        a = b
    else:
        ans += 1

print(ans)

Submission status: Runtime Error

Solution code:
# 全域木？っていうんだっけ？でもコストは関係ないか
# 適当に隣接リストでもってしてDFSする
N, M = map(int, input().split())
Neighbor_list = [[] for _ in range(n)]
for _ in range(M):
    s, t = map(int, input().split())
    Neighbor_list[s-1].append(t-1)
    Neighbor_list[t-1].append(s-1)


def dfs(cur, path):
    if len(path) == N:
        return 1
    else:
        ret = 0
        for neighbor in Neighbor_list[cur]:
            if neighbor not in path:
                next_list = path[:]
                next_list.append(neighbor)
                ret += dfs(neighbor, next_list)
        return ret


print(dfs(0, []))

Submission status: Runtime Error

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

gr = set()

for i in range(N):
    a, b = map(int, input().split())
    gr |= {(a-1,b-1),(b-1,a-1)}

from itertools import permutations

ans = 0
for p in permutations(range(N)):
    if p[0]==0:
        cnt = 0
        cntp = 0
        for i in range(N-1):
            cnt += 1
            if (p[i],p[i+1]) in gr:
                cntp += 1
            else:
                break
        if cnt == cntp:
            ans += 1
print(ans)

Submission status: Runtime Error

Solution code:
import itertools
N,M = map(int,input().split())
edges = set()
for _ in range(N):
  a,b = map(int,input().split())
  edges.add((a,b))
  edges.add((b,a))

answer = 0

for p in itertools.permutations(range(1,N+1)):
  if p[0] != 1:
    continue
  bl = True
  for i in range(N-1):
    if (p[i], p[i+1]) not in edges:
      bl = False
      break
  if bl:
    answer += 1

print(answer)

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())
adj_matrix = [[0] * n for _ in range(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
  
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:
import sys
from collections import deque

sys.setrecursionlimit(4100000)


def inputs(num_of_input):
    ins = [input() for i in range(num_of_input)]
    return ins


def solve(N, M, inputs):
    relations = {}
    visited_all = (2 ** N) - 1
    for i in range(1, N + 1):
        relations[i] = []

    for i in inputs:
        [parent, child] = string_to_int(i)
        relations[parent].append(child)
        relations[child].append(parent)

    routes = 0
    queue = deque([[1, 0]])
    while len(queue) > 0:
        [node, visited] = queue.popleft()

        if visited & (1 << (node - 1)) != 0:
            continue

        visited = visited + (1 << (node - 1))

        if visited == visited_all:
            routes += 1
            continue

        for next in relations[node]:
            queue.append([next, visited])
    return routes


def string_to_int(string):
    return list(map(lambda x: int(x), string.split()))


if __name__ == "__main__":
    [N, M] = string_to_int(input())
    ret = solve(inputs(M))
    print(ret)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10000)
n,m=map(int,input().split())
bra=[set() for _ in range(m)]
for i in range(m):
    a,b=map(int,input().split())
    bra[a-1].add(b-1)
    bra[b-1].add(a-1)

visit=[1]+[0]*(n-1)
#print(bra)
cnt=[]
def dfs(a,visit):
    if visit==[1]*n:
        cnt.append(1)
        return 
    else:
        for e in bra[a]:
            if visit[e]==0:
                visit[e]=1
#                print(visit)
                dfs(e,visit)
                visit[e]=0   
dfs(0,visit)
print(len(cnt))

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10000)
n,m=map(int,input().split())
bra=[set() for _ in range(m)]
for i in range(m):
    a,b=map(int,input().split())
    bra[a-1].add(b-1)
    bra[b-1].add(a-1)

visit=[1]+[0]*(n-1)
#print(bra)
cnt=[]
def dfs(a,visit):
    if visit==[1]*n:
        cnt.append(1)
        return 
    else:
        for e in bra[a]:
            if visit[e]==0:
                visit[e]=1
#                print(visit)
                dfs(e,visit)
                visit[e]=0   
dfs(0,visit)
print(sum(cnt))

Submission status: Runtime Error

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

visit=[1]+[0]*(n-1)
#print(bra)
cnt=[]
def dfs(a,visit):
    if visit==[1]*n:
        cnt.append(1)
        return 
    else:
        for e in bra[a]:
            if visit[e]==0:
                visit[e]=1
#                print(visit)
                dfs(e,visit)
                visit[e]=0

                
dfs(0,visit)
print(sum(cnt))

Submission status: Runtime Error

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



pair=[[0]*n for i in range(n)]
for i,j in lst:
    pair[i-1][j-1]=1
    pair[j-1][i-1]=1


def keiro(a):
    count=0
    for i in range(n-1):
        if pair[a[i]-1][a[i+1]-1]==0:
            break
    else:
        count+=1
    return count
cn=0
b=[i for i in range(2,m+1)]
for i in list(itertools.permutations(b)):

    a=[1]+list(i)

    if keiro(a)==1:
        cn+=1

print(cn)

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
graph = []
visited = []
def dfs(v, N, visited):
    all_visited = True

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

for i in range(M):
    graph.append([False] * 8)
for i in range(N):
    visited.append(False)
for i in range(M):
    A, B = map(int, input().split())
    graph[A-1][B-1] = graph[B-1][A-1] = True

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

Submission status: Runtime Error

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

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

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

P = permutations([0] + [i for i in range(1,N)])

ans = 0

for perm in P :
    visited = [0 for i in range(N)]
    visited[0] = 1
    for i in range(N-1) :
        if perm[i+1] not in L[perm[i]] :
            break
         
        if visited[perm[i+1]] :
            break
        
        visited[perm[i+1]] = 1
    
    if sum(visited) == N :
        ans += 1

print(ans)

Submission status: Runtime Error

Solution code:
l = input().split()
N = int(l[0])
M = int(l[1])

A = []
B = []
C = [[] for i in range(N)]

for i in range(M):
    l = input().split()
    a = int(l[0]) - 1
    b = int(l[1]) - 1
    A.append(a)
    B.append(b)
    C[a].append(b)
    C[b].append(a)

# print(N, M, A, B, C)

def visit(cur, ans, visited):
    # print('cur={}, ans={}'.format(cur, ans))
    visited.append(cur)
    if cur == N - 1:
        # print('goal')
        return ans + 1
    for next in C[cur]:
        if next not in visited:
            return visit(next, ans, visited)

ans = 0
for next in C[0]:
    visited = []
    ans += visit(0, 0, visited)

print(ans)

Submission status: Runtime Error

Solution code:
import itertools
n,m=map(int,input().split())
A=[]
for i in range(n):
  a,b=map(int,input().split())
  A.append([a,b])
N=[int(i+2) for i in range(n-1)]
def f(list,n):
  path=0
  if [1,list[0]] in A:
    path+=1
  for i in range(1,n-1):
    if [list[i],list[i-1]] in A or [list[i-1],list[i]] in A:
      path+=1
  if path==n-1:
    return 1
  else:
    return 0  
ans=0
for p in itertools.permutations(N,n-1):
  ans+=f(list(p),n)
print(ans)

Submission status: Runtime Error

Solution code:
import itertools
N,M=map(int,input().split())
ab=list(list(map(int,input().split())) for _ in range(N))
l=list(l for l in range(1,N+1))
numlist=list(itertools.permutations(l))
ans=0
for I in numlist:
    x=0
    if I[0]==1 and all(sorted([I[j],I[j+1]]) in ab for j in range(N-1)):
        ans+=1
print(ans)

Submission status: Runtime Error

Solution code:
n,m = map(int,input())
path = [map(int,input()) for x in range(m)]

table = [[] for x in range(n)]
for x in path:
    table[int(x[0])-1].append(int(x[1])-1)
    table[int(x[1])-1].append(int(x[0])-1)
    
import itertools
count = 0
for z in itertools.permutations(range(0,n)):
    if z[0] == 0:
        print(z)
        for y in range(len(z)-1):
            if z[y+1] in table[z[y]]:
                continue
            else:
                count -= 1
                break
        count += 1

Submission status: Runtime Error

Solution code:
from itertools import permutations

n,m=map(int,input().split())
path=set()
for _ in range(m):
    u,v=map(int,input().split())
    path|={(u-1,v-1),(v-1,u-1)}
s = 0
for i in permutations(range(n)):
    s+=(all((h,j) in path for h,j in zip(i[1:],i))) if i[0] ==0
print(s)

Submission status: Runtime Error

Solution code:

#########
#thiking Face
from itertools import permutations

n,m=map(int,input().split())
path=set()
for _ in range(m):
    u,v=map(int,input().split())
    path|={(u-1,v-1),(v-1,u-1)}

print(sum(all((u,v) in es for u,v in zip(p,p[1:]))
          for p in permutations(range(n)) if p[0]==0))

Submission status: Runtime Error

Solution code:
###########

#########
#thiking Face
from itertools import permutations

n,m=map(int,input().split())
path=set()
for _ in range(m):
    u,v=map(int,input().split())
    path|={(u-1,v-1),(v-1,u-1)}

print(sum(all((u,v) in es for u,v in zip([0]+p,p))
          for p in permutations(range(1,n))))

Submission status: Runtime Error

Solution code:
import numpy as np
N, M = map(int, input().split())

Adj_matrix = np.zeros((N, N))
for _ in range(N):
    a, b = map(int, input().split())
    Adj_matrix[a - 1, b - 1] += 1
    Adj_matrix[b - 1, a - 1] += 1
    
def initialize():
    explored_list = np.zeros((N, 1))
    return explored_list
  
def is_move(vertex, explored_list, Adj_martrix):
    for i in range(len(explored_list)):
        if explored_list[i] == 0 and Adj_martrix[vertex - 1, i] == 1:
            return True
    return False
  
import copy

g_count = 0

def graph_exp(vertex, explored_list, Adj_matrix):
    global g_count
    
    explored_list[vertex - 1] += 1
    
    # Recursive End
    if not is_move(vertex, explored_list, Adj_matrix):
        g_count += all(explored_list)
        return 0
    
    # Recursive Call
    for i in range(len(explored_list)):
        if explored_list[i] == 0 and Adj_matrix[vertex - 1, i] == 1:
            graph_exp(i + 1, copy.copy(explored_list), Adj_matrix)
    
explored_list = initialize()

graph_exp(1, explored_list, Adj_matrix)

print(g_count)

Submission status: Runtime Error

Solution code:
import itertools

n, m = [int(x) for x in input().split()]
edges = set(tuple(int(x) for x in input().split()) for _ in range(m))
print(sum(1 if all(p in edges or tuple(reversed(p)) in edges for p in [(1, path[0]), *zip(path, path[1:])]) else 0 for path in itertools.permutations(range(2, n + 1))))

Submission status: Runtime Error

Solution code:
def dfs(v, N, visited, graph):

    all_visited = True

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

    if all_visited:
        return 1

    ret = 0

    for i in range(N):
        if graph[v][i] is False:
            continue
        if visited[i]:
            continue

        visited[i] = True
        ret += dfs(i, N, visited, graph)
        visited[i] = False

    return ret

N, M = [int(i) for i in input().split(" ")]
graph = [[False for i in range(M)] for i in range(M)]

for i in range(M):
    A, B = [int(i) for i in input().split()]
    graph[A-1][B-1] = graph[B-1][A-1] = True

visited = [False for i in range(N)]
visited[0] = True
print(dfs(0, N, visited, graph))

Submission status: Runtime Error

Solution code:
import itertools

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

ans=0
for i in itertools.permutations(list(range(n))):
  if i[0]!=0:
    continue
  flg=True
  for j in range(len(i)-1):
    if path[min(i[j],i[j+1])][max(i[j],i[j+1])]==False:
      flg=False
      break
  if flg:
    ans+=1
print(ans)

Submission status: Runtime Error

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

import itertools
ans = 0
for p in itertools.permutations(range(n)):
    if p[0] == 0:
        flag = True
        for i in range(n-1):
            if not p[i+1] in l[p[i]]:
                flag = False
        if flag:
            ans += 1
print(ans)