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:

def get_args():
    N, M = map(int, input().split())
    A, B = [], []

    for _ in range(M):
        a, b = map(int, input().split())
        A.append(a)
        B.append(b)

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

    return N, M, A, B


class Graph:
    def __init__(self, vertex_size):
        self.VERTEX_SIZE = vertex_size
        self.adjacency = [set() for i in range(self.VERTEX_SIZE)]

    def add_edge(self, a_i, b_i):
        self.adjacency[a_i].add(b_i)
        self.adjacency[b_i].add(a_i)

    def get_adj(self, i):
        return self.adjacency[i]

    def vertexes_size(self):
        return self.VERTEX_SIZE

    def edges_size(self):
        raise NotImplemented()

def solve(N, M, A, B):
    g = Graph(8 + 2)

    for i in range(M):
        g.add_edge(A[i], B[i])

    marked = [False for _ in range(N + 1)]
    marked[0] = True

    def dfs(i, ans):
        marked[i] = True
        if marked.count(True) == N:
            return 1
        for a in g.get_adj(i):
            if not marked[a]:
                ans += dfs(a, ans)
        return ans

    res = dfs(1, 0)
    return res


if __name__ == '__main__':
    res = solve(*get_args())
    print(res)

Submission status: Wrong Answer

Solution code:
# coding: utf-8


def solve(*args: str) -> str:
    n, m = map(int, args[0].split())
    edges = [set() for _ in range(n)]
    for AB in args[1:]:
        a, b = map(int, AB.split())
        edges[a-1].add(b-1)
        edges[b-1].add(a-1)

    count = 0
    stack = [(1, 0)]
    while stack:
        node, visited = stack.pop()
        visited |= 1 << node

        if visited+1 == 1 << n:
            count += 1

        for dist in edges[node]:
            if visited & (1 << dist) == 0:
                stack.append((dist, visited))

    return str(count)


if __name__ == "__main__":
    print(solve(*(open(0).read().splitlines())))

Submission status: Wrong Answer

Solution code:
from collections import deque

N,M = map(int, input().split())
table = [[] for i in range(N)]
ans = 0

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

Q = deque()
Q.append(0)
visited = [0]*N

def DFS(x):
    global ans
    if visited[x] == 1:
        return
    visited[x] = 1
    if all(visited):
        ans += 1
        visited[x] = 0
        return
    for nx in table[x]:
        DFS(nx)
DFS(0)
print(ans)

Submission status: Wrong Answer

Solution code:
from itertools import permutations
#N = int(input())
N,M = map(int,input().split())
ab=[[]for i in range(N)]
for i in range(M):
    a,b = list(map(int,input().split()))
    ab[a-1].append(b-1)
    ab[b-1].append(a-1)
num = [i+1 for i in range(N-1)]
count = 0
for i in permutations(num):
    flag = True
    if i[0] not in ab[0]:
        continue
    for j in range(1,len(i)-1):
        if i[j+1] not in ab[j]:
            flag = False
    if flag:
        count += 1
print(count)

Submission status: Wrong Answer

Solution code:
import itertools

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

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

num = [i for i in range(1,n)]
ans = 0

for v in itertools.permutations(num):
    print(v)
    if li[0][v[0]] == 0:
        continue
    for i in range(len(v)-1):
        if li[v[i]][v[i+1]] == 0:
            break
        elif i==len(v)-2:
            ans += 1
print(ans-1)

Submission status: Wrong Answer

Solution code:
import itertools

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

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

num = [i for i in range(1,n)]
ans = 0

for v in itertools.permutations(num):
    if li[0][v[0]] == 0:
        continue
    for i in range(len(v)-1):
        if li[v[i]][v[i+1]] == 0:
            break
        elif i==len(v)-2:
            ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
import itertools
N,M = map(int,input().split())
AB = [list(map(int,input().split())) for i in range(M)]
combinations = list(itertools.combinations(AB,N-1))

