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: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys, math, fractions, itertools


def solve(N: int, M: int, a: "List[int]", b: "List[int]"):
    counter = 0
    for i in range(1 << M):
        p = []
        for j in range(M):
            if i >> j & 1 == 1:
                p.append(j)
        G = [[] for _ in range(N)]
        for pp in p:
            G[a[pp]-1].append(b[pp]-1)
            G[b[pp]-1].append(a[pp]-1)
        flag = True
        if any([k > 2 or k < 1 for k in set([len(L) for L in G])]):
            flag = False
        else:
            if len(G[1]) != 1:
                flag = False
            else:
                C = [len(L) for L in G]
                if C.count(1) != 2:
                    flag = False
                else:
                    stack = [0]
                    visited = [0] * N
                    while(len(stack)>0):
                        t = stack.pop()
                        if visited[t] == 0:
                            stack += G[t]
                            visited[t] = 1
                    if sum(visited) != N:
                        flag = False
        if flag:
            counter += 1
    print(counter)
    return


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    a = [int()] * (M)  # type: "List[int]" 
    b = [int()] * (M)  # type: "List[int]" 
    for i in range(M):
        a[i] = int(next(tokens))
        b[i] = int(next(tokens))
    solve(N, M, a, b)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import itertools

n, m = map(int, input().split())
edge = [[0]*n]*n

for i in range(m):
    s, e = map(int, input().split())
    s -= 1
    e -= 1
    edge[s][e] = 1
    edge[e][s] = 1
    
result = 0

cands= list(itertools.permutations(range(1, n)))

def search(cand):
    cand = [0].extend(cand)
    for i in range(1, n):
        if edge[i-1][i] == 0:
            return False
        else:
            return True
for cand in cands:
    result += search(cand)
    
print(result)

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
distinations = [[] for _ in range(N+1)]
for _ in range(M):
  node, dist = map(int, input().split())
  distinations[node].append(dist)
firsts = distinations[1]
stack = []
for _first in firsts:
  stack.append((_first, 2))
cnt = 1
ans = 0
while len(stack) > 0:
  dist = stack.pop()
  cnt = dist[1] + 1
  if cnt == N:
    ans += 1
    continue
  for node in distinations[dist[0]]:
    stack.append((node, cnt))
print(ans)

Submission status: Wrong Answer

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

graph_ex = [[0 for _ in range(N)] for _ in range(N)]
for i in graph:
  graph_ex[i[0]-1][i[1]-1] = 1
  graph_ex[i[1]-1][i[0]-1] = 1

al_vis = [False for _ in range(N)]
def dfs(v, visited, cnt):
  if cnt == N-1 and v != 0:
    return 1
  ret = 0
  for i in range(N):
    if graph_ex[v][i] == 1 and visited[i] == False:
      visited[i] = True
      ret += dfs(i, visited, cnt+1)
      visited[i] = False
  return ret
ret = dfs(0, al_vis, 0)
print(ret)

Submission status: Wrong Answer

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

graph_ex = [[0 for _ in range(N)] for _ in range(N)]
for i in graph:
  graph_ex[i[0]-1][i[1]-1] = 1
  graph_ex[i[1]-1][i[0]-1] = 1

al_vis = [False for _ in range(N)]
def dfs(v, cnt):
  if cnt == N-1 and v != 0:
    return 1
  ret = 0
  for i in range(N):
    if graph_ex[v][i] == 1 and al_vis[i] == False:
      al_vis[i] = True
      ret += dfs(i, cnt+1)
      al_vis[i] = False
  return ret
ret = dfs(0, 0)
print(ret)

Submission status: Wrong Answer

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

graph_ex = [[0 for _ in range(N)] for _ in range(N)]
for i in graph:
  graph_ex[i[0]-1][i[1]-1] = 1
  graph_ex[i[1]-1][i[0]-1] = 1
print(graph_ex)

al_vis = [False for _ in range(N)]
def dfs(v, cnt):
  if cnt == N-1 and v != 0:
    return 1
  ret = 0
  for i in range(N):
    if graph_ex[v][i] == 1 and al_vis[i] == False:
      al_vis[i] = True
      ret += dfs(i, cnt+1)
      al_vis[i] = False
  return ret
ret = dfs(0, 0)
print(ret)

Submission status: Wrong Answer

Solution code:
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)

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
C = [[] for i in range(N)]
for i in range(M):
  a,b = map(int, input().split())
  a -= 1
  b -= 1
  C[a].append(b)
  C[b].append(a)
