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 dfs(place,number,checkedList,path):
  checkedList[place] = 1
  if sum(checked) == number:
    return 1
  pathNumber = 0
  for i in path[place]:
    if checkedList[i] == 1:
      continue
    pathNumber += dfs(i,number,checkedList,path)
    checkedList[i] = 0
  return pathNumber  

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

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

Submission status: Wrong Answer

Solution code:
from itertools import permutations

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

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


x = [i for i in range(1,n+1)]
ls = list(permutations(x))
ans = 0
for l in ls:
    cnt = 0
    for i in range(n-1):
        for j in range(m):
            if (l[i] in edge[j]) and (l[i+1] in edge[j]):
                cnt += 1
    if i == n-1:
        ans += 1


print(cnt)

Submission status: Wrong Answer

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

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


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

    return check


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

print(count)

Submission status: Wrong Answer

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

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

print(d)


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

    return check


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

print(count)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
# 13:50 -> 

class Node():
    def __init__(self, idx):
        self.idx = idx
        self.next_node = []
    
    def add_node(self, node):
        self.next_node.append(node)

N, M = map(int, input().split())
nodes = {i:Node(i) for i in range(1,N+1)}

for m in range(M):
    a,b = map(int, input().split())
    nodes[a].add_node(nodes[b])
    nodes[b].add_node(nodes[a])

def permutation_search(idxs, now_idx):
    print(now_idx, idxs)
    if len(idxs) == 0:
        return 1

    num = 0
    for i in range(len(idxs)):
        next_idx = idxs[i]
        next_idxs = idxs[:i]+idxs[i+1:]
        if next_idx in [node.idx for node in nodes[now_idx].next_node]:
            num += permutation_search(next_idxs, next_idx)
    
    return num

total = permutation_search([i for i in range(2,N+1)], 1)

print(total)

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
root=[[] for _ in range(n+1)]
for i in range(m):
    a,b=map(int,input().split())
    root[a].append(b)
    root[b].append(a)
s=[0]*(n+1)
s[0]=1
s[1]=1
ans=0
def f(a,x):
    global ans
    for i in root[a]:
        if x[i]==0:
            x[i]=1
            f(i,x)
    if x.count(1)==n+1:
        ans+=1
f(1,s)
print(ans)

Submission status: Wrong Answer

Solution code:
def dfs(g,v,depth):
    if seen[v]==True:return 0
    if depth==n:return 1
    seen[v] = True
    paths = 0
    for next_v in g[v]:
        paths += dfs(g,next_v,depth+1)
    seen[v] = False
    return paths
        
n,m = map(int,input().split())

g = [[]*(n+1) for _ in range(n+1)]

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

seen = [False]*(n+1)
    
dfs(g,1,1)

Submission status: Wrong Answer

Solution code:
# coding: utf-8
# Your code here!

import itertools

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

graph= [[False]*N for i in range(N)]

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

lst = [i-1 for i in range(N)]
cnt = 0

for v in itertools.permutations(lst, N):
    if v[0] != 1:
        continue
    for i in range(N-1):
        if graph[v[i]][v[i+1]] == False:
            break
        if i == N-2:
            cnt += 1

print(cnt)

Submission status: Wrong Answer

Solution code:
from itertools import permutations

N, M = map(int, input().split())
root = []
for i in range(M):
    root.append(list(map(int, input().split())))
root = list(permutations(root, M))

ans = 0
for r in root:
    history = [1]
    pos = 1
    for i in r:
        if not pos in i:
            break
        else:
            if i[0] == pos:
                pos = i[1]
            else:
                pos = i[0]
            if pos in history:
                break
        history.append(pos)
        if len(history) == N:
            ans += 1
            break
print(ans)

Submission status: Wrong Answer

Solution code:
from itertools import permutations

N, M = map(int, input().split())
root = []
for i in range(M):
    root.append(list(map(int, input().split())))
root = list(permutations(root, M))