def check(edges):
    edges_2 = [[] for i in range(N)]
    for e1,e2 in edges:
        edges_2[e1-1].append(e2-1)
        edges_2[e2-1].append(e1-1)
    edges = edges_2
    visited = [False for i in range(N)]
    visited[0] = True
    Q = [(-1,0)]
    print(edges)
    while Q:
        a,b = Q.pop()
        c = 0
        for e in edges[b]:
            if e == a:
                continue
            if visited[e]:
                continue
            c += 1
            if c > 1:
                break
            if not (b,e) in Q and (e,b) in Q:
                Q.append((b,e))
            visited[e] = True
    if False in visited:
        return False
    return True
ans = 0
for edges in combinations:
    if check(edges):
        ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
# https://atcoder.jp/contests/abc054/tasks/abc054_c

import copy
import sys
input = sys.stdin.readline

# 頂点, 辺の数
N, M = map(int, input().split())

# グラフのリスト
# 各頂点からどこの頂点に向かう辺があるかどうかという情報
Graph_list = [[] for i in range(N)]

# 入力
for i in range(M):
    a, b = map(int, input().split())
    a += -1
    b += -1

    # 無向グラフなのでa, b両方
    Graph_list[a].append(b)
    Graph_list[b].append(a)

ans_count = 0           # 正解の経路の数
visited = [False] * N
visited[0] = True

def dfs(i, current, visited):   
    # 頂点をN個通ったら終了処理
    if i >= N-1:

        # 全ての点に到達している場合
        # 順不同で比較
        if all(visited):
            global ans_count
            ans_count += 1
            return 
        return 

    for j in Graph_list[current]:
        if visited[j] == False:
            # 現在地を書き込む
            visited[j] = True
            # 次の点に移動する        
            dfs(i + 1, j, visited)

dfs(0, 0, visited)
print(ans_count)

Submission status: Wrong Answer

Solution code:
# https://atcoder.jp/contests/abc054/tasks/abc054_c

import copy

# 頂点, 辺の数
N, M = map(int, input().split())

# グラフのリスト
# 各頂点からどこの頂点に向かう辺があるかどうかという情報
Graph_list = [[] for i in range(N)]

# 入力
for i in range(M):
    a, b = map(int, input().split())
    a += -1
    b += -1

    # 無向グラフなのでa, b両方
    Graph_list[a].append(b)
    Graph_list[b].append(a)

ans_count = 0
throwgh_point_list = [-1 for i in range(N)]

def dfs(i, current, throwgh_point_list, ans_point_list):   
    # 頂点をN個通ったら終了処理
    if i >= N:
        # すでにカウント済の経路である場合
        if throwgh_point_list in ans_point_list:
            return

        # すでにカウント済ではないかつ全ての点に到達している場合
        # 順不同で比較
        if set(throwgh_point_list) == set(list(range(N))):
            global ans_count
            ans_count += 1
            ans_point_list.append(copy.copy(throwgh_point_list))
            print(throwgh_point_list)
        return

    for j in range(len(Graph_list[current])):
        # 現在地を書き込む
        throwgh_point_list[i] = current

        # 次の点に移動する        
        dfs(i + 1, Graph_list[current][j], throwgh_point_list, ans_point_list)

dfs(0, 0, throwgh_point_list, [])
print(ans_count)

Submission status: Wrong Answer

Solution code:
# https://atcoder.jp/contests/abc054/tasks/abc054_c

import copy

# 頂点, 辺の数
N, M = map(int, input().split())

# グラフのリスト
# 各頂点からどこの頂点に向かう辺があるかどうかという情報
Graph_list = [[] for i in range(N)]

# 入力
for i in range(M):
    a, b = map(int, input().split())
    a += -1
    b += -1

    # 無向グラフなのでa, b両方
    Graph_list[a].append(b)
    Graph_list[b].append(a)

ans_count = 0
throwgh_point_list = [-1 for i in range(N)]

