TnT/Multi_CodeNet4Repair huggingface dataset:
Problem: 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

Submission attempts (in order):
def main():
    import sys
    from itertools import permutations
    
    readlines = sys.stdin.buffer.readlines
    N, M = map(int, input().split())
    edge = [[0] * N for _ in range(N)]
    for s in readlines():
        a, b = map(int, s.split())
        a -= 1; b -= 1
        edge[a][b] = 1
        edge[b][a] = 1

    cnt = 0
    for path in permutations(range(1, N)):
        path = [0] + list(path)
        for i in range(N - 1):
            v = path[i]
            nv = path[i + 1]
            if edge[v][nv] == 0:
                break
        else:
            cnt += 1
    print(cnt)


if __name__ == "__main__":
    main()


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

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


def dfs(node, track):
    if track == [False] * N:
        global res
        res += 1
    else:
        for dst in edges[node]:
            if track[dst]:
                track[dst] = False
                dfs(dst, track)


res = 0
init_track = [True] + [False] * N
dfs(0, init_track)

print(res)


def main():
    import sys
    from itertools import permutations
    
    readlines = sys.stdin.readlines
    N, M = map(int, input().split())
    edge = [[0] * N for _ in range(N)]
    for s in readlines():
        a, b = map(int, s.split())
        a -= 1; b -= 1
        edge[a][b] = 1
        edge[b][a] = 1

    cnt = 0
    for path in permutations(range(1, N)):
        path = [0] + list(path)
        for i in range(N - 1):
            v = path[i]
            nv = path[i + 1]
            if edge[v][nv] == 0:
                break
        else:
            cnt += 1
    print(cnt)


if __name__ == "__main__":
    main()


Verdicts: Wrong Answer

Wrong Answer

Accepted
Problem: 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

Submission attempts (in order):
import itertools
N,M=map(int,input().split())
edges={tuplec(sorted(map(int,input().split()))) for i in range(M)}
ans=0
for i in itertools.permutations(range(2,N+1),N-1):
    l=[1]+list(i)
    ans+=sum(1 for edge in zip(l,l[1:]) if tuple(sorted(edge)) in edges)==N-1
print(ans)

import itertools
N,M=map(int,input().split())
edges={tuplec(sorted(map(int,input().split()))) for i in range(M)}
ans=0
for i in itertools.permutations(range(2,N+1)):
    l=[1]+list(i)
    ans+=sum(1 for edge in zip(l,l[1:]) if tuple(sorted(edge)) in edges)==N-1
print(ans)

import itertools
N,M=map(int,input().split())
edges={tuple(sorted(map(int,input().split()))) for i in range(M)}
ans=0
for i in itertools.permutations(range(2,N+1)):
    l=[1]+list(i)
    ans+=sum(1 for edge in zip(l,l[1:]) if tuple(sorted(edge)) in edges)==N-1
print(ans)

Verdicts: Runtime Error

Runtime Error

Accepted
Problem: 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

Submission attempts (in order):
import itertools


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

ans = 0
node = list(range(1, N+1))
for x in itertools.permutations(node):
    for i in range(N-1):
        if not edge[x[i]][x[i+1]]:
            break
    else:
        ans += 1