ans = 0
for r in root:
    history = [1]
    pos = 1
    for i in r:
        if not pos in i:
            break
        else:
            if i[0] == pos:
                pos = i[1]
            else:
                pos = i[0]
            if pos in history:
                break
        history.append(pos)
        if len(history) == N:
            ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
nm=[[] for _ in range(n+1)]
temp=[]
for i in range(m):
    a,b=map(int,input().split())
    temp.append([a,b])
count=0
from itertools import product
for j in product([0,1],repeat=m):
    if sum(j)==n-1:
        nm=[[] for _ in range(n)]
        for k in range(m):
            if j[k]==1:
                c,d=temp[k]
                nm[c-1].append(d)
                nm[d-1].append(c)
        
        for l in range(n):
            if len(nm[l])!=1 and len(nm[l])!=2:
                break
        else:
            if len(nm[0])==1:
                count+=1
                
print(count)

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
nm=[[] for _ in range(n+1)]
temp=[]
for i in range(m):
    a,b=map(int,input().split())
    temp.append([a,b])
count=0
from itertools import product
for j in product([0,1],repeat=m):
    if sum(j)==n-1:
        nm=[[] for _ in range(n)]
        for k in range(m):
            if j[k]==1:
                c,d=temp[k]
                nm[c-1].append(d)
                nm[d-1].append(c)
        
        for l in range(n):
            if len(nm[l])>=3:
                break
        else:
            if len(nm[0])==1:
                count+=1
                
print(count)

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
nm=[[] for _ in range(n+1)]
temp=[]
for i in range(m):
    a,b=map(int,input().split())
    temp.append([a,b])
count=0
from itertools import product
for j in product([0,1],repeat=m):
    if sum(j)==n-1:
        nm=[[] for _ in range(n)]
        for k in range(m):
            if j[k]==1:
                c,d=temp[k]
                nm[c-1].append(d)
                nm[d-1].append(c)
        
        for l in range(n):
            if len(nm[l])>=3:
                break
        else:
            count+=1
print(count)

Submission status: Wrong Answer

Solution code:
import itertools

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

#繋がっている頂点リスト
a_list = []
for j in range(m) :
    a = list(map(int, input().split()))
    a_list.append(a)
a_list.sort()

#道順リスト(最初が1に限る)
b_list = [k for k in itertools.permutations([l for l in range(1, n + 1)]) if k[0] == 1]

#道順リストの中で頂点リストが含まれているもの
cnt = 0
for x in b_list :
    if x == (1, 3, 4, 5, 6, 7, 2) :
        print("#")
    tf_list = []
    for y in range(n - 1) :
        tf_list.append([x[y], x[y + 1]] in a_list or [x[y + 1], x[y]] in a_list)
    
    if all(tf_list) == True :
        cnt += 1

print(cnt)

Submission status: Wrong Answer

Solution code:
from typing import List, Tuple


def main():
    n, m = map(int, input().split())
    g = []
    for _ in range(m):
        a, b = map(int, input().split())
        g.append((a, b))
    print(osp(n, g))


def osp(n: int, g: List[Tuple[int]]) -> int:
    graph = [[False] * n] * n
    for a, b in g:
        graph[a - 1][b - 1] = graph[b - 1][a - 1] = True
    v = [False] * n

    return dfs(0, v, n, graph)


def dfs(i, v, n, graph):
    v[i] = True
    if all(v):
        return 1

    cnt = 0
    for j in range(n):
        if v[j]:
            continue
        if not graph[i][j]:
            continue

        cnt += dfs(j, v, n, graph)
        v[j] = False

    return cnt


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import itertools

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

ans=0

for v in itertools.permutations(li):
  pas=0
  ch=0
  st=1
  for x in range(n-1):
    if v[x]-1 not in rin[st-1]:
      ch+=1
      break
    else:
      st=v[x]
  if ch==0:
    ans+=1
    
print(ans)

