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:

class Graph():
    def __init__(self):
        """ ノードのつながりを辞書型で表現する """
        self.adjacency_dict = {}
    
    def add_vertex(self, v):
        """ ノードを追加する """
        self.adjacency_dict[v] = []
    def add_edge(self, v1, v2):
        """ ノード同士をつなぐ。"""
        # 無向グラフの場合は双方向。もし有向グラフなら片側のみ。
        self.adjacency_dict[v1].append(v2)
        self.adjacency_dict[v2].append(v1)
    def remove_edge(self, v1, v2):
        """ ノード同士のつながりを削除する。"""
        self.adjacency_dict[v1].remove(v2)
        self.adjacency_dict[v2].remove(v1)
    def remove_vertex(self,v):
        """ ノードを削除する。"""
        while self.adjacency_dict[v] != []:
            adjacent_vertex = self.adjacency_dict[v][-1]
            self.remove_edge(v, adjacent_vertex)
        del self.adjacency_dict[v]
    
    def print_graph(self):
        print(self.adjacency_dict)

    def _init_internal_graph(self, graph_dict):
        self.adjacency_dict = graph_dict
    
    def get_edge(self, v):
        """ 指定されたノードに関するエッジを返す。"""
        return self.adjacency_dict[v]

def dprint(*args):
  if len(args)==1:
    print(args[0])
  else:
    print(args)

debug = False
if debug:
  g = Graph()
  # N,M = [7, 7]
  # g._init_internal_graph({0: [2], 1: [6], 2: [0, 3], 3: [2, 4, 5], 4: [3, 5], 5: [3, 4, 6], 6: [1, 5]})
  
  N,M = [3, 3]
  g._init_internal_graph({0: [1, 2], 1: [0, 2], 2: [0, 1]})
else:
  N, M = map(int, input().split())
  g = Graph()
  dprint(N,M)

  for n in range(N):
    g.add_vertex(n)

  # 0-origin    
  for m in range(M):
      v1,v2 = list(map(int, input().split()))
      g.add_edge(v1-1,v2-1)                     

# g.print_graph()

seen = [False] * N
count = 0

def dfs(node, depth):
    dprint(node,depth)        
    if seen[node]:
        return 0
    if depth == N - 1:
        dprint('count-up',seen)
        return 1

    seen[node] = True
    dprint(seen)
    
    total_paths = 0
    for next_node in g.get_edge(node):
      total_paths += dfs(next_node, depth + 1)

    # seenを未到達にして次へ
    seen[node] = False

    return total_paths

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

Submission status: Wrong Answer

Solution code:
import sys
import itertools
n,m=map(int,input().split())
ab=[]
for _ in range(m):
    ab.append(list(map(int,input().split())))

lis=[i for i in range(1,n+1)]
per_lis = itertools.permutations(lis) 

ans=0
for one_case in per_lis:
    if one_case[0]==1:
        tmp=0
        for j in range(n-1):
            for num in ab:
                if one_case[j]==num[0] and one_case[j+1]==num[1]:
                    tmp+=1
                    break        
        if tmp==n-1:
            ans+=1

print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
N,M = list(map(int, input().split()))
adj_list = defaultdict(list)

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


res = 0
def dfs(node, visited):
  global res

  if len(visited) == N-1:
    res += 1
    return
  visited.append(node)

  for nei in adj_list[node]:
    if nei not in visited:
      dfs(nei, visited)

for node in adj_list[1]:
  dfs(node, [1])

print(res)

Submission status: Wrong Answer

Solution code:
import sys
from collections import defaultdict

input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)


def main():

    N, M = map(int, input().split())
    G = defaultdict(lambda: [])

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

    # print(G)

    def dfs(v, is_visited):
        is_visited[v] = True
        if sum(is_visited) == N:
            return 1
        ans = 0
        for u in G[v]:
            if is_visited[u] == True:
                continue
            ans += dfs(u, is_visited)
            is_visited[u] = False

        return ans

    is_visited = [False] * N

    print(dfs(1, is_visited))


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import itertools
n,m=map(int,input().split())
l=[list(map(int,input().split())) for i in range(m)]
s=list(itertools.permutations(range(1,n+1)))
count=0
for lis in s:
    flag=False
    if lis[0]==1:
        if all([lis[i],lis[i+1]] in l for i in range(n-1)):
            count+=1
        elif all([lis[i+1],lis[i]] in l for i in range(n-1)):
            count+=1