visited = [0]*N
ans = 0
def dfs(x):
  global ans
  if x == N-1:
    ans += 1
    return
  if visited[x] == 1:
    return
  visited[x] = 1
  for nx in C[x]:
    dfs(nx)
dfs(0)
print(ans)

Submission status: Wrong Answer

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

adj_list = [[] for _ in range(N)]
for a,b in ab:
    adj_list[a-1].append(b-1)
    adj_list[b-1].append(a-1)
ans = 0
def search(s,ans):
    tmp2 = -1
    memo[s] = False
    stack = adj_list[s]
    while stack:
        tmp = stack.pop()
        memo[tmp] = False
        next_list = adj_list[tmp]
        if not(next_list):
            if sum(memo) == 0:
                ans += 1
            else:
                stack.append(tmp2)
                
        for x in next_list:
            if memo[x]:
                stack.append(x)
                memo[x] = False
        tmp2 = tmp
                
    return ans
        
 

stack =adj_list[0]
while stack:
    tmp = stack.pop()
    memo = [True] * N
    memo[0] =False
    ans += search(tmp,ans)

print(ans)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
import itertools
sys.setrecursionlimit(10**5)
stdin = sys.stdin
bisect_left = bisect.bisect_left
bisect_right = bisect.bisect_right
def LI(): return list(map(int, stdin.readline().split()))
def LF(): return list(map(float, stdin.readline().split()))
def LI_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def II(): return int(stdin.readline())
def IF(): return float(stdin.readline())
def LS(): return list(map(list, stdin.readline().split()))
def S(): return list(stdin.readline().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')

#A
def A():
    a, b = LI()
    a -= 2
    b -= 2
    a %= 13
    b %= 13
    if a > b:
        print("Alice")
    elif a < b:
        print("Bob")
    else:
        print("Draw")
    return

#B
def B():
    n, m = LI()
    a = SR(n)
    b = SR(m)
    if a == b:
        print("Yes")
        return
    for y in range(n - m):
        for x in range(n - m):
            if a[y][x] == b[0][0]:
                flg = 0
                for yi in range(m):
                    for xi in range(m):
                        if b[yi][xi] == a[y + yi][x + xi]:
                            continue
                        flg = 1
                        break
                    if flg:
                        break
                if flg:
                    continue
                print("Yes")
                return
    print("No")
    return

#C
def C():
    n, m = LI()
    edg = [[] for i in range(n)]
    for _ in range(m):
        a, b = LI_()
        edg[a].append(b)
        edg[b].append(a)
    def dfs(i, c):
        res = 0
        c[i] = False
        if not (True in c):
            c[i] = True
            return 1
        for e in edg[i]:
            if c[e]:
                res += dfs(e, c)
                print(c)
        c[i] = True
        return res
    print(dfs(0, [True] * n))
    return

#D
def D():
    return

#Solve
if __name__ == '__main__':
    C()

Submission status: Wrong Answer

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
            global r
            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: Wrong Answer

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)]
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: Wrong Answer

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

g = [[] for _ in range(N)]
for a, b in AB:
	a, b = a - 1, b - 1
	g[a] += [b]
	g[b] += [a]

def dfs(v, p, visited):
	if visited[v]:
		return 0
	if v == p:
		return 0
	if v == N - 1:
		return 1
	visited[v] = True
	count = 0
	for n in g[v]:
		count += dfs(n, v, visited)
	return count

print(dfs(0, -1, [False] * N))

Submission status: Wrong Answer

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

g = [[] for _ in range(N)]
for a, b in AB:
	a, b = a - 1, b - 1
	g[a] += [b]
	g[b] += [a]

visited = [False] * N

def dfs(v, p):
	if visited[v]:
		return 0
	if v == p:
		return 0
	if v == N - 1:
		return 1
	visited[v] = True
	count = 0
	for n in g[v]:
		count += dfs(n, v)
	return count

print(dfs(0, -1))

Submission status: Wrong Answer

Solution code:
import itertools

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

paths = []

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

def check(paths):
    prev = 1
    flag = [False] * (N+1)
    flag[1] = True

    for path in paths:
        if path[0] == prev:
            t = path[1]
        elif path[1] == prev:
            t = path[0]
        else:
            return False

        if flag[t]:
            # the node has already been visited
            return False
        prev = t
        flag[t] = True
        if flag.count(True) == N:
            return True

    return False


ans = 0

for path in itertools.permutations(paths):
    if check(path):
        ans += 1

print(ans)

Submission status: Wrong Answer

Solution code:
import itertools

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

paths = []

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