Submission status: Wrong Answer

Solution code:
import itertools

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

ans=0

for v in itertools.permutations(li):
  pas=0
  ch=0
  st=1
  for x in range(n-1):
    if v[x]-1 not in rin[st-1]:
      ch+=1
      break
    else:
      st=v[x]-1
  if ch==0:
    ans+=1
    
print(ans)

Submission status: Wrong Answer

Solution code:
def abc054c_one_stroke_path():
    import itertools
    n, m = map(int, input().split())
    e = [set() for _ in range(n + 1)]
    for _ in range(m):
        a, b = map(int, input().split())
        e[a].add(b)
        e[b].add(a)
    pattern = itertools.permutations(range(2, n + 1))
    cnt = 0
    for p in pattern:
        p_m = [1] + list(p)
        for i in range(n - 1):
            if p_m[i+1] not in e[p_m[i]]:
                break
        else:
            cnt += 1
    print(cnt)

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())
    G[a-1][b-1] = 1
    G[b-1][a-1] = 1

ans = 0

for p in permutations(range(N)):
    now = p[0]
    
    if now!=1:
        continue

    for i in range(1, N):
        if G[now][p[i]]==1:
            now = p[i]
        else:
            break
    else:
        ans += 1

print(ans)

Submission status: Wrong Answer

Solution code:
import itertools as it

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

#print(a)

#無向グラフのルート作成（リスト）
for i in range(len(a)):
    a.append([a[i][1],a[i][0]])
#print(a)


#１を始点とするルートを全探索で作成
lis  = list(it.permutations(range(2, n + 1)))
#print(lis)
for i in range(len(lis)):
    lis[i] = (1,) + lis[i]
#print(lis)

#リストに変換
lis2 = []
for i in range(len(lis)):
    lis[i] = list(lis[i])
    lis2.append(lis[i])
#print(lis2)

#ルート探索
for i in range(len(lis2)):
    flag = 0
    for j in range(len(lis2[i]) - 1):
        for k in range(len(a)):
            if lis2[i][j : j + 2] == a[k]:
                flag += 1
                #print(lis[i][j : j + 2], a[k])
        #print(lis[i][j : j + 2])
print(flag)

Submission status: Wrong Answer

Solution code:
import itertools as it

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

print(a)

#無向グラフのルート作成（リスト）
for i in range(len(a)):
    a.append([a[i][1],a[i][0]])
print(a)


#１を始点とするルートを全探索で作成
lis  = list(it.permutations(range(2, n + 1)))
#print(lis)
for i in range(len(lis)):
    lis[i] = (1,) + lis[i]
#print(lis)

#リストに変換
lis2 = []
for i in range(len(lis)):
    lis[i] = list(lis[i])
    lis2.append(lis[i])
print(lis2)

#ルート探索
for i in range(len(lis2)):
    flag = 0
    for j in range(len(lis2[i]) - 1):
        for k in range(len(a)):
            if lis2[i][j : j + 2] == a[k]:
                flag += 1
                #print(lis[i][j : j + 2], a[k])
        #print(lis[i][j : j + 2])
print(flag)

Submission status: Wrong Answer

Solution code:
#Nはノード数、Mはエッジ数
N, M = map(int, input().split())

path_matrix = []

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

#まず無向グラフを表す行列を作る
for m in range(M):
    line = map(int, input().split())
    paths = [x - 1 for x in line]
    path_matrix[paths[0]][paths[1]] = True
    path_matrix[paths[1]][paths[0]] = True

#最初はvisited、つまり訪問したことのあるノードはひとつもないので、Falseにする
visited = [False] * N


#再帰関数、ここが難しいかもしれない。
def dfs(now, depth):
    if visited[now]:
        return 0
    if depth == N - 1:
        return 1

    visited[now] = True
    total_paths = 0
    for i in range(0, N):
        if path_matrix[now][i]:
            total_paths += dfs(i, depth + 1)


    return total_paths