print(count)

Submission status: Wrong Answer

Solution code:
import itertools

N,M = map(int, input().split())
path = [[False] * N for x in range(N)]

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

count = 0
for j in itertools.permutations(range(N),M):
    if j[0] != 1:
        continue
    for k in range(M-1):
        if k == M-2:
            count += 1
            break
        if path[j[k]][j[k+1]] == 'False':
            break
print(count)

Submission status: Wrong Answer

Solution code:
from itertools import permutations
n,m = map(int,input().split())

rel_t = [[False for i in range(n)] for j in range(n)]

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

cnt=0
n_list = [i for i in range(n)]
for l in permutations(n_list,len(n_list)):
    if(l[0]!=1):
        continue
    judge=[rel_t[l[i]][l[i+1]] for i in range(n-1)]
    if all(judge):
        cnt+=1

print(cnt)

Submission status: Wrong Answer

Solution code:
from itertools import permutations
def main():
    n, m = map(int, input().split())
    path = []
    for _ in range(m):
        path.append(tuple(map(int, input().split())))

    nodes = [i for i in range(2, n + 1)]
    routes = permutations(nodes, n-1)

    r = 0
    for route in routes:
        route = list(route)
        route.insert(0,1)
        for i1 in range(n-1):
            if (route[i1], route[i1+1]) not in path:
                if (route[i1+1], route[i1]) not in path:
                    print("do break")
                    break
        else:
            r += 1
    print(r)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

import itertools
li = [i for i in range(1,n)]
count = 0
for p in itertools.permutations(li, len(li)):
    for i in range(len(p) -1):
        if l[p[i]][p[i + 1]] == 0:
            continue
        count += 1

print(count)

Submission status: Wrong Answer

Solution code:
def DFS(i):
    global ans
    visited[i] = 0
    # print(i, visited)
    if sum(visited) == 0:
        ans += 1
        return 1
    cnt = 0
    for j in graf[i]:
        if visited[j] == 1:
            cnt += DFS(j)
    visited[i] = 1
    return cnt

import sys
sys.setrecursionlimit(200000)
n, m = map(int, input().split())
graf = [[] for _ in range(n)]
for i in range(m):
    a, b = map(int, input().split())
    graf[a-1].append(b-1)
    graf[b-1].append(a-1)

now = 0
visited = [1 for _ in range(n)]
visited[now] = 0
# print(graf)
ans = 0
for i in graf[now]:
    DFS(i)
print(ans)

Submission status: Wrong Answer

Solution code:
def DFS(i):
    visited[i] = 0
    # print(i, visited)
    if sum(visited) == 0:
        return 1
    cnt = 0
    for j in graf[i]:
        if visited[j] == 1:
            cnt += DFS(j)
    visited[i] = 1
    return cnt

import sys
sys.setrecursionlimit(200000)
n, m = map(int, input().split())
graf = [[] for _ in range(n)]
for i in range(m):
    a, b = map(int, input().split())
    graf[a-1].append(b-1)
    graf[b-1].append(a-1)

now = 0
visited = [1 for _ in range(n)]
visited[now] = 0
# print(graf)
ans = 0
for i in graf[now]:
    ans += DFS(i)
print(ans)

Submission status: Wrong Answer

Solution code:
import itertools