print(ans // 2)

import itertools


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

ans = 0
node = list(range(1, N+1))
for x in itertools.permutations(node):
    if x[0] == 1:
        for i in range(N-1):
            if not edge[x[i]][x[i+1]]:
                break
        else:
            ans += 1

print(ans)

Verdicts: Wrong Answer

Accepted
Problem: 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

Submission attempts (in order):
import itertools

n,m=(map(int,input().split()))
l=[]

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

ans=0
ans_list=[0]*n

for i in range(n):
  l_new=l[0:i]+l[i+1:n]
  l_new=itertools.chain.from_iterable(l_new)
  for i in l_new:
    ans_list[int(i)-1]+=1
  print(ans_list)
  if (ans_list[0]==1) and (ans_list.count(2)==(n-2)) and (ans_list.count(1)==2):
    ans+=1
  ans_list=[0]*n
  
print(ans)

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


is_checked = [False] * N

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

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


is_checked = [False] * N

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

Verdicts: Wrong Answer

Wrong Answer

Accepted
Problem: 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

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

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

import itertools
n, m = map(int, input().split())
G = [set() for _ in range(n)]
for _ in range(m):
    a,b = map(lambda x:int(x)-1, input().split())
    G[a].add(b)
    G[b].add(a)

P = [*itertools.permutations(range(1,n))]
ans = 0
for p in P:
    nw = 0
    for nx in p:
        if nx in G[nw]:
            nw = nx
        else:
            break
    else:
        ans += 1
print(ans)

Verdicts: Runtime Error

Accepted
Problem: 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

Submission attempts (in order):
def dfs(place,number,checkedList,path):
  checkedList[place] = 1
  if sum(checked) == number:
    return 1
  pathNumber = 0
  for i in path[place]:
    if checkedList[i] == 1:
      continue
    pathNumber += dfs(i,number,checkedList,path)
    checkedList[i] = 0
  return pathNumber  

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

checked = [0] * 8
path = [ [] for _ in range(8)]
for i in range(m):
  a, b = map(int, input().split())
  path[a-1].append(b-1)
  path[b-1].append(a-1)
  print(path)
  
print(dfs(0,n,checked,path))

def dfs(place,number,checkedList,path):
  checkedList[place] = 1
  if sum(checked) == number:
    return 1
  pathNumber = 0
  for i in path[place]:
    if checkedList[i] == 1:
      continue
    pathNumber += dfs(i,number,checkedList,path)
    checkedList[i] = 0
  return pathNumber  

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

checked = [0] * 8
path = [ [] for _ in range(8)]
for i in range(m):
  a, b = map(int, input().split())
  path[a-1].append(b-1)
  path[b-1].append(a-1)
  #print(path)
  
print(dfs(0,n,checked,path))

Verdicts: Wrong Answer

Accepted
Problem: 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

Submission attempts (in order):
n, m = map(int, input().split())
ab = [ list(map(int, input().split())) for _ in range(m) ]

graph = [ [False] * 8 for _ in range(8) ]
visited = [False] * n

def dfs(a, N, visited):
    finish = True
    for i in range(N):
        if not visited[i]:
            finish = False
    if finish:
        return 1
    ans = 0
    for i in range(N):
        if not graph[a][i] or visited[i]:
            continue
        visited[i] = True
        ans += dfs(i,N,visited)
        visited[i] = False

for i in range(m):
    graph[ab[i][0]-1][ab[i][1]-1], graph[ab[i][1]-1][ab[i][0]-1] = True, True

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

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

graph = [ [False] * 8 for _ in range(8) ]
visited = [False] * n

def dfs(a, N, visited):
    finish = True
    for i in range(N):
        if not visited[i]:
            finish = False
    if finish:
        return 1
    ans = 0
    for i in range(N):
        if not graph[a][i] or visited[i]:
            continue
        visited[i] = True
        ans += dfs(i,N,visited)
        visited[i] = False
    return ans

for i in range(m):
    graph[ab[i][0]-1][ab[i][1]-1], graph[ab[i][1]-1][ab[i][0]-1] = True, True

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

Verdicts: Runtime Error

Accepted
Problem: 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

Submission attempts (in order):
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)            

N,M=map(int,input().split())
import itertools
graph={i:{} for i in range(1,N+1)}
for _ in range(M):
    a,b=map(int,input().split())
    graph[a][b]=1
    graph[b][a]=1
    
seq=[i+1 for i in range(N)]
Q=list(itertools.permutations(seq))
ans=0
for que in Q:
    flag=True
    s=que[0]
    if s!=1:
        flag=False
    for i in range(1,N):
        node=que[i]
        if node in graph[s]:
            s=node
        else:
            flag=False
        if flag==False:
            break
    ans+=int(flag)
print(ans)    

Verdicts: Runtime Error