def dfs(i, current, throwgh_point_list, ans_point_list):   
    # 頂点をN個通ったら終了処理
    if i >= N:
        # すでにカウント済の経路である場合
        if throwgh_point_list in ans_point_list:
            print('カウント済み')
            print(throwgh_point_list)
            return

        # すでにカウント済ではないかつ全ての点に到達している場合
        # 順不同で比較
        if set(throwgh_point_list) == set(list(range(N))):
            global ans_count
            ans_count += 1
            ans_point_list.append(copy.copy(throwgh_point_list))
            print(throwgh_point_list)
        return

    for j in range(len(Graph_list[current])):
        # 現在地を書き込む
        throwgh_point_list[i] = current

        # 次の点に移動する        
        dfs(i + 1, Graph_list[current][j], throwgh_point_list, ans_point_list)

dfs(0, 0, throwgh_point_list, [])
print(ans_count)

Submission status: Wrong Answer

Solution code:
import copy
n, m = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(m)]
cnt = 0
fin = set([i + 1 for i in range(n)])
def path(now, edges, past):
    global cnt
    if set(past) == fin:
        cnt += 1
        return
    for i in range(len(edges)):
        if now == edges[i][0] and edges[i][1] not in past:
            now = edges[i][1]
            new_edges = copy.deepcopy(edges)
            new_edges.pop(i)
            past.append(edges[i][1])
            # print("now", now, "edges", edges, "new", new_edges, "past", past, "cnt", cnt)
            path(now, new_edges, past)
        elif now == edges[i][1] and edges[i][0] not in past:
            now = edges[i][0]
            new_edges = copy.deepcopy(edges)
            new_edges.pop(i)
            past.append(edges[i][0])
            # print("now", now, "edges", edges, "new", new_edges, "past", past, "cnt", cnt)


            path(now, new_edges, past)

for i in range(m):
    if ab[i][0] == 1:
        edges = copy.deepcopy(ab)
        edges.pop(i)
        path(ab[i][1], edges, [1, ab[i][1]])
    elif ab[i][1] == 1:
        edges = copy.deepcopy(ab)
        edges.pop(i)
        path(ab[i][0], edges, [1, ab[i][0]])
print(cnt)

Submission status: Wrong Answer

Solution code:
import sys

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

V = []

seen = [False]*N

for i in range(N):
    V.append(set())

for _ in range(M):
    *l, = map(int, input().split())
    
    V[l[0]-1].add(l[1]-1)
    V[l[1]-1].add(l[0]-1)

count = 0
def dfs(node):
    global count
    global seen
    if seen[node]==True:
        return

    seen[node] = True

    #全てのノードを回ったか?
    if not (False in seen):
        count = count + 1
        seen  = [False]*N
        return
    while len(V[node])!=0:
        next_node = V[node].pop()
        dfs(next_node)


dfs(0)
print(count)

Submission status: Wrong Answer

Solution code:
import sys
import copy

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

A = []

V = []

seen = [False]*N

for i in range(N):
    V.append(set())

for _ in range(M):
    *l, = map(int, input().split())
    
    V[l[0]-1].add(l[1]-1)
    V[l[1]-1].add(l[0]-1)

count = 0
def dfs(node):
    global count
    global seen
    if seen[node]==True:
        return

    seen[node] = True

    #全てのノードを回ったか?
    if not (False in seen):
        count = count + 1
        seen  = [False]*N
        return
    while len(V[node])!=0:
        next_node = V[node].pop()
        dfs(next_node)


dfs(0)
print(count)

Submission status: Wrong Answer

Solution code:
def solve():
    def dfs(node, path, rest):
        if rest == 0:
            nonlocal cnt
            cnt += 1
        for next_node in adj[node]:
            if next_node not in path:
                dfs(next_node, path + [next_node], rest - 1)
                
    
    from sys import stdin
    f_i = stdin
    
    N, M = map(int, f_i.readline().split())
    
    adj = [[] for i in range(N)]
    for i in range(M):
        a, b = map(int, f_i.readline().split())
        a -= 1
        b -= 1
        adj[a].append(b)
        adj[b].append(a)
    
    ans = []
    for i in range(N):
        cnt = 0
        dfs(i, [i], N - 1)
        ans.append(cnt)
    
    print(max(ans))