def check(paths):
    prev = 1
    flag = [False] * (N+1)
    flag[1] = True

    for path in paths:
        if path[0] == prev:
            t = path[1]
        elif path[1] == prev:
            t = path[0]
        else:
            return False

        if flag[t]:
            # the node has already been visited
            return False
        prev = t
        flag[t] = True
        if flag.count(True) == N:
            return True

    return True


ans = 0

for path in itertools.permutations(paths):
    if check(path):
        ans += 1

print(ans)

Submission status: Wrong Answer

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: Wrong Answer

Solution code:
import itertools
n, m = map(int, input().split())
d = [[0 for i in range(n)] for j in range(n)]
for i in range(m):
    a, b = map(int, input().split())
    a-=1
    b-=1
    d[a][b] = 1
    d[b][a] = 1
ans = 0

nums = [i for i in range(n)]
for num in itertools.permutations(nums):
    if(num[0] != 0):
        continue
    flag = True
    for i in range(n - 1):
            flag = False
            break
    if(flag):
        ans += 1

print(ans)

Submission status: Wrong Answer

Solution code:
import itertools
n, m = map(int, input().split())
d = [[0 for i in range(n)] for j in range(n)]
for i in range(m):
    a, b = map(int, input().split())
    a-=1
    b-=1
    d[a][b] = 1
    d[b][a] = 1
ans = 0

nums = [i for i in range(n)]
for num in itertools.permutations(nums):
    if(num[0] != 1):
        continue
    flag = True
    for i in range(n - 1):
        if(d[num[i]][num[i+1]] != 1):
            flag = False
            break
    if(flag):
        ans += 1

print(ans)

Submission status: Wrong Answer

Solution code:
import itertools

n,m = map(int, input().split(" "))
data = [list(map(int, input().split(" "))) for _ in range(m)]
count = 0
ans = [i for i in range(1,m+1)]

for x in itertools.permutations(data):
    if not x[0][0] == 1:
        break

    index = 0
    lastP = x[0][1]
    while index < len(x) - 2:
        if not lastP in x[index+1]:
            break
        else:
            for j in x[index+1]:
                if not j == lastP:
                    lastP = j
                    break
            index += 1
    
    flag = False
    if index == len(x)-2:
        tmp = []
        for i in x:
            tmp.append(i[0])
            tmp.append(i[1])
        for mm in range(1,m+1):
            if not mm in tmp:
                flag = True
                break
        if not flag:
            count += 1

print(count)

Submission status: Wrong Answer

Solution code:
import itertools

n,m = map(int, input().split(" "))
data = [list(map(int, input().split(" "))) for _ in range(m)]
count = 0
ans = [i for i in range(1,m+1)]

for x in itertools.permutations(data):
    if not x[0][0] == 1:
        break

    index = 0
    lastP = x[0][1]
    while index < len(x) - 2:
        if not lastP in x[index+1]:
            break
        else:
            for j in x[index+1]:
                if not j == lastP:
                    lastP = j
                    break
            index += 1
    
    flag = False
    if index == len(x)-2:
        tmp = []
        for i in x:
            tmp.append(i[0])
            tmp.append(i[1])
        for mm in range(1,m*1):
            if not mm in tmp:
                flag = True
                break
        if not flag:
            count += 1

print(count)

Submission status: Wrong Answer

Solution code:
import itertools

n,m = map(int, input().split(" "))
data = [list(map(int, input().split(" "))) for _ in range(m)]
count = 0

for x in itertools.permutations(data):
    if not x[0][0] == 1:
        break

    index = 0
    lastP = x[0][1]
    while index < len(x) - 2:
        if not lastP in x[index+1]:
            break
        else:
            for j in x[index+1]:
                if not j == lastP:
                    lastP = j
                    break
            index += 1
    
    if index == len(x)-2:
        count += 1

print(count)

Submission status: Wrong Answer

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, visited):
    # print('cur={}, ans={}'.format(cur, ans))
    visited.append(cur)
    if len(visited) == N:
        # print('goal')
        return True
    for n in C[cur]:
        if n not in visited:
            return visit(n, visited)
    return False

ans = 0
for n in C[0]:
    visited = [0]
    cleared = visit(n, visited)
    ans += (1 if cleared else 0)

print(ans)

Submission status: Wrong Answer

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 len(visited) == N:
        # print('goal')
        return ans + 1
    for n in C[cur]:
        if n not in visited:
            return visit(n, ans, visited)
    return 0

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

print(ans)

