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:
import itertools
import collections

N,M = map(int,input().split())
side = [list(map(int,input().split())) for _ in range(M)]
c_side = list(itertools.combinations(side,N-1)) #mCn-1の組み合わせを作成
result = 0

for i in c_side: #全ての組み合わせを一つずつチェックしていく
  box = []
  for j in range(len(i)): #リストを一つに
    box += i[j]
  check_box = collections.Counter(box) #リスト内の数字の数を出す
  bool1 = True
  for n in range(1,N):
    if check_box[n] <= 0:
      bool1 = False
      break
  if not bool1:
    continue
  if check_box[1] != 1:
    continue

  count = 0
  for k in range(2,N):
    if check_box[j] == 1:
      count += 1
      if count == 2:
        break
    elif check_box[j] > 2:
      continue
  else:
    result += 1
print(result)

Submission status: Wrong Answer

Solution code:
from itertools import permutations

n, m = map(int, input().split())
L = [set() for _ in range(n)]
for _ in range(m):
    a, b = map(int, input().split())
    L[a-1].add(b-1)
    L[b-1].add(a-1)
lst = [i for i in range(1, n)]
ans = 0
for v in permutations(lst, n-1):
    case = [0] + list(v)
    for i in range(n-2):
        next = case[i+1]
        if next not in L[i]:
            break
    else:
        ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
import itertools as it

n,m=map(int,input().split())
path=[]
for i in range(m): path.append(list(map(int,input().split())))
ls=list(it.permutations(range(1,n+1)))
cnt=0
for l in ls:
    if l[0]!=1: break
    for i in range(n-1):
        if [i,i+1] in path: cnt+=1
print(cnt)

Submission status: Wrong Answer

Solution code:
import itertools
(n,_),*a= [[*map(int,i.split())] for i in open(0)]
p=itertools.permutations(range(1,n+1),n)
c = 0
for i in p:
    for j in range(n-1):
        if sorted([i[j],i[j+1]]) not in a:
            break
    else:
        c+=1
print(c)

Submission status: Wrong Answer

Solution code:
import numpy as np
N,M = map(int,input().split())
ab=[]
while True:
    try:
        ab.append(list(map(int,input().split())))

    except:
        break;
        
adjacency_matrix= np.full((N, N),False, dtype=bool)
for pair in ab:
  adjacency_matrix[pair[0]-1][pair[1]-1]=True
  adjacency_matrix[pair[1]-1][pair[0]-1]=True

  
A=[]
for n in range(N):
  A.append(np.linalg.matrix_power(adjacency_matrix, n))

A_m=[[0] * N for i in range(N)]
shortest_path=0
for matrix in A:
  shortest_path+=1
  for i in range(N):
    for j in range(N):
      if (matrix[i][j]==True)and(A_m[i][j]==0):
        A_m[i][j]=shortest_path

depth_list=[]
for i in range(max(A_m[0])):
  depth_list.append(A_m[0].count(i+1))

import functools
import operator
print(functools.reduce(operator.mul, depth_list))

Submission status: Wrong Answer

Solution code:
from itertools import permutations

V, E = map(int, input().split())
edges = {tuple(map(int, input().split())) for _ in range(E)}
ans = 0

for route in permutations(range(2, V+1)):
	route = [1] + list(route)
	ans += len([1 for edge in zip(route, route[1:]) 
				if tuple(sorted(edges)) in edges]) == V - 1
print(ans)

Submission status: Wrong Answer

Solution code:
from itertools import permutations

V, E = map(int, input().split())
edges = {tuple(map(int, input().split())) for _ in range(E)}
ans = 0

for route in permutations(range(2, V+1)):
	route = [1] + list(route)
	ans += len([1 for edge in zip(route, route[1:]) 
		if tuple(sorted(edges)) in edges]) == V - 1
print(ans)

Submission status: Wrong Answer

Solution code:

from itertools import permutations

V, E = map(int, input().split())
edges = {tuple(map(int, input().split())) for _ in range(E)}
ans = 0