def main():
    # 入力
    n, m = map(int, input().split())

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

    ablist.sort()
    itertools.permutations(ablist)

    permutations_lis = itertools.permutations(ablist)

    count = 0
    for perlist in permutations_lis:
        if perlist[0][0] != 1:
            break

        i_current = perlist[0][1]
        i_already = [1, perlist[0][1]]

        for per in perlist[1:]:
            if per[0] == i_current:
                if per[1] in i_already:
                    break

                i_current = per[1]
                i_already.append(per[1])
            elif per[1] == i_current:
                if per[0] in i_already:
                    break
                i_current = per[0]
                i_already.append(per[0])
            else:
                break

        if len(i_already) == n:
            count += 1

    print(count)


main()

Submission status: Wrong Answer

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

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

def search_indecies(index, remainGraph, path):
    indecies = []
    for i, x in enumerate(remainGraph):
        if x[0] == index or x[1] == index:
            others = get_other_num(x, index)
            if all([x[0] != others and x[1] != others for x in path]):
                indecies.append(i)
    return indecies

def search_iterative(currentGraph, currentNodeNum, currentIndex, path):
    prev = currentNodeNum

    currentNode = currentGraph.pop(currentIndex)
    path.append(currentNode)
    if len(path) == n - 1:
        return 1
    nextNum = get_other_num(currentNode, prev)

    nextCandidateIndecies = search_indecies(nextNum, currentGraph, path)

    pathList = 0
    for nextIndex in nextCandidateIndecies:
        c = search_iterative(currentGraph[:], nextNum, nextIndex, path[:])
        pathList += c
        return pathList

    return 0

def get_other_num(currentNode, prev):
    return currentNode[0] if currentNode[1] == prev else currentNode[1]


startIndecies = search_indecies(1, graphs, [])

resuts = 0
for startIndex in startIndecies:
    path = []
    resuts += search_iterative(graphs[:], 1, startIndex, path)
print(resuts)

Submission status: Wrong Answer

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

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

def search_indecies(index, remainGraph):
    indecies = []
    for i, x in enumerate(remainGraph):

        if x[0] == index or x[1] == index:
            indecies.append(i)
    return indecies

def search_iterative(currentGraph, currentNodeNum, currentIndex, path):
    prev = currentNodeNum

    currentNode = currentGraph.pop(currentIndex)
    path.append(currentNode)
    if len(path) == n - 1:
        return [path]
    nextNum = get_other_num(currentNode, prev)

    nextCandidateIndecies = search_indecies(nextNum, currentGraph)

    pathList = []
    for nextIndex in nextCandidateIndecies:
        nextNum = get_other_num(currentGraph[nextIndex], nextNum)
        c = search_iterative(currentGraph[:], nextNum, nextIndex, path[:])
        pathList.append(c)
        return pathList

    return []

def get_other_num(currentNode, prev):
    return currentNode[0] if currentNode[1] == prev else currentNode[1]


startIndecies = search_indecies(1, graphs)

resuts = []
for startIndex in startIndecies:
    path = []
    resuts.append(search_iterative(graphs[:], 1, startIndex, path))

print(len(resuts))

Submission status: Wrong Answer

Solution code:
## coding: UTF-8
from itertools import permutations

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

graph = []
for i in range(M):
    graph.append(list(map(int, input().split())))
#print(graph)

point = [i+1 for i in range(1,N)]
root = list(permutations(point, N-1))
#print(root)

counter = 0
for i in range(len(root)):
    pairs = []
    pairs.append([1, root[i][0]])
    #print(root[i])
    for j in range(N-2):
        pairs.append([root[i][j], root[i][j+1]])
    #print('i:{},root[i]:{},pairs:{}'.format(i, root[i], pairs))
    status = True
    for k in range(N-2):
        if(not(pairs[k] in graph)):
            status = False
    #print('status:{}'.format(status))
    if(status):
        counter += 1
print(counter)

'''
counter = 0
for i in range(len(root)):
    print('i:{},root[i]:{}'.format(i, root[i]))
    spot = 1
    for j in range(N-1):
        #勧めるなら進む
        n = root[i][j]
        print('spot:{}, n:{}'.format(spot, n))
        if(spot < n):
            if([spot, n] in graph):
                spot = n
            else:
                continue
        elif(spot > n):
            if([n, spot] in graph):
                spot = n
            else:
                continue
        else:
            continue
'''

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())  #頂点, 辺
g = [[] for _ in range(N)]  #iはjと繋がっている
for _ in range(M):
    a, b = map(int, input().split())
    g[a-1].append(b-1)
    g[b-1].append(a-1)