Submission status: Wrong Answer

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 len(visited) == N:
        # print('goal')
        return ans + 1
    for next in C[cur]:
        if next not in visited:
            return visit(next, ans, visited)
    return 0

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

print(ans)

Submission status: Wrong Answer

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 len(visited) == N:
        # print('goal')
        return ans + 1
    for next in C[cur]:
        if next not in visited:
            return visit(next, ans, visited)
    return 0

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

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
from itertools import combinations as comb

N, M = map(int, input().split())
ab = [[int(_) for _ in input().split()] for _ in range(M)]
ans = 0
cand = list(comb(ab, N-1))

for i in cand:
    tmp = []
    one = 0
    two = 0
    index = 1
    flag = True
    for j in range(N-1):
        tmp.append(list(i[j]))
    tmp = sorted(sum(tmp, []))
    
    if tmp[1] == 1:
            flag = False
            continue
    else:
        while True:
            if tmp[index] == N:
                if index == 2*(N-1)-1:
                    one += 1
                    break
                elif index == 2*(N-2):
                    two += 1
                    break
            else:
                if tmp[index] != tmp[index+1]:
                    one += 1
                    index += 1
                elif tmp[index] != tmp[index+2]:
                    two += 1
                    index += 2
                else:
                    flag = False
                    break
    
    if flag and one == 1 and two == N-2:
        ans += 1

print(ans)

Submission status: Wrong Answer

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

graph = [[None] * N for _ in range(N)]
for x, y in edges:
    graph[x - 1][y - 1] = True
    graph[y - 1][x - 1] = True
    
def dfs(v):
    global ans
    visited[v] = True
    
    if all(visited):
        ans += 1
        return
    
    for i in range(N):
        if not graph[v][i]:
            continue
        if visited[i]:
            continue
            
        visited[v] = True
        dfs(i)
        visited[v] = False

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

Submission status: Wrong Answer

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

graph = [[None] * N for _ in range(N)]
for x, y in edges:
    graph[x - 1][y - 1] = True
    graph[y - 1][x - 1] = True
    
def dfs(v):
    global ans
    visited[v] = True    
    if all(visited):
        ans += 1
        visited[v] = False
        return
    
    for i in range(N):
        if not graph[v][i]:
            continue
        if visited[i]:
            continue
        dfs(i)

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

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
ab = [list(map(int,input().split())) for _ in range(M)]
import itertools
import queue
L = list(range(1,M+1))
Llist = list(itertools.combinations(L,N-1))
ans = 0
for i in range(len(Llist)):
    tmp = []
    for j in Llist[i]:
        tmp += [ab[j-1]]
    q = queue.Queue()
    tmp.sort()
    if tmp[0][0] == 1:
        q.put(tmp[0][1])
        del tmp[0]
    else:continue
    while not q.empty():
        s = q.get()
        for j in range(len(tmp)):
            if tmp[j][0] == s:
                q.put(tmp[j][1])
                del tmp[j]
                break
            elif tmp[j][1] == s:
                q.put(tmp[j][0])
                del tmp[j]
                break
        else:break
    if len(tmp) == 0:
        ans += 1
    
print(ans)

Submission status: Wrong Answer

Solution code:
# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math
import sys

mod = 10**9+7
sys.setrecursionlimit(mod) # 再帰回数上限はでdefault1000

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

def dfs(node,p,passed):
    if len(passed) == N-1:
        return 1
    cnt = 0

    for new_node in tree[node]:
        if new_node == p:
            continue
        if not new_node in passed:
            passed2 = copy.deepcopy(passed)
            passed2 += [new_node]
            cnt += dfs(new_node,node,passed2)
    return cnt

ans = dfs(0,-1,[])
print(ans)

Submission status: Wrong Answer

Solution code:
# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math
import sys

mod = 10**9+7
sys.setrecursionlimit(mod) # 再帰回数上限はでdefault1000

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

def dfs(node,p,passed):
    if len(passed) == N:
        return 1
    cnt = 0

    for new_node in tree[node]:
        if new_node == p:
            continue
        if not new_node in passed:
            passed2 = copy.deepcopy(passed)
            passed2 += [new_node]
            cnt += dfs(new_node,node,passed2)
    return cnt

ans = dfs(0,-1,[])
print(ans)

Submission status: Wrong Answer

Solution code:
# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math
import sys

mod = 10**9+7
sys.setrecursionlimit(mod) # 再帰回数上限はでdefault1000

N,M = map(int,input().split())
tree = [[] for i in range(N)]
for i in range(M):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    tree[a] += [b]
    tree[b] += [a]