for route in permutations(range(2, V+1)):
	route = [1] + list(route)
	ans += len([1 for edge in zip(route, route[1:]) if tuple(sorted(edges)) in edges]) == V - 1
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
import itertools
input = sys.stdin.readline
 
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    N, M = MI()
    numlist = [i for i in range(1, N)]
    mylist2 = [[0 for i in range(N)] for j in range(M)]
    result = 0
    for i in range(M):
        a, b = MI()
        mylist2[min(a, b) - 1][max(a, b) - 1] = 1
        index = 0
    for j in itertools.permutations(numlist, len(numlist)):
        mylist = mylist2[:]
        for k in j:
            try:
                if mylist[min(past, k)][max(past, k)] == 1:
                    mylist[min(past, k)][max(past, k)] = 0
                    past =  k
                    index += 1
                else:
                    break
            except:
                past = 0
                if mylist[0][k] == 1:
                    mylist[0][k] = 0
                    past = k
                    index += 1
        if index == len(numlist):
            result += 1
    print(result)
    
main()

Submission status: Wrong Answer

Solution code:
import sys
import itertools
input = sys.stdin.readline
 
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    N, M = MI()
    numlist = [i for i in range(1, N)]
    mylist2 = [[0 for i in range(N)] for j in range(M)]
    result = 0
    for i in range(M):
        a, b = MI()
        mylist2[min(a, b) - 1][max(a, b) - 1] = 1
        print(mylist2)
        index = 0
    for j in itertools.permutations(numlist, len(numlist)):
        mylist = mylist2[:]
        for k in j:
            try:
                if mylist[min(past, k)][max(past, k)] == 1:
                    mylist[min(past, k)][max(past, k)] = 0
                    past =  k
                    index += 1
                else:
                    break
            except:
                past = 0
                if mylist[0][k] == 1:
                    mylist[0][k] = 0
                    past = k
                    index += 1
        if index == len(numlist):
            result += 1
    print(result)
    
main()

Submission status: Wrong Answer

Solution code:
import sys
import itertools
input = sys.stdin.readline
 
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    N, M = MI()
    numlist = [i for i in range(1, N)]
    print(numlist)
    mylist2 = [[0 for i in range(N)] for j in range(M)]
    print(mylist2)
    result = 0
    for i in range(M):
        a, b = MI()
        mylist2[min(a, b) - 1][max(a, b) - 1] = 1
        print(mylist2)
        index = 0
    for j in itertools.permutations(numlist, len(numlist)):
        mylist = mylist2[:]
        for k in j:
            try:
                if mylist[min(past, k)][max(past, k)] == 1:
                    mylist[min(past, k)][max(past, k)] = 0
                    past =  k
                    index += 1
                else:
                    break
            except:
                past = 0
                if mylist[0][k] == 1:
                    mylist[0][k] = 0
                    past = k
                    index += 1
        if index == len(numlist):
            result += 1
    print(result)
    
main()

Submission status: Wrong Answer

Solution code:
import sys
import itertools
input = sys.stdin.readline
 
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    N, M = MI()
    numlist = [i for i in range(1, N)]
    mylist2 = [[0 for i in range(N)] for j in range(M)]
    reuslt = 0
    for i in range(M):
        a, b = MI()
        mylist[min(a, b) - 1][max(a, b) - 1] = 1
        for j in itertools.permutations(numlist, len(numlist)):
            mylist = mylist2[:]
            for k in j:
                try:
                    if mylist[min(past, k)][max(past, k)] == 1:
                        mylist[min(past, k)][max(past, k)] = 0
                        past =  k
                    else:
                        break
                except:
                    past = 0
                    if mylist[0][k] == 1:
                        mylist[0][k] = 0
                        past = k
            if sum(map(sum, mylist)) == 0:
                result += 1
    print(resutl)

Submission status: Wrong Answer

Solution code:
import itertools
N, M = map(int, input().split())
l = []
seq = []
num = 0
for _ in range(M):
    a,b = list(map(int, input().split()))
    l.append([a-1,b-1])
    seq.append(num)
    num += 1