Accepted
Problem: 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

Submission attempts (in order):
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)


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


###########

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



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)):
    if i[0] ==0:

        s+=(all((h,j) in path for h,j in zip(i[1:],i)))


print(s)

Verdicts: Runtime Error

Runtime Error

Runtime Error

Accepted
Problem: 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

Submission attempts (in order):
from collections import defaultdict, deque
N, M = map(int, input().split())

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

print(d)


def dfs(n, check):
    check[n - 1] = True
    for i in range(len(d[n])):
        if not check[d[n][i] - 1]:
            check[d[n][i] - 1] = True
            return dfs(d[n][i], check)

    return check


count = 0
for i in range(len(d[1])):
    check = [False] * N
    check[0] = True
    c = dfs(d[1][i], check)
    if False not in c:
        count += 1

print(count)


import itertools
n, m = map(int, input().split())
ab = {}
for i in range(n+1):
    ab[i] = []
for i in range(m):
    a, b = map(int, input().split())
    ab[a].append(b)
    ab[b].append(a)
print(ab) 
count = 0
 
for values in list(itertools.permutations(range(2, n+1))):
    pre = 1
    for i, v in enumerate(values):
        if(v not in ab[pre]):
            break
        if i == n-2:
            count += 1
        pre = v

print(count)

from collections import defaultdict
N, M = map(int, input().split())
d = defaultdict(list)
for _ in range(M):
    a, b = map(int, input().split())
    d[a].append(b)
    d[b].append(a)


def dfs(n, path):
    count = 0
    path.append(n)
    if len(path) == N:
        count += 1
        return count

    for i in range(len(d[n])):
        if d[n][i] not in path:
            count += dfs(d[n][i], path)
            path.pop()

    return count


print(dfs(1, []))


Verdicts: Wrong Answer

Wrong Answer

Accepted
Problem: 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

Submission attempts (in order):
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)


                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)

                from itertools import permutations

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

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

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


from itertools import permutations

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

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

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

Verdicts: Runtime Error

Runtime Error

Runtime Error

Accepted
Problem: 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

Submission attempts (in order):
from collections import deque
N,M=map(int,input().split())
l=[[] for _ in range(N)]
for _ in range(M):
  x,y=map(int,input().split())
  l[x-1].append(y-1)
  l[y-1].append(x-1)

def dfs(N,l):
  stack=deque()
  check=[] 
  ans=0
  s=0
  t=0
  for i in l[0]:
    stack.append(i)
  check.append(0)
  while stack:
    a=stack.pop()
    if a not in check:
      check.append(a)
      if len(check)==N:
        ans+=1
        print(check)
        check.pop()
      else:
        for j in l[a]:
          stack.append(j)
    else:
      continue
  return ans
print(dfs(N,l))

from itertools import permutations
N,M=map(int,input().split())
l=[[] for _ in range(N)]
for _ in range(M):
  x,y=map(int,input().split())
  l[x-1].append(y-1)
  l[y-1].append(x-1)

res=0
for i in permutations(range(2,N+1)):
  s='1'
  for j in i:
    s+=str(j)
  ans=True
  for k in range(N-1):
    ss=int(s[k])-1
    st=int(s[k+1])-1
    if st not in l[ss]:
      ans=False
  if ans:
    res+=1
print(res)

Verdicts: Wrong Answer

Accepted
Problem: 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

Submission attempts (in order):
n, m = map(int, input().split())
l = []
combo = []
for i in range(max(n, m) + 1):
  l.append([])
def dfs(path, now):
  if len(set(path)) == n and not path in combo:
    combo.append(path)
    return

  for i in l[now]:
    if not i in path:
      temp = path[:]
      temp.append(i)
      dfs(temp, i)

  return

if m == 0:
  print(0)
else:

  for i in range(m):
    f, t = map(int, input().split())
    if not t in l[f]:
      l[f].append(t)
    
    if not f in l[t]:
      l[t].append(f)

  dfs([1], 1)
  print(len(combo))n, m = map(int, input().split())