print(g)

#1度通った頂点をTrueにする
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)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
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
  if (ans_list[0]==1) and (ans_list.count(2)==(n-2)):
    ans+=1
  ans_list=[0]*n
  
print(ans)

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())  #頂点, 辺
g = [[] for _ in range(N)]  #iはjと繋がっている
for i 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

import sys
sys.setrecursionlimit(10 ** 8)
def dfs(i):
    cnt = 0
    is_checked[i] = True
    for j in g[i]:
        if not(is_checked[j]):
            dfs(j)
        if not(False in is_checked):
            cnt += 1
    return cnt
            
ans = dfs(0)
print(ans)

Submission status: Wrong Answer

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

def solve(s,p,dp):
  global res
  if s == (1<<n)-1 and dp[p-1] == 0:
    return 1    
  if dp[p-1] == 1:
    return 0
  dp[p-1]=1
  for u in graph[p-1]:
    res += solve(s|(1<<(u-1)),u,dp)            
  return res

dp=[0 for _ in range(n)]
print(solve(1,1,dp))

Submission status: Wrong Answer

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

def dfs(v, used,cnt):
    used[v] = 1
    if all(used):
        cnt+=1
    for nv in es[v]:
        if used[nv]:
            continue
        dfs(nv, used,cnt)
    used[v] = 0


used = [0] * N
cnt = 0
dfs(0, used,cnt)
print(cnt)

Submission status: Wrong Answer

Solution code:
from itertools import permutations
def main():
    n, m = map(int, input().split())

    edge = set()
    for _ in range(m):
        a, b = map(lambda x: int(x)-1, input().split())
        edge.add((a, b))  
        edge.add((b, a))

    #全ノード間に辺が張っていると仮定する
    #このとき全てのノードを廻る順番は順列の数だけある
    #ここから条件を絞って数えるべきものを数えていく 

    #ノードを廻る順を構成する 
    node_num = []
    for i in range(n):
        node_num.append(i)
    
    cnt = 0
    for p in permutations(node_num):
        #数える経路は始点が0である
        print(p)
        if p[0] == 0:
            #この順列pの通りに辿れるように辺が張っているならこの経路は数えるべき経路である
            flag = True
            for i in range(n-1):
                #この順列のあるノード間に辺が存在しないならこの経路は不可能
                if (p[i], p[i+1]) not in edge:
                    falg = False
            if flag:
                cnt += 1 
    print(cnt) 
main()

Submission status: Wrong Answer

Solution code:
n, m = [int(x) for x in input().split()] # n: 頂点, m: 辺
line = [ tuple( int(x)-1 for x in input().split() ) for _ in range(m) ]

matrix = [ [False]*n for _ in range(n) ] # n x n 行列
for a, b in line:
    matrix[a][b] = True
    matrix[b][a] = True

visited = [False]*n

def dfs(point, depth):
    if visited[point]:
        return 0
    visited[point] = True

    if depth == n - 1:
        return 1

    total = 0
    for i, np in enumerate(matrix[point]):
        if np:
            total += dfs(i, depth + 1)

    return total

print(dfs(0, 1))

Submission status: Wrong Answer

Solution code:
def main():
    import sys
    from itertools import permutations
    # readline = sys.stdin.buffer.readline
    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()

Submission status: Wrong Answer

Solution code:
import sys
import os
import math

ii = lambda: int(sys.stdin.buffer.readline().rstrip())
il = lambda: list(map(int, sys.stdin.buffer.readline().split()))
fl = lambda: list(map(float, sys.stdin.buffer.readline().split()))
iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)]

iss = lambda: sys.stdin.buffer.readline().decode().rstrip()
sl = lambda: list(map(str, sys.stdin.buffer.readline().decode().split()))
isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)]

MOD = 10 ** 9 + 7