cnt = 0
for i in list(itertools.permutations(seq)):
  ans = [0]*N
  ans[0]+=1
  e = 0
  for n,j in enumerate(i):
    a = l[j][0]
    b = l[j][1]
    if e == a:
      e = b
      ans[e]+=1
    elif e == b:
      e = a
      ans[e]+=1
    else:
      break
    if ans[e]>=2:
      break
    if sum(ans) == N:
      cnt += 1
      break
print(cnt)

Submission status: Wrong Answer

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

import itertools
np = [i for i in range(1,n)]
p = list(itertools.permutations(np))
ans = 0
for pi in p:
  flag = True
  sta = 0
  for j in range(n-1):
    if pi[j] not in graph[sta]:
      flag = False
      break
    else:
      sta = pi[j]
  ans += 1

print(ans)

Submission status: Wrong Answer

Solution code:
#C
import itertools
n, m = map(int, input().split())
l = [list(map(int, input().split())) for _ in range(m)]
paths= list(itertools.permutations(l))
ans = 0
for path in paths:
    state = 1
    ver = [i for i in range(2,n+1) ]
    for edge in path:
        if state == edge[0]:
            if edge[1] in ver:
                state = edge[1]
                ver.remove(edge[1])
            else:
                break
        elif state == edge[1]:
            if edge[0] in ver:
                state = edge[0]
                ver.remove(edge[0])
            else:
                break
        else:
            break
        if ver == []:
            ans += 1
            break
print(ans)

Submission status: Wrong Answer

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

G = [[] for i in range(N)]
for i in range(M):
    a, b = ab[i]
    G[a-1].append(b-1)
    G[b-1].append(a-1)

def rec(v, memo):
    memo[v] = 1

    if -1 not in memo:
        memo[v] = -1
        return 1

    count = 0
    for next_v in G[v]:
        if memo[next_v] == -1:
            count += rec(next_v, memo)

    memo[v] = -1
    return count

memo = [-1 for i in range(N)]
print(rec(1, memo))

Submission status: Wrong Answer

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

G = [[] for i in range(N)]
for i in range(M):
    a, b = ab[i]
    G[a-1].append(b-1)
    G[b-1].append(a-1)

def rec(v, memo):
    memo[v] = 1

    if -1 not in memo:
        memo[v] -1
        return 1

    count = 0
    for next_v in G[v]:
        if memo[next_v] == -1:
            count += rec(next_v, memo)

    memo[v] = -1
    return count

memo = [-1 for i in range(N)]
print(rec(1, memo))

Submission status: Wrong Answer

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

G = [[] for i in range(N)]
for i in range(M):
    a, b = ab[i]
    G[a-1].append(b-1)
    G[b-1].append(a-1)

def rec(v, memo):
    if memo.count(-1) == 1:
        return 1

    memo[v] = 1

    count = 0
    for next_v in G[v]:
        if memo[next_v] == -1:
            count += rec(next_v, memo)

    memo[v] = -1
    return count

memo = [-1 for i in range(N)]
print(rec(1, memo))

Submission status: Wrong Answer

Solution code:
import itertools
N, M = map(int, input().split())
p = [list(map(int, input().split())) for i in range(M)]
v = list(map(list, itertools.permutations(range(1,N+1), N)))
cnt = 0
for i in range(len(v)):
    for j in range(N-1):
        #print((i,j))
        #print(v[i][j:j+2])
        if v[i][j:j+2] in p:
            cnt += 1
print(int(cnt/2))

Submission status: Wrong Answer

Solution code:
# ACB054C
n, m = map(int, input().split())
L = [[] for i in range(n)]

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

ans = 0
def f(t, history):
    history[t] += 1
    his = history[:]
    global ans
    if sum(his) == n:
        ans += 1
        # print("count!")
    else:
        
        for i in L[t]:
            if his[i] == 0:
                # print(t, i, history)
                f(i, his)
            
f(0, [0]*n)
print(ans)

Submission status: Wrong Answer