l = []
combo = []
for i in range(max(n, m) + 1):
  l.append([])
def dfs(path, now):
  if len(set(path)) == n and not path in combo:
    combo.append(path)
    return

  for i in l[now]:
    if not i in path:
      temp = path[:]
      temp.append(i)
      dfs(temp, i)

  return

if m == 0:
  print(0)
else:

  for i in range(m):
    f, t = map(int, input().split())
    if not t in l[f]:
      l[f].append(t)
    
    if not f in l[t]:
      l[t].append(f)

  dfs([1], 1)
  print(len(combo))

n, m = map(int, input().split())
l = []
combo = []
for i in range(max(n, m)+1):
  l.append([])
  
def dfs(path, now):
  if len(set(path)) == n and not path in combo:
    combo.append(path)
    return

  for i in l[now]:
    if not i in path:
      temp = path[:]
      temp.append(i)
      dfs(temp, i)

  return

if m == 0:
  print(0)
else:

  for i in range(m):
    f, t = map(int, input().split())
    if not t in l[f]:
      l[f].append(t)
    
    if not f in l[t]:
      l[t].append(f)

  dfs([1], 1)
  print(len(combo))

Verdicts: Runtime Error

Accepted
Problem: 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

Submission attempts (in order):
def dfs(v, N, visited, ret, route):
    if sum(visited) == N:
        return 1
    
    visitable = []
    for pair in route:
        if v in pair:
            if visited[pair[0]] == 0:
                visitable.append(pair[0])
            elif visited[pair[1]] == 0:
                visitable.append(pair[1])
    
    for v in visitable:
        visited[v] = 1
        ret = dfs(v, N, visited, ret, route)
        visited[v] = 0
    
    return ret

N, M = map(int, input().split())
route = []
for i in range(M):
    a, b = map(int, input().split())
    a, b = a-1, b-1
    route.append([a, b])
visited = [0] * N
visited[0] = 1
ret = dfs(0, N, visited, 0, route)
print(ret)

def dfs(v, N, visited, ret, route):
    if sum(visited) == N:
        return ret + 1
    
    visitable = []
    for pair in route:
        if v in pair:
            if visited[pair[0]] == 0:
                visitable.append(pair[0])
            elif visited[pair[1]] == 0:
                visitable.append(pair[1])
    
    for v in visitable:
        visited[v] = 1
        ret = dfs(v, N, visited, ret, route)
        visited[v] = 0
    
    return ret

N, M = map(int, input().split())
route = []
for i in range(M):
    a, b = map(int, input().split())
    a, b = a-1, b-1
    route.append([a, b])
visited = [0] * N
visited[0] = 1
ret = dfs(0, N, visited, 0, route)
print(ret)

Verdicts: Wrong Answer

Accepted
Problem: 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

Submission attempts (in order):

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)

from itertools import permutation
N,M=map(int,input().split())
ab=[list(map(int,input().split())) for i in range(M)]
g=[[False]*N for i in range(N)]
for a,b in ab:
  g[a-1][b-1]=True
  g[b-1][a-1]=True
nodes=[i for i in range(N)]
ans=0
for route in permutation(nodes):
  for i in range(N):
    if i == N-1:
      ans+=1
      break
    if g[route[i]][route[i+1]]:
      continue
    else:
      break
print(ans)
      
    
    

from itertools import permutations
N, M = map(int, input().split())
ab = [tuple(map(int, input().split())) for i in range(M)]
G = [set() for i in range(N)]

for a, b in ab:
    a -= 1
    b -= 1
    G[a].add(b)
    G[b].add(a)

ans = 0
for x in permutations(range(1, N)):
    if x[0] in G[0]:
        for i in range(N-1):
            if i < N-2:
                if x[i+1] in G[x[i]]:
                    continue
                else:
                    break
            else:
                ans += 1
print(ans)


Verdicts: Runtime Error

Runtime Error

Accepted
Problem: 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