position = 0


def dfs(node,p,passed,ans):
    if len(passed) == N - 1:
        return ans + 1
    for new_node in tree[node]:
        if new_node == p:
            continue
        if not new_node in passed:
            passed += [node]
            return dfs(new_node,node,passed,ans)


ans = dfs(0,-1,[],0)
print(ans)

Submission status: Wrong Answer

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))) * i[0] ==0
print(s)

Submission status: Wrong Answer

Solution code:
ans = 0
def dfs(v, visitedNode, graph):
    visitedNode[v] = 1  # 探索済みとして True にする
    if all(visitedNode):
        global ans
        ans += 1
        return
    for node in graph[v]:   # v の隣接端子を調べる
        if visitedNode[node]:
            # 探索済みなので、ほかの隣接候補へ。
            continue
        else:
            # 未探索なので、さらに次の隣接端子の探索へ
            dfs(node, visitedNode, graph)


N, M = map(int, input().split())
v = 0
visitedNode = [0] * N


# 隣接リストを作成する
graph = [[] for _ in range(N)]
for _ in range(M):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    graph[a].append(b)
    graph[b].append(a)


# 深さ優先探索で経路数を数える
dfs(v, visitedNode, graph)
print(ans)

Submission status: Wrong Answer

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

    edges = []
    nodes = list(range(1, n + 1))

    for i in range(m):
        a, b = map(int, input().split())
        edges.append((a, b))


    edges_dic = {}
    for i in range(n):
        edges_dic[i + 1] = []

    for edge in edges:
        edges_dic[edge[0]].append(edge[1])
        edges_dic[edge[1]].append(edge[0])

    return n, m, nodes, edges_dic


# throughを通過済みとして、curr_nodeから残りのnodesにたどり着けるかチェックする
def check_path(curr_node, rest_nodes, edges_dic, through):
    # 終点
    if not rest_nodes:
        return 1

    # rest_nodesのうち、curr_nodeからいけるnodeがあるか確認する
    next_nodes = edges_dic[curr_node]
    targets = []
    for n in next_nodes:
        if n in rest_nodes:
            targets.append(n)

    # restがあるにもかかわらず、次にいけるnodeがない
    if not targets:
        return 0

    # いけるnodeがあれば、その分チェックする
    count = 0
    for t in targets:
        new_rest = [r for r in rest_nodes if r != t]
        new_through = through + [curr_node]
        count += check_path(t, new_rest, edges_dic, new_through)

    return count



def submit():
    n, m, nodes, edges_dic = read_input()

    rest_nodes = [r for r in nodes if r != 1]
    print(check_path(1, rest_nodes, edges_dic, []))

Submission status: Wrong Answer

Solution code:
# vim: set fileencoding=utf-8:

# https://atcoder.jp/contests/abc054/tasks/abc054_c
# 無向ハミルトン路を数え上げる問題。ただし開始点が必ず 1 になる。


def main():
    nodes = initialize()
    root = nodes[1]
    ans = 0

    # root.simple_depth_first_search()
    root.taboo_depth_first_search()
    ans += 1 if len(list(filter(lambda n: n.passed == False, nodes))) == 0 else ans
    for n in nodes:
        n.passed = False

    root.taboo_depth_first_search()

    print(ans)


def initialize():
    """標準入力を受け取って Node のリストを返す。

    """
    N, M = map(int, input().split())  # 1 <= M <= N <= 50
    a = [0] * M
    b = [0] * M

    nodes = [Node(-1)] + [Node(idx) for idx in range(1, N+1)]

    for i in range(M):
        a[i], b[i] = map(int, input().split())
        assert nodes[a[i]].id == a[i]
        assert nodes[b[i]].id == b[i]
        nodes[a[i]].edges.append(nodes[b[i]])
        nodes[b[i]].edges.append(nodes[a[i]])

    return nodes


class Node:
    """原始的な Node クラス
    """

    def __init__(self, id):
        self.id = id
        self.edges = []
        self.passed = False
        self.taboo = []

    def simple_depth_first_search(self):
        if self.passed == False:
            self.passed = True
            print(self.id)
        else:
            return

        for n in self.edges:
            n.simple_depth_first_search()

    def taboo_depth_first_search(self):
        if self.passed == False:
            self.passed = True
            print(self.id)
        else:
            return

        for idx, n in enumerate(self.edges):
            if [idx] <= self.taboo:
                continue

            n.taboo_depth_first_search()
            if len(self.edges) >= 2:
                self.taboo.append(idx)


if __name__ == "__main__":
    main()