Solution code:
# ACB054C
import itertools
n, m = map(int, input().split())
# L = [[] for i in range(n)]

if m < n-1:
    print(0)
M = []
for i in range(m):
    # a, b = map(int, input().split())
    # L[a-1].append(b)
    # L[b-1].append(a)
    M.append(list(map(int, input().split())))

count = 0

for i in itertools.combinations(M, r=n-1):
    A = [0]*n
    a = True
    for j in i:
        A[j[0]-1] += 1
        A[j[1]-1] += 1
        if A[j[0]-1] > 2 or A[j[1]-1] > 2:
            a = False

    if a == True and A[0] == 1:
        count += 1
    # print(i, A, a)
print(count)

Submission status: Wrong Answer

Solution code:
from itertools import permutations

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

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

for p in list(permutations(range(N))):
    if p[0] != 0:
        continue
    else:
        check = 1
        for i in range(N - 1):
            check *= matrix[i][i+1]
        ans += check

print(ans)

Submission status: Wrong Answer

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

def func(x, c):
    global C
    c += 1
    last = True
    for r in R[x]:
        if r in Parents[x]:
            continue
        for i in range(len(Parents[x])):
            Parents[r].append(Parents[x][i])
        Parents[r].append(x)
        last = False
        func(r, c)
        Parents[r].remove(x)
    if last:
        if c == N:
            C += 1

func(0, 0)
print(C)

Submission status: Wrong Answer

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

G = [[] for i 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)

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

def dfs(v):
    global ans
    if 0 not in visited:
        return 1

    for i in G[v]:
        if visited[i] == 0:
            visited[i] = 1
            ans += dfs(i)
            visited[i] = 0

    return ans

print(dfs(0))

Submission status: Wrong Answer

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

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

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

def dfs(v, visited):
    if 0 not in visited:
        return 1

    ans = 0
    for i in G[v]:
        if visited[i] == 0:
            visited[i] = 1
            ans += dfs(i, visited)
            visited[i] = 0

    return ans

print(dfs(0, visited))

Submission status: Wrong Answer

Solution code:
import copy
A = list()
n, m = map(int, input().split())
for i in range(m):
    a = list(map(int, input().split()))
    A.append(a)
    A.append([a[1], a[0]])

B = list()

def update(current=[1], rest=A, count = 0):
    next = list(filter(lambda x: x[0] == current[count], rest))
    if len(current) < n - 1:
        for ne in next:
            l = copy.deepcopy(current)
            l.append(ne[1])
            nRest = list(filter(lambda x: x[0] != current[count] and x[1] != current[count] and x[1] != ne[1], rest))
            update(l, nRest, count + 1)
    else:
        B.append(current)

update()
print(len(B))

Submission status: Wrong Answer

Solution code:
import copy
A = list()
n, m = map(int, input().split())
for i in range(m):
    a = list(map(int, input().split()))
    A.append(a)
    A.append([a[1], a[0]])

B = list()

def update(current=[1], rest=A, count = 0):
    next = list(filter(lambda x: x[0] == current[count], rest))
    if len(current) < m:
        for n in next:
            l = copy.deepcopy(current)
            l.append(n[1])
            nRest = list(filter(lambda x: x[0] != current[count] and x[1] != current[count] and x[1] != n[1], rest))
            update(l, nRest, count + 1)
    else:
        B.append(current)

update()
print(len(B))

Submission status: Wrong Answer

Solution code:
import copy
A = list()
n, m = map(int, input().split())
for i in range(m):
    a = list(map(int, input().split()))
    A.append(a)
    A.append([a[1], a[0]])

B = list()

def update(current=[1], rest=A, count = 0):
    next = list(filter(lambda x: x[0] == current[count], rest))
    if len(current) < m:
        for n in next:
            l = copy.deepcopy(current)
            l.append(n[1])
            nRest = list(filter(lambda x: x[0] != current[count] and x[1] != current[count], rest))
            update(l, nRest, count + 1)
    else:
        B.append(current)

update()
print(len(B))

Submission status: Wrong Answer