print(dfs(0, 0))

Submission status: Wrong Answer

Solution code:
#Nはノード数、Mはエッジ数
N, M = map(int, input().split())

path_matrix = []

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

#まず無向グラフを表す行列を作る
for m in range(M):
    line = map(int, input().split())
    paths = [x - 1 for x in line]
    path_matrix[paths[0]][paths[1]] = True
    path_matrix[paths[1]][paths[0]] = True

#最初はvisited、つまり訪問したことのあるノードはひとつもないので、Falseにする
visited = [False] * N


#再帰関数、ここが難しいかもしれない。
def dfs(now, depth):
    if visited[now]:
        return 0
    if depth == N - 1:
        return 1

    visited[now] = True
    total_paths = 0
    for i in range(0, N):
        if path_matrix[now][i]:
            total_paths += dfs(i, depth + 1)

    return total_paths

print(dfs(0, 0))

Submission status: Wrong Answer

Solution code:
from networkx import *
N,M = map(int,input().split())
A = [list(map(int,input().split())) for m in range(M)]
G = Graph(A)
ans = 0

for n in range(2,N+1):
  for p in all_simple_paths(G,1,n):
    if len(p)==n:
      ans+=1

print(ans)

Submission status: Wrong Answer

Solution code:
#一度だけ頂点を通る⇒辺の数=頂点-1
import itertools

Mlist=[]
N,M=map(int,input().split(' '))
for i in range(M):
  Mlist.append(list(map(int,input().split(" "))))

all_parterns=itertools.permutations(range(M),r=N-1)

ans=0
for partern in all_parterns:
  x=1
  IsOk=True
  for i in partern:
    a,b=Mlist[i]
    if x==a:
      x=b
    elif x==b:
      x=a
    else:
      IsOk=False
      break
  if IsOk:
    ans+=1

print(ans)

Submission status: Wrong Answer

Solution code:
#一度だけ頂点を通る⇒辺の数=頂点-1
import itertools

Mlist=[]
N,M=map(int,input().split(' '))
for i in range(M):
  Mlist.append(list(map(int,input().split(" "))))

all_parterns=itertools.permutations(range(M),r=N-1)