Submission attempts (in order):
n, m = map(int, input().split())
ab = [list(map(int, input().split())) for x in range(m)]

abmap = {}
for a, b in ab:
    atarget = abmap.get(a)
    if atarget == None:
        abmap[a] = []
    abmap[a].append(b)

    btarget = abmap.get(b)
    if btarget == None:
        abmap[b] = []
    abmap[b].append(a)

que = [[1, abmap[1], []]]
ends = []
while que:
    now, nextnodes, visited = que.pop()
    ends.append(visited)
    visited.append(now)
    for node in nextnodes:
        if node in visited:
            continue
        mvisited = visited[:]
        que.append([node, abmap[node], mvisited])

print(len(filter(lambda x: len(x) == n, ends)))


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

abmap = {}
for a, b in ab:
    atarget = abmap.get(a)
    if atarget == None:
        abmap[a] = []
    abmap[a].append(b)

    btarget = abmap.get(b)
    if btarget == None:
        abmap[b] = []
    abmap[b].append(a)

que = [[1, abmap[1], []]]
ends = []
while que:
    now, nextnodes, visited = que.pop()
    ends.append(visited)
    visited.append(now)
    for node in nextnodes:
        if node in visited:
            continue
        mvisited = visited[:]
        que.append([node, abmap[node], mvisited])

print(len(list(filter(lambda x: len(x) == n, ends))))


Verdicts: Runtime Error

Accepted
Problem: 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

Submission attempts (in order):
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[p[i+1]][p[i+1]]
        ans += tmp

    print(ans)

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

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[p[i]][p[i+1]]
        ans += tmp

    print(ans)

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 in range(n-1):
            tmp *= S[p[i]][p[i+1]]
        ans += tmp

    print(ans)

if __name__ == '__main__':
    resolve()

Verdicts: Wrong Answer

Runtime Error

Wrong Answer

Accepted
Problem: 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

Submission attempts (in order):
import numpy as np
nmax = 8
graph = np.array([[False]*nmax]*nmax)

n, m = map(int, input().split())
for i in range(m):
    a, b = map(int, input().split())
    graph[a-1][b-1] = graph[b-1][a-1] = True
    
visited = [False]*nmax
visited[0] = True

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
  
dfs(0, n, visited)

import numpy as np
nmax = 8
graph = np.array([[False]*nmax]*nmax)
 
n, m = map(int, input().split())
for i in range(m):
    a, b = map(int, input().split())
    graph[a-1][b-1] = graph[b-1][a-1] = True
    
visited = [False]*nmax
visited[0] = True
 
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
  
print(dfs(0, n, visited))

Verdicts: Wrong Answer

Accepted
Problem: 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

Submission attempts (in order):
N, M = list(map(int, input().split()))

ans = 0

def dfs(n, visited):
    global ans
    visited.append(n)
    if len(visited) == N:
        ans += 1
    else:
        for i in l[n-1]:
            print("i=", i)
            if i not in visited:
                dfs(i, visited)
    visited.remove(n)

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

dfs(1, [])
print(ans)
print(l)

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

ans = 0

def dfs(n, visited):
    global ans
    visited.append(n)
    if len(visited) == N:
        ans += 1
    else:
        for i in l[n-1]:
            if i not in visited:
                dfs(i, visited)
    visited.remove(n)

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

dfs(1, [])
print(ans)

Verdicts: Wrong Answer

Accepted
Problem: 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

Submission attempts (in order):
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)


import itertools

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

path_matrix = []


for n in range(N):
    path_matrix.append([0] * N)

for m in range(M):
    paths = [int(i) - 1 for i in input().split()]
    path_matrix[paths[0]][paths[1]] = 1
    path_matrix[paths[1]][paths[0]] = 1

list_per = list(itertools.permutations(range(N)))
ans = 0

for i in list_per:
    if i[0] != 0:
        break
    cnt = 1
    for index in range(N - 1):
        cnt *= path_matrix[i[index]][i[index + 1]]
    ans += cnt
    
print(ans)


Verdicts: Runtime Error

Accepted