Solution code:
# C. One-stroke Path
# https://atcoder.jp/contests/abc054/tasks/abc054_c

from collections import deque

def dfs(i, visited):
    stack = deque()
    total = 0
    stack.append((i, visited))
    while stack:
        idx, vis = stack.pop()
        if all(vis):
            total += 1
        for j in graph[idx]:
            if not vis[j]:
                vis[j] = True
                stack.append((j, vis))
    return total

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

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

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

Submission status: Wrong Answer

Solution code:
# C. One-stroke Path
# https://atcoder.jp/contests/abc054/tasks/abc054_c

from collections import deque

def dfs(i, visited):
    stack = deque()
    total = 0
    stack.append((i, visited))
    while stack:
        idx, vis = stack.popleft()
        if all(vis):
            total += 1
        for j in graph[idx]:
            if not vis[j]:
                vis[j] = True
                stack.append((j, vis))
    return total

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

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

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

Submission status: Wrong Answer

Solution code:
from collections import deque
from heapq import heapify,heappop,heappush,heappushpop
from copy import copy,deepcopy
from itertools import product,permutations,combinations,combinations_with_replacement
from collections import defaultdict,Counter
from bisect import bisect_left,bisect_right
# from math import gcd,ceil,floor,factorial
# from fractions import gcd
from functools import reduce
from pprint import pprint

INF = float("inf")

def myinput():
    return map(int,input().split())

def mylistinput(n):
    return [ list(myinput()) for _ in range(n) ]

def mycol(data,col):
    return [ row[col] for row in data ]

def mysort(data,col,reverse_flag):
    data.sort(key=lambda x:x[col],reverse=reverse_flag)
    return data

def mymax(data):
    M = -1*float("inf")
    for i in range(len(data)):
        m = max(data[i])
        M = max(M,m)
    return M

def mymin(data):
    m = float("inf")
    for i in range(len(data)):
        M = min(data[i])
        m = min(m,M)
    return m

def mycount(ls,x):
    # lsはソート済みであること
    l = bisect_left(ls,x)
    r = bisect_right(ls,x)
    return (r-l)

def myoutput(ls,space=True):
    if space:
        if len(ls)==0:
            print(" ")
        elif type(ls[0])==str:
            print(" ".join(ls))
        elif type(ls[0])==int:
            print(" ".join(map(str,ls)))
        else:
            print("Output Error")
    else:
        if len(ls)==0:
            print("")
        elif type(ls[0])==str:
            print("".join(ls))
        elif type(ls[0])==int:
            print("".join(map(str,ls)))
        else:
            print("Output Error")

def I():
    return int(input())

def MI():
    return map(int,input().split())

def RI():
    return list(map(int,input().split()))

def CI(n):
    return [ int(input()) for _ in range(n) ]

def LI(n):
    return [ list(map(int,input().split())) for _ in range(n) ]

def S():
    return input()

def MS():
    return input().split()

def RS():
    return list(input().split())

def CS(n):
    return [ input() for _ in range(n) ]

def LS(n):
    return [ list(input().split()) for _ in range(n) ]

n,m = RI()
ab = LI(m)

g = [ [] for _ in range(n) ]
for i in range(m):
    a = ab[i][0] - 1
    b = ab[i][1] - 1
    g[a].append(b)
    g[b].append(a)
# print(g)

l = list(range(1,n))
ls = list( permutations(l) )
# print(ls)

ans = 0
for i in range(len(ls)):
    flag = True
    v = [0]*n
    p = list(ls[i])
    for j in range(len(p)-1):
        if v[p[j]]!=0:
            flag = False
        else:
            if p[j+1] in g[p[j]]:
                v[p[j]] = 1
            else:
                flag = False
    if flag:
        ans += 1
    else:
        pass

print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque
from heapq import heapify,heappop,heappush,heappushpop
from copy import copy,deepcopy
from itertools import product,permutations,combinations,combinations_with_replacement
from collections import defaultdict,Counter
from bisect import bisect_left,bisect_right
# from math import gcd,ceil,floor,factorial
# from fractions import gcd
from functools import reduce
from pprint import pprint