solve()

Submission status: Wrong Answer

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

path_matrix = []

#無向行列の初期化
for n in range(N):
    path_matrix.append([False] * N)

#まず無向グラフを表す行列を作る
for m in range(M):
    a,b = map(int, input().split())
    path_matrix[a-1][b-1] = True
    path_matrix[b-1][a-1] = True
#無向グラフを表す行列はpath_matrix[i][j]iの部分が各頂点でjが他の頂点との繋がりを意味する
#最初はvisited、つまり訪問したことのあるノードはひとつもないので、Falseにする
visited = [False] * N 
#この問題は各頂点をすべて通る方法を調べること
def dfs(now,depth):
    if visited[now]:#もし現在位置が訪問済みなら
        return 0
    if depth == N-1:#もし深さが最大までいったら
        return 1
    
    visited[now] = True#現在位置を訪問済みにする
    total_path = 0
    for i in range(n):
        if path_matrix[now][i]:#もし飛べる先があるのなら、その飛んだ先のノードで今いる位置と深さを更新した上で、もっと掘り下げてみる
            total_path += dfs(i,depth+1) 

    visited[now] = False

    return total_path

print(dfs(0,0))

Submission status: Wrong Answer

Solution code:
import sys
import itertools
import math
input = sys.stdin.readline
#sys.setrecursionlimit(1e9)
N,M = map(int,input().split())

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

graph=[[0]*8 for _ in range(8)]
def dfs(v,visited):
    if sum(visited) == N:
        return 1
    ret =0
    for i in range(N):
        if graph[v][i] == 1 and visited[i] == 0:
            visited[i]=1
            ret += dfs(i,visited)
            visited[i]=0
    return ret
def main():
    """code here"""

    for i in range(M):
        a=ab[i][0]
        b=ab[i][1]
        graph[a-1][b-1]=1
        graph[b-1][a-1]=1

    visited=[0]*N
    visited[0]=1
    print(dfs(0,visited))

Submission status: Wrong Answer

Solution code:
import sys
if sys.platform == 'ios':
	sys.stdin = open('input.txt')
	
n,m = map(int,input().split())

#各頂点のパスはタプルで書く
path = {i+1:[] for i in range(n)}

#各頂点が、どの頂点に繋がっているかのリストを入力しながら作る。
for i in range(m):
	a,b = map(int,input().split())
	path[a].append(b)
	path[b].append(a)

#1は根なので不要。2,3,...,nのリストを作る。
chk = [i for i in range(2,n+1)]
ans = 0

import itertools

#fは辿った頂点の数
#intertools.permurationsで頂点の総並び替えを出す
for way in itertools.permutations(chk):
	print(way)
	now = 1
	f = 0
	
	for j in way:
		if j in path[now]:
			f = f + 1
			now = j
		else:
			break
		
	if f + 1 == n: # +1するのは根の分
		ans = ans + 1

print(ans)

Submission status: Wrong Answer

Solution code:
n,m = map(int, input().split())
ls = [tuple(map(int, input().split())) for _ in range(m)]
neighborls = []
for i in range(1,n+1):
    neighbors = []
    for j in range(1, m+1):
        if (i,j) in ls or (j,i) in ls:
            neighbors.append(j)
    neighborls.append(neighbors)

ans = 0

def main():
    visitedls = []
    dfs(1, visitedls)
    print(ans)
    
        
def dfs(a, visitedls):
    global ans
    visitedls.append(a)
    if len(visitedls) == n:
        ans += 1
    else:
        for i in neighborls[a-1]:
            if i not in visitedls:
                dfs(i, visitedls)
    visitedls.remove(a)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
n,m = map(int, input().split())
ls = [tuple(map(int, input().split())) for _ in range(m)]
neighborls = []
for i in range(1,n+1):
    neighbors = []
    for j in range(1, m+1):
        if (i,j) in ls or (j,i) in ls:
            neighbors.append(j)
    neighborls.append(neighbors)