ans=0
for partern in all_parterns:
  x=1
  IsOk=True
  for i in partern:
    a,b=Mlist[i]
    if x==a:
      x=b
    elif x==b:
      x=a
    else:
      IsOk=False
  if IsOk:
    ans+=1
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
def input(): return sys.stdin.readline().strip()
sys.setrecursionlimit(10**9)

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

    visited = [0] * N
    visited[0] = 1
    ans = [0]

    def stroke(u):
        #print("now={}, vis={}".format(u, visited))
        if visited == [1] * N:
            ans[0] += 1
            return
        for v in repn[u]:
            if visited[v] == 1: continue
            visited[v] = 1
            stroke(v)
            visited[v] = 0

    stroke(0)
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import itertools
n,m=map(int,input().split())
l=[[0]*n for i 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
d=[int(i)+1 for i in range(n)]
ans=chk=0
print(l)
for i in list(itertools.permutations(d,n)):
    chk=1
    if i[0]!=1: continue
    for j in range(n-1):
        chk*=l[i[j+1]-1][i[j]-1]
    ans+=chk
print(ans)

Submission status: Wrong Answer

Solution code:
from itertools import permutations
N, M = map(int, input().split())
AB = [tuple(map(int, input().split())) for _ in range(M)]

fst = [ab[1] for ab in AB if ab[0] == 1] + [ab[0] for ab in AB if ab[1] == 1]
remains = [ab for ab in AB if ab[0] != 1 and ab[1] != 1 and (ab[0] in fst or ab[1] in fst)]

ans = 0
for ab in permutations(remains):
    for here in fst:
        valid = True
        for (a, b) in ab:
            if a == here:
                here = b
            elif b == here:
                here = a
            else:
                valid = False
                break
        if valid:
            ans += 1

print(ans)

Submission status: Wrong Answer

Solution code:
from itertools import permutations
N, M = map(int, input().split())
AB = [tuple(map(int, input().split())) for _ in range(M)]

ans = 0
for ab in permutations(AB):
    here = 1
    valid = True
    for (a, b) in ab[1:]:
        if a == here:
            here = b
        elif b == here:
            here = a
        else:
            valid = False
            break
    if valid:
        ans += 1

print(ans)

Submission status: Wrong Answer

Solution code:
import itertools


def main():
    N, M = map(int, input().split())
    node_lst = [x for x in range(N)]
    edge_lst = [list(map(int, input().split())) for _ in range(M)]
    ans = 0
    print(edge_lst)

    for route in itertools.permutations(node_lst):
        is_visited = [False] * N
        is_visited[0] = True
        if route[0] != 0:
            continue

        for i in range(N - 1):
            if [route[i] + 1, route[i + 1] + 1] in edge_lst and is_visited[route[i + 1]] == False:
                is_visited[route[i + 1]] = True
            if [route[i + 1] + 1, route[i] + 1] in edge_lst and is_visited[route[i + 1]] == False:
                is_visited[route[i + 1]] = True

        if is_visited == [True] * N:
            ans += 1

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
from collections import deque
inf=float("inf")


def BFS():
    color=["white" for _ in range(N+1)]
    D=[inf for _ in range(N+1)]

    queue=deque([1])
    D[1]=0
    color[1]="gray"

    while len(queue)>0:
        num=queue.popleft()
        for i in MAP[num]:
            if color[i]!="black":
                D[i]=D[num]+1
                color[i]="gray"
                queue.append(i)
        color[num]="black"

    return True if N-1 in D else False


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

cnt=0
for i in range(M):
    MAP=[[] for _ in range(N+1)]
    for j in range(M):
        if i==j:continue
        a,b=AB[j]
        MAP[a].append(b)
        MAP[b].append(a)
    cnt +=BFS()
print(cnt)

Submission status: Wrong Answer

Solution code:
from collections import deque
inf=float("inf")


def BFS():
    color=["white" for _ in range(N+1)]
    D=[inf for _ in range(N+1)]

    queue=deque([1])
    D[1]=0
    color[1]="gray"

    while len(queue)>0:
        num=queue.popleft()
        for i in MAP[num]:
            if color[i]=="white":
                D[i]=D[num]+1
                color[i]="gray"
                queue.append(i)

    return True if N-1 in D else False


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

cnt=0
for i in range(M):
    MAP=[[] for _ in range(N+1)]
    for j in range(M):
        if i==j:continue
        a,b=AB[j]
        MAP[a].append(b)
        MAP[b].append(a)
    cnt +=BFS()
print(cnt)

Submission status: Wrong Answer

Solution code:
n,m=list(map(int,input().split()))
# 再帰の深さが1000を超えそうなときはこれをやっておく
import sys
sys.setrecursionlimit(10**7)

#隣接行列表現
es=[[0 for i in range(n)] for j in range(n)]
for i in range(m):
  a,b=list(map(int,input().split()))
  es[a-1][b-1]=1
  es[b-1][a-1]=1

  
#深さ優先探索

def dfs(v,visited):
  ans=0
  
  #自分が今いるところは探索済にする
  visited[v-1]=1
  print(visited)
  #全部探索できたことになる
  if visited==check:
    visited[v-1]=0
    return 1
  
  #vから行けるところを考える
  for i in range(n):
    #道があって未訪問
    if visited[i]==0 and es[v-1][i]==1:
      ans=ans+dfs(i+1,visited)
  #次の探索のため未訪問にしておく
  visited[v-1]=0
   
  return ans





visited=[0 for i in range(n)]
check=[1 for i in range(n)]
print(dfs(1,visited))

Submission status: Wrong Answer

Solution code:
import math,itertools,fractions,heapq,collections,bisect,sys,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
# def LF(): return [float(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

N,M=LI()
graph=[[N]*8 for _ in range(N)]

for _ in range(M):
  a,b=LI()
  a-=1
  b-=1
  graph[a][b]=True
  graph[b][a]=True

def dfs(v,visited):
  all_visited=True
  for i in range(N):
    if not visited[i]:
      all_visited=False
  if all_visited:
    return 1

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

  return ret

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

Submission status: Wrong Answer

Solution code:
import sys
from itertools import permutations

sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7


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

    res = 0
    for pattern in permutations(range(n)):
        if pattern[0] == 1:
            for i in range(1, n):
                prev = pattern[i - 1]
                now = pattern[i]
                if (prev, now) not in edge:
                    break
            else:
                res += 1
    print(res)


if __name__ == '__main__':
    resolve()

Submission status: Wrong Answer

Solution code:
import numpy

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
n, m = map(lambda x: int(x), input().split())

links = defaultdict(set)

for _ in range(m):
    a, b = map(lambda x: int(x), input().split())
    links[a].add(b)
    links[b].add(a)
    
path_counter = 0
    
def path_patterns_number(current_node, remaining_nodes):#, remaining_links):
#     print(current_node, remaining_nodes)
    if len(remaining_nodes) == 0:
        return 1
    
    patterns = 0
    
    for next_node in (links[current_node] & remaining_nodes):
#         remaining_links_copy = remaining_links.copy()
#         remaining_links_copy[current_node].remove(next_node) <=浅いコピーなので元のからもremoveされてる
        patterns += path_patterns_number(
            next_node,
            remaining_nodes.copy() - {next_node}
#             remaining_links_copy
        )
    
    return patterns
    
path_patterns_number(1, set(range(2,n+1)))#, links)

Submission status: Wrong Answer

Solution code:
import math

n, m = list(map(int, input().split()))
ab = [list(map(int, input().split())) for _ in range(m)]
t = [[] for _ in range(n + 1)]
for i in ab:
    t[i[0]].append(i[1])
    t[i[1]].append(i[0])
ans = math.inf
for i in range(1, n + 1):
    ans = min(ans, len(t[i]))

print(ans)

Submission status: Wrong Answer

Solution code:
def saiki(arr_lst,count,path,N):
	print(path)
	if len(path) == N:
		count[0] += 1
	else:
		here = path[-1]
		arrival = arr_lst[here]
		for next in arrival:
			if not next in path:
				newpath = path[:]
				newpath.append(next)
				saiki(arr_lst,count,newpath,N)


if __name__ == '__main__':
	N, M = map(int, input().split())
	arr_lst = [[]]

	for i in range(1,N+1):
		arr_lst.append([])

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

	count = [0]

	saiki(arr_lst,count,[1],N)

	print(count[0])

Submission status: Wrong Answer

Solution code:
import itertools
N,M=map(int,input().split())
A=[list(map(int,input().split())) for i in range(M)]
people=[]

for i in range(1,N+1) :
    people.append(i)

people_combination=list(itertools.permutations(people,N))
n=(N-1)*(N-2)
ans=0

for i in range(n) :
    for j in range(N-1) :
        if people_combination[i][j]<people_combination[i][j+1] :
            if [people_combination[i][j],people_combination[i][j+1]] in A :
                continue
            else :
                break
        elif people_combination[i][j]>people_combination[i][j+1] :
            if [people_combination[i][j+1],people_combination[i][j]] in A :
                continue
            else :
                break
    else :
        ans+=1
        continue
    break
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
import math
import itertools
import statistics
n,m=map(int,input().split())
side=[]
for _ in range(m):
    side.append(tuple(map(int,input().split())))
per_lis=itertools.permutations(list(range(1,n+1)))
ans=0
for one_case in per_lis:
    if one_case[0]==1:
        tmp=0
        for i in range(n-1):
            if (one_case[i],one_case[i+1]) or (one_case[i+1],one_case[i]) in side:
                tmp+=1
        if tmp==n-1:
            ans+=1
print(ans)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
N,M = map(int, input().split())
G = [[] for j in range(N)]
#グラフの読み込み
for i in range(M):
    a,b = map(int, input().split())
    G[a-1].append(b-1)
    G[b-1].append(a-1)
print(G)
visited = [False]*N
visited[0] = True
#再帰
def DFS(v,visited):
    #もし全てTrueなら1を返す
    if all(visited):
        return 1
    ans = 0
    for i in G[v]:
        print('i',i)
        if visited[i]:
            continue
        visited[i] = True
        ans += DFS(i,visited)
        visited[i] = False
    return ans

print(DFS(0,visited))

Submission status: Wrong Answer

Solution code:
def kaijyo(n):
    ans = 1
    for i in range(n):
        ans *= i + 1
    return ans

N,M = map(int,input().rstrip().split(" "))
hen = []
ans = 0
for i in range(M):
    a,b = map(int,input().rstrip().split(" "))
    hen.append([a,b])
print(hen)
for i in range(kaijyo(N-1)):
    lis = [i+2 for i in range(N-1)]
    lis2 = [1]
    k = i
    for i2 in range(N-1):
        lis2.append(lis[k % (N - 1 - i2)])
        k = k // (N - 1 - i2)
        for i3 in range(len(lis)):
            if lis[i3] == lis2[-1]:
                lis.pop(i3)
                break
    for i2 in range(N-1):
        if not ([lis2[i2],lis2[i2+1]] in hen or [lis2[i2+1],lis2[i2]] in hen):
            break
        if i2 == N - 2:
            ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**7)