INF = float("inf")

def myinput():
    return map(int,input().split())

def mylistinput(n):
    return [ list(myinput()) for _ in range(n) ]

def mycol(data,col):
    return [ row[col] for row in data ]

def mysort(data,col,reverse_flag):
    data.sort(key=lambda x:x[col],reverse=reverse_flag)
    return data

def mymax(data):
    M = -1*float("inf")
    for i in range(len(data)):
        m = max(data[i])
        M = max(M,m)
    return M

def mymin(data):
    m = float("inf")
    for i in range(len(data)):
        M = min(data[i])
        m = min(m,M)
    return m

def mycount(ls,x):
    # lsはソート済みであること
    l = bisect_left(ls,x)
    r = bisect_right(ls,x)
    return (r-l)

def myoutput(ls,space=True):
    if space:
        if len(ls)==0:
            print(" ")
        elif type(ls[0])==str:
            print(" ".join(ls))
        elif type(ls[0])==int:
            print(" ".join(map(str,ls)))
        else:
            print("Output Error")
    else:
        if len(ls)==0:
            print("")
        elif type(ls[0])==str:
            print("".join(ls))
        elif type(ls[0])==int:
            print("".join(map(str,ls)))
        else:
            print("Output Error")

def I():
    return int(input())

def MI():
    return map(int,input().split())

def RI():
    return list(map(int,input().split()))

def CI(n):
    return [ int(input()) for _ in range(n) ]

def LI(n):
    return [ list(map(int,input().split())) for _ in range(n) ]

def S():
    return input()

def MS():
    return input().split()

def RS():
    return list(input().split())

def CS(n):
    return [ input() for _ in range(n) ]

def LS(n):
    return [ list(input().split()) for _ in range(n) ]

n,m = RI()
ab = LI(m)

g = [ [] for _ in range(n) ]
for i in range(m):
    a = ab[i][0] - 1
    b = ab[i][1] - 1
    g[a].append(b)
    g[b].append(a)
# print(g)

l = list(range(1,n))
ls = list( permutations(l) )
# print(ls)

ans = 0
for i in range(len(ls)):
    flag = True
    v = [0]*n
    p = list(ls[i])
    for j in range(len(p)-1):
        if v[p[j]]!=0:
            flag = False
        else:
            if p[j+1] in g[j]:
                v[p[j]] = 1
            else:
                flag = False
    if flag:
        ans += 1
    else:
        pass

print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque
from heapq import heapify,heappop,heappush,heappushpop
from copy import copy,deepcopy
from itertools import product,permutations,combinations,combinations_with_replacement
from collections import defaultdict,Counter
from bisect import bisect_left,bisect_right
# from math import gcd,ceil,floor,factorial
# from fractions import gcd
from functools import reduce
from pprint import pprint

INF = float("inf")

def myinput():
    return map(int,input().split())

def mylistinput(n):
    return [ list(myinput()) for _ in range(n) ]

def mycol(data,col):
    return [ row[col] for row in data ]

def mysort(data,col,reverse_flag):
    data.sort(key=lambda x:x[col],reverse=reverse_flag)
    return data

def mymax(data):
    M = -1*float("inf")
    for i in range(len(data)):
        m = max(data[i])
        M = max(M,m)
    return M

def mymin(data):
    m = float("inf")
    for i in range(len(data)):
        M = min(data[i])
        m = min(m,M)
    return m

def mycount(ls,x):
    # lsはソート済みであること
    l = bisect_left(ls,x)
    r = bisect_right(ls,x)
    return (r-l)

def myoutput(ls,space=True):
    if space:
        if len(ls)==0:
            print(" ")
        elif type(ls[0])==str:
            print(" ".join(ls))
        elif type(ls[0])==int:
            print(" ".join(map(str,ls)))
        else:
            print("Output Error")
    else:
        if len(ls)==0:
            print("")
        elif type(ls[0])==str:
            print("".join(ls))
        elif type(ls[0])==int:
            print("".join(map(str,ls)))
        else:
            print("Output Error")