ans = 0

def main():
    visitedls = []
    dfs(1, visitedls)
    print(ans)
    
        
def dfs(a, visitedls):
    global ans
    visitedls.append(a)
    if len(visitedls) == n:
        ans += 1
    else:
        for i in range(1,n+1):
            if i not in visitedls and i in neighborls[a-1]:
                dfs(i, visitedls)
    visitedls.remove(a)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
n,m = map(int, input().split())
ls = [tuple(map(int, input().split())) for _ in range(m)]
neighborls = []
for i in range(1,n+1):
    neighbors = []
    for j in range(1, m+1):
        if (i,j) in ls or (j,i) in ls:
            neighbors.append(j)
    neighborls.append(neighbors)

ans = 0

def main():
    global ans
    visitedls = [1]
    ans = dfs(1, visitedls, ans)

    print(ans)
    
        
def dfs(a, visitedls, ans):
    if len(visitedls) == n:
        ans += 1
    else:
        for i in range(1,n+1):
            if i not in visitedls and i in neighborls[a-1]:
                visitedls.append(i)
                ans = dfs(i, visitedls, ans)
                visitedls.remove(i)
    return ans

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
n,m = map(int, input().split())
ls = [tuple(map(int, input().split())) for _ in range(m)]
neighborls = []
for i in range(1,n+1):
    neighbors = []
    for j in range(1, m+1):
        if (i,j) in ls or (j,i) in ls:
            neighbors.append(j)
    neighborls.append(neighbors)

ans = 0

def main():
    global ans
    visitedls = [1]
    ans = dfs(1, visitedls, ans)

    print(ans)
    
        
def dfs(a, visitedls, ans):
    if len(visitedls) == n:
        ans += 1
    for i in range(1,n+1):
        if i not in visitedls and i in neighborls[a-1]:
            visitedls.append(i)
            ans = dfs(i, visitedls, ans)
            visitedls.remove(i)
    return ans


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
n,m = map(int, input().split())
ls = [tuple(map(int, input().split())) for _ in range(m)]
neighborls = []
for i in range(1,n+1):
    neighbors = []
    for j in range(1, m+1):
        if (i,j) in ls or (j,i) in ls:
            neighbors.append(j)
    neighborls.append(neighbors)

ans = 0

def main():
    global ans
    visitedls = [1]
    ans = dfs(1, visitedls, ans)

    print(ans)
    
        
def dfs(a, visitedls, ans):
    if len(visitedls) == n:
        ans += 1
        return ans
    for i in range(1,n+1):
        if i not in visitedls and i in neighborls[a-1]:
            visitedls.append(i)
            ans = dfs(i, visitedls, ans)
            visitedls.remove(i)
    return ans


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
n,m = map(int, input().split())
ls = [tuple(map(int, input().split())) for _ in range(m)]
neighborls = []
for i in range(1,n+1):
    neighbors = []
    for j in range(1, m+1):
        if (i,j) in ls or (j,i) in ls:
            neighbors.append(j)
    neighborls.append(neighbors)

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

    print(ans)
    
        
def dfs(a, visitedls, ans):
    if len(visitedls) == n:
        ans += 1
        return ans
    for i in range(1,n+1):
        if i not in visitedls and i in neighborls[a-1]:
            visitedls.append(i)
            ans = dfs(i, visitedls, ans)
            visitedls.remove(i)
    return ans


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import queue
def dfs(cnt):
    while True:
        if not q.empty():
            item = q.get()
            if len(item) == N and len(set(item)) == N:
                cnt += 1
            else:
                for a, b in lis:
                    if a in item and b in item:
                        continue
                    elif a == item[-1] and b not in item:
                        item.append(b)
                        q.put(item)
                        break
                    elif b == item[-1] and a not in item:
                        item.append(a)
                        q.put(item)
                        break
        else:
            return cnt

N, M = map(int, input().split())
lis = [list(map(int, input().split())) for _ in range(M)]
q = queue.Queue()
cnt = 0
for a, b in lis:
    if a == 1:
        q.put([a,b])