n, m = map(int, input().split())
ab = [[] for i in range(n)]
for i in range(m):
  a, b = map(int, input().split())
  a -= 1
  b -= 1
  ab[a].append(b)
  ab[b].append(a)

ary = []
def dfs(s,t):
  if len(t) == m:
    ary.append(t)
    return
  for i in ab[s]:
    if i not in t:
      dfs(i,t+[i])
  return
dfs(0,[0])

print (len(ary))

Submission status: Wrong Answer

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

ary = []
def dfs(s,t):
  if len(t) == m:
    ary.append(t)
    return
  for i in ab[s]:
    if i not in t:
      dfs(i,t+[i])

dfs(x,[0])

print (len(ary))

Submission status: Wrong Answer

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

ary = []
def dfs(s,t):
  if len(t) == m:
    ary.append(t)
  for i in ab[s]:
    if i not in t:
      dfs(i,t+[i])

dfs(x,[0])

print (len(ary))

Submission status: Wrong Answer

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

ary = []
def dfs(s,t):
  if len(t) == m:
    ary.append(t)
  for i in ab[s]:
    if i not in t:
      dfs(i,t+[i])

dfs(0,[0])

print (len(ary))

Submission status: Wrong Answer

Solution code:
import itertools

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

route = itertools.permutations([i for i in range(2,N+1)])
route = ((1,)+ i for i in route)

ans = 0
for i in route:
    count = 0
    for j in range(M):
        a,b = ab[j][0],ab[j][1]
        if i.index(a) == i.index(b)+1 or i.index(a) == i.index(b)-1:
            count += 1
            if count == M-1:
                ans +=1
    

print(ans)

Submission status: Wrong Answer

Solution code:
import itertools
N,M = map(int,input().split())
L=[]
for i in range(M):
    a,b=map(int,input().split())
    L.append([a,b])

number=[]
for i in range(1,N+1):
    number.append(i)
    
ans=0
a=0
for v in itertools.permutations(number,N):
    v=list(v)
    for j in range(N-1):
        if ([v[j],v[j+1]] not in L ) and ([v[j+1],v[j]] not in L):
            a=1
    if a==0 and v[0]==1:
        ans+=1

print(ans)