def I():
    return int(input())

def MI():
    return map(int,input().split())

def RI():
    return list(map(int,input().split()))

def CI(n):
    return [ int(input()) for _ in range(n) ]

def LI(n):
    return [ list(map(int,input().split())) for _ in range(n) ]

def S():
    return input()

def MS():
    return input().split()

def RS():
    return list(input().split())

def CS(n):
    return [ input() for _ in range(n) ]

def LS(n):
    return [ list(input().split()) for _ in range(n) ]

n,m = RI()
ab = LI(m)

g = [ [] for _ in range(n) ]
for i in range(m):
    a = ab[i][0] - 1
    b = ab[i][1] - 1
    g[a].append(b)
    g[b].append(a)
# print(g)

l = list(range(1,n))
ls = list( permutations(l) )
# print(ls)

ans = 0
for i in range(len(ls)):
    flag = True
    v = [0]*n
    p = list(ls[i])
    for j in range(len(p)-1):
        if v[j]!=0:
            flag = False
        else:
            if p[j+1] in g[j]:
                v[j] = 1
            else:
                flag = False
    if flag:
        ans += 1
    else:
        pass

print(ans)

Submission status: Wrong Answer

Solution code:
import itertools

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

path_matrix = []

# 無向グラフの作成
for n in range(N):
    path_matrix.append([0] * N)

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

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

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

Submission status: Wrong Answer

Solution code:
import itertools
import sys

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

if M < N-1:
  print(0)
  sys.exit()

p = [i for i in range(M)] #0からM-1本目までの道のリスト
root = []
for i in range(M):
  a,b = map(int,input().split())
  root.append([a-1,b-1])

#たどる道の全探索
pattern = list(itertools.permutations(p))
#print(pattern)

ans = 0
for i in range(len(pattern)):
  Flag = [0 for t in range(N)]
  Flag[0] = 1
  now = 0
  last = False
  for j in range(N-1):
    if now == root[pattern[i][j]][0]:
      now = root[pattern[i][j]][1]
    elif now == root[pattern[i][j]][1]:
      now = root[pattern[i][j]][0]
    else:
      break
    if Flag[now] != 0:
      break
    else:
      Flag[now] = 1
      if j == N-2:
        last = True
  if last:
    ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
import itertools
import sys

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

if M < N-1:
  print(0)
  sys.exit()

p = [i for i in range(M)] #0からM-1本目までの道のリスト
root = []
for i in range(M):
  a,b = map(int,input().split())
  root.append([a-1,b-1])

#たどる道の全探索
pattern = list(itertools.permutations(p))
print(pattern)

ans = 0
for i in range(len(pattern)):
  Flag = [0]*N
  Flag[0] = 1
  now = 0
  last = False
  for j in range(N-1):
    if now == root[pattern[i][j]][0]:
      now = root[pattern[i][j]][1]
    elif now == root[pattern[i][j]][1]:
      now = root[pattern[i][j]][0]
    else:
      break
    if Flag[now] != 0:
      break
    else:
      Flag[now] = 1
      if j == N-2:
        last = True
  if last:
    ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
import itertools
import sys

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

if M < N-1:
  print(0)
  sys.exit()

p = [i for i in range(M)] #0からM-1本目までの道のリスト
root = []
for i in range(M):
  a,b = map(int,input().split())
  root.append([a-1,b-1])

#たどる道の全探索
pattern = list(itertools.permutations(p))

ans = 0
for i in range(len(pattern)):
  Flag = [0]*N
  Flag[0] = 1
  now = 0
  last = False
  for j in range(N-1):
    if now == root[pattern[i][j]][0]:
      now = root[pattern[i][j]][1]
    elif now == root[pattern[i][j]][1]:
      now = root[pattern[i][j]][0]
    else:
      break
    if Flag[now] != 0:
      break
    else:
      Flag[now] = 1
      if j == N-2:
        last = True
  if last:
    ans += 1
print(ans)