print(dfs(cnt))

Submission status: Wrong Answer

Solution code:
import queue
def dfs(cnt):
    while True:
        if not q.empty():
            item = q.get()
            if len(item) == N:
                cnt += 1
            else:
                for a, b in lis:
                    if a in item and b in item:
                        continue
                    elif a == item[-1] and b not in item:
                        item.append(b)
                        q.put(item)
                        break
                    elif b == item[-1] and a not in item:
                        item.append(a)
                        q.put(item)
                        break
        else:
            return cnt

N, M = map(int, input().split())
lis = [list(map(int, input().split())) for _ in range(M)]
q = queue.Queue()
cnt = 0
for a, b in lis:
    if a == 1:
        q.put([a,b])
print(dfs(cnt))

Submission status: Wrong Answer

Solution code:
def get_unique_list(ans):
    seen = []
    return [x for x in ans if x not in seen and not seen.append(x)]

import queue
N, M = map(int, input().split())
lis = [list(map(int, input().split())) for _ in range(M)]
q = queue.Queue()
for a, b in lis:
    if a == 1:
        q.put([a, b])
ans = []
while True:
    if not q.empty():
        item = q.get()
    else:
        break

    if len(item) == N:
        ans.append(item)
    else:
        for a, b in lis:
            if a in item and b in item:
                continue
            elif a == item[-1]:
                item.append(b)
                q.put(item)
            elif b == item[-1]:
                item.append(a)
                q.put(item)
print(len(get_unique_list(ans)))

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
import itertools


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

res = 0
if M < N - 1:
    print(res)
else:
    for path in itertools.permutations(edges, N - 1):
        vertex = [True] * N
        v = 0
        for edge in path:
            if v in edge:
                nv = edge[0] if v == edge[1] else edge[1]
                if vertex[nv]:
                    vertex[nv] = False
                    v = nv
                    continue
            break
        else:
            res += 1
    print(res)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
G = [[] for i in range(N+1)]
for i in range(M):
    a,b = map(int,input().split())
    G[a].append(b)
    G[b].append(a)
l = [i for i in range(2,N+1)]
import itertools
ans = 0
for v in itertools.permutations(l):
    v = list(v)
    s = 1
    t = 1
    while v:
        s = t
        t = v.pop(0)
        if t not in G[s]:
            break
    if len(v) == 0:
        ans += 1
print(ans)

Submission status: Wrong Answer

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

if m < n -1:
    print(0)
    exit()

paths = []
start = 1

still_possible = True
while still_possible:
    passed = [1]
    current = start
    for i in range(1, n):
        for e in edges:
            if e[0] == current and e[1] != current and not (e[1] in passed):
                for path in paths:
                    if path[i] == e[1]:
                        break
                else:
                    passed.append(e[1])
                    current = e[1]
                    break
            elif e[0] != current and e[1] == current and not (e[0] in passed):
                for path in paths:
                    if path[i] == e[0]:
                        break
                else:
                    passed.append(e[0])
                    current = e[0]
                    break        
        else: # if e all in edges are not accepted
            if passed == [1]:
                still_possible = False
            break

    if len(passed) == n:
        paths.append(passed)

print(len(paths))

Submission status: Wrong Answer

Solution code:
from sys import stdin
memo = {}


def dfs(e, ans, done, N, graph):
    if (1 << N) - 1 == done:
        ans += 1
        return ans
    key = (e, done)
    if key in memo:
        return memo[key]
    for s in graph[e]:
        if done >> s & 1:
            continue
        done ^= 1 << s
        ans = dfs(s, ans, done, N, graph)
        done ^= 1 << s
    memo[key] = ans
    return ans


def main():
    lines = stdin.readlines()
    N, M = map(int, lines[0].split())
    graph = [[] for i in range(N)]
    for i in range(1, M + 1):
        a, b = map(lambda x: int(x) - 1, lines[i].split())
        # 0-based indexing
        graph[a].append(b)
        graph[b].append(a)
    ans = 0
    print(dfs(0, ans, 1, N, graph))
    return