def dfs(g, n, r):
    r[n - 1] = True
    for m in g[n]:
        if r[m - 1]: continue
        dfs(g, m, r)


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    N, M = il()
    g = {n + 1: [] for n in range(N)}
    for m in range(M):
        a, b = il()
        g[a].append(b)
        g[b].append(a)

    ret = 0
    for n in g[1]:
        r = [False] * N
        r[0] = True
        dfs(g, n, r)
        if all(r): ret += 1

    print(ret)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
import os
import math

ii = lambda: int(sys.stdin.buffer.readline().rstrip())
il = lambda: list(map(int, sys.stdin.buffer.readline().split()))
fl = lambda: list(map(float, sys.stdin.buffer.readline().split()))
iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)]

iss = lambda: sys.stdin.buffer.readline().decode().rstrip()
sl = lambda: list(map(str, sys.stdin.buffer.readline().decode().split()))
isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)]

MOD = 10 ** 9 + 7


def dfs(g, n, r):
    if r[n - 1]: return
    r[n - 1] = True
    for m in g[n]:
        dfs(g, m, r)


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    N, M = il()
    g = {n + 1: [] for n in range(N)}
    for m in range(M):
        a, b = il()
        g[a].append(b)
        g[b].append(a)

    ret = 0
    for n in g[1]:
        r = [False] * N
        r[0] = True
        dfs(g, n, r)
        if all(r): ret += 1

    print(ret)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import copy
class Node:
    def __init__(self):
        self.adjacentnode=[]

def search(lista,nodet):
    global count
    global m
    if len(lista)==m:
            count+=1
            return True
    for a in nodet[lista[-1]].adjacentnode:
        if a not in lista:
                newlist=copy.copy(lista)
                newlist.append(a)
                search(newlist,nodet)
    
n,m=map(int,input().split()) #n is node,m is edge 
count=0
listsrch=[]
listsrch.append(0)
nodelist=[Node() for a in range(n)]

for t in range(m):
    a,b=map(int,input().split())
    nodelist[a-1].adjacentnode.append(b-1)
    nodelist[b-1].adjacentnode.append(a-1)
search(listsrch,nodelist)
print(count)

Submission status: Wrong Answer

Solution code:
import itertools

n,m = [int(i) for i in input().split()]

chk = [[0]*n for i in range(n)]
for i in range(m):
  a,b = [int(i) for i in input().split()]
  chk[a-1][b-1] = 1
  chk[b-1][a-1] = 1

ans = 0

for i in itertools.permutations(range(n),n):
  if i[0] == 1:
    for j in range(n):
      if j == n-1:
        ans += 1
        break
      if chk[i[j]][i[j+1]] != 1:
        break
print(ans)

Submission status: Wrong Answer

Solution code:
import itertools

n,m = [int(i) for i in input().split()]

chk = [[0]*8 for i in range(8)]
for i in range(m):
  a,b = [int(i) for i in input().split()]
  chk[a-1][b-1] = 1
  chk[b-1][a-1] = 1

ans = 0

for i in itertools.permutations(range(n),n):
  if i[0] == 1:
    for j in range(n):
      if j == n-1:
        ans += 1
        break
      if chk[i[j]][i[j+1]] != 1:
        break
print(ans)

Submission status: Wrong Answer

Solution code:
import itertools

n,m = [int(i) for i in input().split()]

chk = [[0]*n for i in range(n)]
for i in range(m):
  a,b = [int(i) for i in input().split()]
  chk[a-1][b-1] = 1
  chk[b-1][a-1] = 1

ans = 0

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

Submission status: Wrong Answer

Solution code:
import itertools

n,m = [int(i) for i in input().split()]

chk = [[0]*9 for i in range(9)]
for i in range(m):
  a,b = [int(i) for i in input().split()]
  chk[a-1][b-1] = 1
  chk[b-1][a-1] = 1

ans = 0

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

Submission status: Wrong Answer

Solution code:
import itertools

n,m = [int(i) for i in input().split()]