main()

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
G = {}
for _ in range(M):
    a,b = map(int,input().split())
    if a not in G:
        G[a] = []
    G[a].append(b)
    if b not in G:
        G[b] = []
    G[b].append(a)
hist = [0 for _ in range(N+1)]
hist[1] = 1
stack = [(1,0,1)]
cnt = 0
while stack:
    cur = stack.pop()
    hist[cur[0]] = 1
    flag = 0
    for y in G[cur[0]]:
        if hist[y]==0:
            flag += 1
            stack.append((y,cur[0],flag))
    if flag==0:
        if sum(hist)==N:
            cnt += 1
        hist[cur[0]] = 0
        if cur[2]==1:
            hist[cur[1]]=0
print(cnt)

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
G = {}
for _ in range(M):
    a,b = map(int,input().split())
    if a not in G:
        G[a] = []
    G[a].append(b)
    if b not in G:
        G[b] = []
    G[b].append(a)
hist = [0 for _ in range(N+1)]
hist[1] = 1
stack = []
cnt = 0
for x in G[1]:
    stack.append((x,1,1))
    hist[x] = 1
    while stack:
        cur = stack.pop()
        flag = 0
        for y in G[cur[0]]:
            if hist[y]==0:
                flag += 1
                stack.append((y,cur[0],flag))
                hist[y]=1
        if flag==0:
            if sum(hist)==N:
                cnt += 1
            hist[cur[0]] = 0
            if cur[2]==1:
                hist[cur[1]]=0
print(cnt)

Submission status: Wrong Answer

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

S = []
count = 0

visit[1-1]=1
S.append(1)
while S:
  v = S[0]
  S.pop(0)
  if all(visit):
    count += 1
  for next in G[v-1]:
    if not visit[next-1]:
      visit[next-1]=1
      S.append(next)
      
print(count)

Submission status: Wrong Answer

Solution code:
import itertools
import collections

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

a = [list(sorted(map(int, input().split()))) for i in range(m)]
a.sort()

cnt = 0

for i in itertools.permutations(range(2, n + 1), (n - 1)):
    li = [1] + list(i)
    for edge in zip(li, li[1:]):
        print(edge)
    if sum(list(sorted(edge)) in a for edge in zip(li, li[1:])) == n - 1:
       cnt += 1

print(cnt)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
from collections import defaultdict


def c():
    n, m = map(int, input().split())
    graph = defaultdict(list)
    for i in range(m):
        a, b = map(int, input().split())
        graph[a].append(b)
        graph[b].append(a)
    stack = []
    count = 0

    stack.append((1, set()))

    while stack:
        val, visited = stack.pop()
        visited.add(val)
        if len(visited) == m:
            count += 1
            continue

        for g in graph[val]:
            if g not in visited:
                stack.append((g, set(visited)))

    print(count)


if __name__ == '__main__':
    c()

Submission status: Wrong Answer

Solution code:
from collections import defaultdict


def c():
    n, m = map(int, input().split())
    graph = defaultdict(list)
    a1 = None
    for i in range(m):
        a, b = map(int, input().split())
        if i == 0:
            a1 = a
        graph[a].append(b)
        graph[b].append(a)
    stack = []
    count = 0

    if a1:
        stack.append((a1, set()))

    while stack:
        val, visited = stack.pop()
        visited.add(val)
        if len(visited) == m:
            count += 1
            continue

        for g in graph[val]:
            if g not in visited:
                stack.append((g, set(visited)))

    print(count)


if __name__ == '__main__':
    c()

Submission status: Wrong Answer

Solution code:
import itertools

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

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

per = list(itertools.permutations(range(N)))

count = 0

for x in per:
    if x[0] != 1:
        continue
    det = 0
    for k in range(N-1):
        if x[k+1] in con[x[k]]:
            continue
        else:
            det = -1
            break
    if det == 0:
        count += 1

print(count)