chk = [[0]*8 for i in range(8)]
for i in range(m):
  a,b = [int(i) for i in input().split()]
  chk[a-1][b-1] = 1
  chk[b-1][a-1] = 1

ans = 0

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

Submission status: Wrong Answer

Solution code:
import itertools

n,m = [int(i) for i in input().split()]

chk = [[0]*8 for i in range(8)]
for i in range(m):
  a,b = [int(i) for i in input().split()]
  chk[a-1][b-1] = 1
  chk[b-1][a-1] = 1

ans = 0

for i in itertools.permutations(range(n),n):
  if i[0] == 1:
    for j in range(n):
      if j == n-1:
        ans += 1
        break
      if chk[i[j]][i[j+1]] == 0:
        break

Submission status: Wrong Answer

Solution code:
from itertools import permutations


def main():
    n, m = map(int, input().split())
    graph = [[] for _ in range(n)]
    for _ in range(m):
        a, b = map(lambda x: int(x) - 1, input().split())
        graph[a].append(b)
        graph[b].append(a)
    answer = 0
    for p in permutations([i for i in range(n)]):
        if p[0] != 1:
            continue
        if all(p[i] in graph[p[i - 1]] for i in range(1, n)):
            answer += 1
    print(answer)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from itertools import permutations
n, m = map(int, input().split())
G = [[0]*n for _ in range(n)]
for _ in range(m):
  a, b = map(int, input().split())
  a -= 1
  b -= 1
  G[a][b] = 1
  G[b][a] = 1
ans = 0
for l in permutations(range(n)):
  if l[0] != 1:
    continue
  for i in range(n-1):
    if not G[l[i]][l[i+1]]:
      break
  else:
    ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
a=[]

for i in range(m):
    ai,bi=map(int,input().split())
    a.append([ai,bi])

ni=[0]*n
    
def pathm(n,a,bi,pcnt,ni):
    if n==1:
        pcnt=pcnt+1
#        print("2:","n:",n,"bi:",bi,"pcnt:",pcnt)
        return pcnt
    else:
        n=n-1
        for mm in range(m):
            if a[mm][0]==bi and ni[a[mm][1]-1]==0:
#            if a[mm][0]==bi :
                ni[a[mm][1]-1]=1
#                print("1:","n:",n,"mm:",mm,"a[mm][1]:",a[mm][1],"pcnt:",pcnt)
                pcnt=pathm(n,a,a[mm][1],pcnt,ni)
            if a[mm][1]==bi  and ni[a[mm][0]-1]==0 :
                ni[a[mm][0]-1]=1
#                ni[mm]=1
#                print("1:","n:",n,"mm:",mm,"a[mm][0]:",a[mm][0],"pcnt:",pcnt)
                pcnt=pathm(n,a,a[mm][0],pcnt,ni)
        return pcnt       
                
pcnt=0
pcnt1=pathm(n,a,1,pcnt,ni)
print(pcnt1)

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
a=[]

for i in range(m):
    ai,bi=map(int,input().split())
    a.append([ai,bi])

ni=[0]*n
    
def pathm(n,a,bi,pcnt,ni):
    if n==1:
        pcnt=pcnt+1
        print("2:","n:",n,"bi:",bi,"pcnt:",pcnt)
        return pcnt
    else:
        n=n-1
        for mm in range(m):
            if a[mm][0]==bi and ni[a[mm][1]-1]==0:
#            if a[mm][0]==bi :
                ni[a[mm][1]-1]=1
                print("1:","n:",n,"mm:",mm,"a[mm][1]:",a[mm][1],"pcnt:",pcnt)
                pcnt=pathm(n,a,a[mm][1],pcnt,ni)
            if a[mm][1]==bi  and ni[a[mm][0]-1]==0 :
                ni[a[mm][0]-1]=1
#                ni[mm]=1
                print("1:","n:",n,"mm:",mm,"a[mm][0]:",a[mm][0],"pcnt:",pcnt)
                pcnt=pathm(n,a,a[mm][0],pcnt,ni)
        return pcnt       
                
pcnt=0
pcnt1=pathm(n,a,1,pcnt,ni)
print(pcnt1)

Submission status: Wrong Answer

Solution code:
import itertools
import sys
N,M=map(int,input().split())
dic={}
for _ in range(M):
    a,b=map(int,input().split())
    if(a in dic.keys()):
        if((b in dic[a])==False):
            dic[a].append(b)
    else:
        dic[a]=[b]
    if(b in dic.keys()):
        if((a in dic.values())==False):
            dic[b].append(a)
    else:
        dic[b]=[a]

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

node=[i for i in range(N)]
ans=0
strokes=itertools.permutations(node,M)

def judge(A,B):
    values=dic[A]
    if(B in values):
        return True
    else:
        return False

for stroke in strokes:
    stroke=list(stroke)
    if(stroke[0]==0):
        pre=stroke.pop(0) + 1
        for s in stroke:
            if(judge(pre,s+1)==False):
                break
            pre=s+1
        else:
            ans+=1
    
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
# dfs, check path len, count paths                                                                                                                           
# test = 2                                                                                                                                                   
n, m = map(int, input().split())
edges = [map(int, input().split()) for i in range(m)]
graph = defaultdict(list)
for k,v in edges:
    graph[k].append(v)
    graph[v].append(k)

cnt = 0
# dfs                                                                                                                                                        
def dfs(node, visited):
    global cnt
    if node in visited:
        return None
    elif len(visited) + 1 == m:
        cnt += 1
        return None
    else:
        for v in graph[node]:
            dfs(v, visited+[node])
dfs(1, [])
print(cnt)

Submission status: Wrong Answer

Solution code:
import sys
input=sys.stdin.readline
#グラフの連結成分を調べる
def Graph(ab):
    G=[[] for i in range(n)]
    for a,b in ab:
        G[a-1].append(b)
        G[b-1].append(a)
    return G
from collections import deque
def dfs(G,v,p,n):
    q=deque()
    q.append((v,p,1,0))
    log=[0]*n
    log[v-1]=1
    ans=0
    while q:
        V,P,cnt,S=q.pop()
        if S==0:
            #下に遷移していくときの処理
            q.append((V,P,cnt,1))
            for new_v in G[V-1]:
                if new_v==P:continue
                if log[new_v-1]:continue
                log[V-1]=1
                if cnt==n-1:
                    ans+=1
                    continue
                q.append((new_v,V,cnt+1,0))
        else:
            log[P-1]=0
    return ans

n,m=map(int,input().split())
ab=[list(map(int,input().split())) for i in range(m)]
G=Graph(ab)
#print(G)
ans=dfs(G,1,-1,n)
print(ans)

Submission status: Wrong Answer

Solution code:
n,m = map(int,input().split())
 
root = [[] for i in range(n)]
for _ in range(m):
    a, b = (int(x) for x in input().split())
    root[b-1].append(a-1)
    root[a-1].append(b-1)
 
stack=[0]
check = [0]*n
check[0] = 1
 
while len(stack):
    v = stack.pop(-1)
    for i in root[v]:
        if check[i] == 0:
            stack.append(i)
        check[i] += check[v]

print(min(check))

Submission status: Wrong Answer

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

ans=0
def dfs(start,finish):
    global ans
   # print(finish)
    if len(finish)==n:#全部回ってたら終了
        ans+=1
    else:
        for i in adlist[start-1]:
            if i not in finish:#通ったところに入っていないなら通れるということ   
                #print(i)
                #print(adlist)
                finish_1=finish | set(adlist[start-1])#finish=だと結局変えてもそのまま引き継がれるのでダメ
                dfs(i,finish_1)
#finishを一回ごとに変えないといけない
adlist=[]
for h in range(n):    
    adlist.append([])
for j in range(m):
    x=ab[j][0]
    y=ab[j][1]
    adlist[x-1].append(y)
    adlist[y-1].append(x)
finish=set()
finish.add(1)
#print(adlist)
dfs(1,finish)#引数がけすノード
print(ans)