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:
n,m=map(int,input().split())
lis=[[0 for i in range(n)] for _ in range(n)]
for i in range(m):
	x,y=map(int,input().split())
	lis[x-1][y-1]=1
	lis[y-1][x-1]=1
s=""
k=[]
import itertools
for i in range(n):
	s+=str(i)
for i in itertools.permutations(s):
	k.append(i)
ans=0
for i in range(len(k)):
	if k[i][0]!="1":
		continue
	for j in range(n-1):
		if lis[int(k[i][j])][int(k[i][j+1])]==0:
			break
		elif j==n-2:
			ans+=1
print(ans)

Submission status: Wrong Answer

Solution code:
def dfs(n, cnt):  # ノードのこと
    if visited[n]:
        if cnt == N:
            ans[-1] += 1
            cnt = 0
        return  # 訪問済みならreturnする
    else:
        visited[n] = True
        cnt += 1
    for a in graph[n]:
        dfs(a, cnt)


N, M = map(int, input().split())  # N頂点, M辺存在する

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

for _ in range(M):  # M辺を受け取る
    a, b = map(lambda x: int(x)-1, input().split())
    graph[a].append(b)
    graph[b].append(a)

# print(graph)
ans = [0]
dfs(0, 0)

print(ans[0])

Submission status: Wrong Answer

Solution code:
N,M = tuple(map(int,input().split()))
from collections import defaultdict
graph = defaultdict(list)
for i in range(M):
  a,b = tuple(map(int,input().split()))
  graph[a].append(b)
  graph[b].append(a)
  
# pathを運んで，その中で
queue = [(1,set())]
res = 0
while queue:
  now,prevs = queue.pop()
  if len(prevs) == 1:
      res += 1
  for next_node in graph[now]:
    if next_node not in prevs:
      queue.append((next_node, prevs|{now}))
print(res)

Submission status: Wrong Answer

Solution code:
from itertools import permutations
import sys
input = sys.stdin.readline

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

ver = [[] for _ in range(N)]
# 頂点xから移動できる頂点を格納する
print(ver)

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

ans = 0

for i in permutations(range(1, N)):
    here = 0
    for j in i:
        if j not in ver[here]:
            break
        here = j
    else:
        ans += 1

print(ans)

Submission status: Wrong Answer

Solution code:
import itertools
n, m = map(int, input().split())
ab_list = [tuple(map(int, input().split())) for _ in range(m)]

path_list = sorted(iter for iter in itertools.permutations(range(2, n+1), 2))

counter = 0

for path_i in path_list:
  path = (1, )+path_i
  
  result_list = [True for s_e in zip(path, path[1:]) if tuple(sorted(s_e)) in ab_list]
  
  if sum(result_list) == len(path)-1: counter += 1
    
print(counter)

Submission status: Wrong Answer

Solution code:
n,m= list(map(int, input().split()))
li=[list(map(int,input().split())) for _ in range(m)]
checker=[0 for _ in range(n)]
for i in li:
    checker[i[0]-1]+=1
    checker[i[1]-1]+=1
ans=1
tmp=0
for i in range(n):
    if i==0:
        if checker[i]==2:
            ans*=2
        elif checker[i]>2:
            print(0)
            exit(0)
    else:
        if checker[i]==3:
            tmp+=1
        elif checker[i]>3:
            print(0)
            exit(0)
if tmp==0:
    print(ans)
else:
    print(tmp//2*ans)

Submission status: Wrong Answer

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

G = {k: set() for k in range(N+1)}
for _ in range(M):
    a, b = map(int, input().split())
    # 無向グラフ
    G[a].add(b)
    G[b].add(a)
print(G)

ans = 0
for p in itertools.permutations(range(2, N+1)):
    print(p)
    c = 1
    for n in p:
        if n not in G[c]:
            break
        c = n
    else:
        ans += 1

print(ans)

Submission status: Wrong Answer

Solution code:
import itertools
N,M=map(int,input().split())
edges={tuple(sorted(map(int,input().split()))) for i in range(M)}
ans=0
for i in itertools.permutations(range(2,N+1),N-1):
    l=[1]+list(i)
    ans+=sum(1 for edge in zip(l,l[1:]) if tuple(sorted(edge)) in edges)==N-1
print(0)

Submission status: Wrong Answer

Solution code:
# ABC054c
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

n, m = map(int, input().split())
l = [set() for _ in range(n+1)]
for _ in range(m):
    a, b = map(int, input().split())
    l[a].add(b)
    l[b].add(a)

visited = [False]*(n+1)


def dfs(i, cnt):
    #print(i, cnt)
    if (visited[i]):
        return 1 if cnt == n else 0
    visited[i] = True
    ans = 0
    for j in l[i]:
        ans += dfs(j, cnt+1)
    return ans


print(dfs(1, 0))

Submission status: Wrong Answer

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

# それぞれの要素のつながりを1で表現
A = [[0]*N]*N

visited = [False]*N

for i in range(M):
    a, b = map(int, input().split())
    # インデックスのため -1する
    a -= 1
    b -= 1
    A[a][b] = 1
    A[b][a] = 1

def dfs(node, count):
    # 全てのノードが訪れられていたら ans+=1
    if all(visited):
        return count+1
    
    # 全てのノード間の繋がりでfor文
    for i in range(N):
        # nodeの繋がりがあるか判定。
        if A[node][i] == 0:
            continue
        # 見ているノードが訪れられているか判定。
        if visited[i]:
            continue
        
        # 見ているノード間の繋がりがあり、そのノードが訪れられていないとき。
        visited[i] = True
        count = dfs(i, count)
        # 探索前の状態に戻す
        visited[i] = False

    return count

# 開始地点
visited[0] = True

# 開始地点とcountを引数に
count = dfs(0, 0)

print(count)

Submission status: Wrong Answer

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

A = [[0]*N]*N # それぞれの要素のつながりを1で表現
visited = [False]*N

for i in range(M):
    a, b = map(int, input().split())
    # インデックスのため -1する
    a -= 1
    b -= 1
    A[a][b] = 1
    A[b][a] = 1

def dfs(node, count):
    # 全てのノードが訪れられていたら ans+=1
    if all(visited):
        return count+1
    
    # 全てのノード間の繋がりでfor文
    for i in range(N):
        # nodeの繋がりがあるか判定。
        if A[node][i] == 0:
            continue
        # 見ているノードが訪れられているか判定。
        if visited[i]:
            continue
        
        # 見ているノード間の繋がりがあり、そのノードが訪れられていないとき。
        visited[i] = True
        count = dfs(i, count)
        # 探索前の状態に戻す
        visited[i] = False

    return count

# 開始地点
visited[0] = True

# 開始地点とcountを引数に
count = dfs(0, 0)

print(count)

Submission status: Wrong Answer

Solution code:
from collections import deque

def run():
  N, M = map(int, input().split())
  vertex_dict = {}
  for m in range(M):
    a, b = map(int, input().split())
    vertex_dict.setdefault(a, []).append(b)
    vertex_dict.setdefault(b, []).append(a)
  all_m_list = range(M)
  q = deque([])
  q.append((1, [1]))
  total = 0
  while True:
    if len(q) == 0: break
    now_vertex, visited_list = q.popleft()
    if len(visited_list) == N:
      total += 1
      continue
    next_list = vertex_dict[now_vertex]
    for next_vertex in next_list:
      for visited_vertex in visited_list:
        if next_vertex == visited_vertex: break
      else:
        visited_list.append(next_vertex)
        q.append((next_vertex, visited_list))
  print(total)
        
  
if __name__ == '__main__':
  run()

Submission status: Wrong Answer

Solution code:
from collections import defaultdict as dd
from collections import deque as dq
N, M = map(int, input().split())
e = dd(list)
for _ in range(M):
  u, v = map(int, input().split())
  e[u].append(v)
  e[v].append(u)
dp = [[0] * (N + 1) for _ in range(2 ** N)]
dp[1][1] = 1
Q = dq([])
Q.append((1, 1))
while len(Q):
  i, j = Q.popleft()
  for p in e[j]:
    temp = i ^ (1 << (p - 1))
    if temp > i:
      dp[temp][p] += dp[i][j]
      Q.append((temp, p))
print(sum(dp[2 ** N - 1]))

Submission status: Wrong Answer

Solution code:
# ABC054C - One-stroke Path
from itertools import permutations as perm


def main():
    N, M, *A = map(int, open(0).read().split())
    E = {(i, j) for i, j in zip(A, A[1:])} | {(j, i) for i, j in zip(A, A[1:])}
    ans = 0
    for path in perm(range(2, N + 1), N - 1):  # check all possible paths (O(N!))
        path = (1,) + path
        if all((i, j) in E for i, j in zip(path, path[1:])):
            ans += 1
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
from itertools import permutations
n,m = map(int,input().split())
e = {tuple(sorted(map(int,input().split()))) for _ in range(m)}

ans = 1
for i in permutations(range(2, n+1), n-1):
  l = [1] + list(i)
  ans += sum(1 for j in zip(l, l[1:]) if tuple(sorted(j)) in e) == n-1

print(ans)

Submission status: Wrong Answer

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

ans = 1
for i in permutations(range(2, n+1), n-1):
  l = [1] + list(i)
  ans += sum(1 for j in zip(l, l[1:]) if tuple(sorted(j)) in e) == n-1

print(ans)

Submission status: Wrong Answer

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

ans = 1
for i in permutations(range(2, n+1), n-1):
  l = [1] + list(i)
  ans += sum(1 for j in zip(l, l[1:]) if tuple(j) in e) == n-1

print(ans)

Submission status: Wrong Answer

Solution code:
from itertools import permutations

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

E = []
for i in range(M):
    E.append(tuple(map(int, input().split())))

P = []
if N > 2:
    for p in permutations(range(2, N+1)):
        tmp = [1]
        tmp.extend(list(p))
        P.append(tmp)

ans = 0
for p in P:
    for i in range(1, N):
        exist = False
        for e in E:
            if set(e) == {p[i-1], p[i]}:
                exist = True
                break
        if exist is False:
            break
    else:
        a = 1
        if exist is False:
            break
    if exist:
        ans += 1

print(ans)

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
G = [] * M
for i in range(M):
  G.append([i,list(map(int,input().split()))])
#print(G)

def check(v,t):
  visited[v] = 1
  for u in E[v]:
    if u != t:
      if visited[u] == 1:
        return False
      return check(u,v)
  return True

ans = 0
for i in range(1<<M):
  E = [set() for _ in range(N)]
  for j in range(M):
    if i & (1 << G[j][0]):
      u,v = G[j][1]
      E[u-1].add(v-1)
      E[v-1].add(u-1)
  #print(E)
  visited = [0] * N
  #print(E,check(0,-1),visited)
  if check(0,-1) and sum(visited) == N:
    ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
N, M=(int(i) for i in input().split())
P=[]
for i in range(M):
    P.append([int(i) for i in input().split()])


ans=0
q=[]
s=1

def func(s,Q,r):
    global ans
    for q ,P in Q:
        if r==N-1:
            ans+=1
        n_s=[i for i in q if i!=s][0]
        n_q=[]
        for p in P:
            if n_s in p:
                n_q.append([p, [_p for _p in P if s not in _p]])
        if len(n_q)==0:
            continue
        else:
            func(n_s, n_q, r+1)


for p in P:
    if s in p:
        q.append([p, [_p for _p in P if s not in _p]])
func(s,q,1)
print(ans)

Submission status: Wrong Answer

Solution code:
N, M=(int(i) for i in input().split())
P=[]
for i in range(M):
    P.append([int(i) for i in input().split()])


ans=0
q=[]
s=1

def func(s,Q,r):
    global ans
    for q ,P in Q:
        if r==N-1:
            ans+=1
        n_s=[i for i in q if i!=s][0]
        n_q=[]
        for p in P:
            if n_s in p:
                n_q.append([p, [_p for _p in P if _p!=p]])
        if len(n_q)==0:
            continue
        else:
            func(n_s, n_q, r+1)


for p in P:
    if s in p:
        q.append([p, [_p for _p in P if _p!=p]])
func(s,q,1)
print(ans)

Submission status: Wrong Answer

Solution code:
N, M=(int(i) for i in input().split())
P=[]
for i in range(M):
    P.append([int(i) for i in input().split()])


ans=0
q=[]
s=1

def func(s,Q,r):
    global ans
    for q ,P in Q:
        n_s=[i for i in q if i!=s][0]
        n_q=[]
        for p in P:
            if n_s in p:
                n_q.append([p, [_p for _p in P if _p!=p]])
        if r==N-1 and len(n_q)>0:
            ans+=1
        if len(n_q)==0:
            continue
        else:
            func(n_s, n_q, r+1)


for p in P:
    if s in p:
        q.append([p, [_p for _p in P if _p!=p]])
func(s,q,2)
print(ans)

Submission status: Wrong Answer

Solution code:
N, M=(int(i) for i in input().split())
P=[]
for i in range(M):
    P.append([int(i) for i in input().split()])


ans=0
q=[]
s=1

def func(s,Q,r):
    global ans
    for q ,P in Q:
        n_s=[i for i in q if i!=s][0]
        n_q=[]
        for p in P:
            if n_s in p:
                n_q.append([p, [_p for _p in P if _p!=p]])
        if r==N-1 and len(n_q)>0:
            ans+=1
        else:
            func(n_s, n_q, r+1)


for p in P:
    if s in p:
        q.append([p, [_p for _p in P if _p!=p]])
func(s,q,2)
print(ans)

Submission status: Wrong Answer

Solution code:
import itertools
N,M=map(int,input().split())
L=[[]]*N
for _ in range(M):
    a,b=map(int,input().split())
    L[a-1].append(b-1)
    L[b-1].append(a-1)
cnt=0
for i in itertools.permutations(range(N),N):
    if i[0]==0:
        for j in range(N):
            if j==N-1:
                cnt+=1
                break
            if not (i[j+1] in L[i[j]]):
                break
print(cnt)

Submission status: Wrong Answer

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

used = [0 for i in range(n)]
ans = 0
print(link)
def dfs(now, prev):
    global ans

    if sum(used) == n:
        #print('+1')
        ans += 1

    for i in link[now]:
        #print(now,i,used)
        if i != now and used[i] == 0:
            used[i] = 1
            #print('a')
            dfs(i, now)
            #print('b')
            used[i] = 0
            #print('c')

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

Submission status: Wrong Answer

Solution code:
import copy

#深さ優先探索
def dfs(V_st_tmp, count, node, E_st_tmp):
    #終了条件
    if len(V_st_tmp)==1:
  
        return 1

    for j in V_st_tmp:
        V_st_copy = copy.copy(V_st_tmp)
        E_st_copy = copy.copy(E_st_tmp)
        if {node, j} in E_st_copy:
            E_st_copy.remove({node, j})
            V_st_copy.remove(node)
            count = dfs(V_st_copy, count, j, E_st_copy)

    return count

V, E  = map(int, input().split())

#頂点の集合3 3
V_set = [v for v in range(V)]
V_set_tmp = copy.copy(V_set)
E_set = []
#無向グラフの構築
for i in range(E):
    a,b   = map(int, input().split())
    E_set.append({a-1,b-1})

sm = 0

#全探索
for i in range(2, V+1, 1):
    V_set_tmp = copy.copy(V_set)
    E_set_tmp = copy.copy(E_set)
    if {0, i-1} in E_set_tmp:
        V_set_tmp.pop(0)
        E_set_tmp.remove({0, i-1})
        sm = sm + dfs(V_set_tmp, sm, i-1, E_set_tmp)

print(sm)

Submission status: Wrong Answer

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

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

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

    #print(bisect.bisect_left(g[a],b))
    #g[a][] = b
    #g[a].append(b)
    #g[b].append(a)

#g[4].sort()
    
ans = 0

def dfs(x,check):
    #print(check,x)
    ans = 0
    if not False in check:
        print(ans)
        return 1
        #check[x] = 0
        #print(x)
    #print(check)
    for i in g[x]:
        if check[i] == True:
            continue
        #print(i,check)
        check[i] = True
        ans += dfs(i,check)
        check[i] = False
    
    return ans
    
check = [False] * (n+1)
check[0] = True
check[1] = True

print(dfs(1,check))

Submission status: Wrong Answer

Solution code:
import itertools

N, M = map(int,input().split())
edges = {tuple(sorted(map(int,input().split()))) for i in range(M)}
#print(edges)
ans = 0
num = 0
for i in itertools.permutations(range(2,N+1)):
  #print(i)
  l = [1] + list(i)
  for edge in zip(l,l[1:]):
    #print(edge)
    if tuple(sorted(edge)) in edges:
      num += 1
      if num == N-1:
        ans += 1
        num = 0
  #print(l,l[1:])
  #ans += sum(1 for edge in zip(l,l[1:]) if tuple(sorted(edge)) in edges)==N-1
  #print(ans)
print(ans)         
#a = sum(1 for edge in zip(l,l[1:]) if tuple(sorted(edge)) in edges) == N-1

Submission status: Wrong Answer

Solution code:
import itertools

N, M = map(int,input().split())
edges = {tuple(sorted(map(int,input().split()))) for i in range(M)}
print(edges)
ans = 0
num = 0
for i in itertools.permutations(range(2,N+1)):
  #print(i)
  l = [1] + list(i)
  for edge in zip(l,l[1:]):
    #print(edge)
    if tuple(sorted(edge)) in edges:
      num += 1
      if num == N-1:
        ans += 1
        num = 0
  #print(l,l[1:])
  #ans += sum(1 for edge in zip(l,l[1:]) if tuple(sorted(edge)) in edges)==N-1
  #print(ans)
print(ans)         
#a = sum(1 for edge in zip(l,l[1:]) if tuple(sorted(edge)) in edges) == N-1

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
from collections import deque

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

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

q = deque([])
q.append(0)

ans = 0
def dfs(n, q):
  print (n, D[n], q)
  global ans
  q.append(n)
  if len(q) == N:
    ans += 1
  else:
    for b in D[n]:
      if b not in q:
        dfs(b, q)
        q.pop()

dfs(0, [])
print (ans)

Submission status: Wrong Answer

Solution code:
import itertools
N,M = map(int,input().split())
r = []
for _ in range(M):
    add = list(map(int,input().split()))
    r.append(add)
    r.append(add[::-1])
A = [i for i in range(2,N + 1)]
A = list(itertools.permutations(A,N - 1))
ans = 0
for check in A:
    q = 0
    p = [1] + list(check)
    for c in range(N - 1):
        if p[c:c + 2] in r:
            q += 1
    if q == N - 1:
        ans += 1
    print(q)
print(ans)

Submission status: Wrong Answer

Solution code:
input()

Submission status: Wrong Answer

Solution code:
import itertools
N,M=map(int,input().split())
edges={tuple(sorted(map(int,input().split()))) for i in range(M)}
print(edges)
ans=0
for i in itertools.permutations(range(2,N+1),N-1):
    l=[1]+list(i)
    ans+=sum(1 for edge in zip(l,l[1:]) if tuple(sorted(edge)) in edges)==N-1
print(l)
print(ans)

Submission status: Wrong Answer

Solution code:
import itertools

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

l = list()
for m in range(M):
    l.append(tuple(map(int, input().split())))

ans = 0
for p in itertools.permutations(l):
    nodes = {1}
    next_node = 0
    for i, pair in enumerate(p):
        if i == 0:
            if 1 != pair[0]:
                break
            else:
                next_node = pair[1]
                nodes.add(pair[1])

        elif len(nodes) == N:
            ans += 1
            break

        else:
            if pair[0] == next_node and pair[1] not in nodes:
                next_node = pair[1]
                nodes.add(pair[1])
            elif pair[1] == next_node and pair[0] not in nodes:
                next_node = pair[0]
                nodes.add(pair[0])
            else:
                break

print(ans)

Submission status: Wrong Answer

Solution code:
import itertools
n, m = map(int, input().split())
ab = {}
for i in range(n+1):
    ab[i] = []
for i in range(m):
    a, b = map(int, input().split())
    ab[a].append(b)
    ab[b].append(a)
print(ab) 
count = 0
 
for values in list(itertools.permutations(range(2, n+1))):
    pre = 1
    for i, v in enumerate(values):
        if(v not in ab[pre]):
            break
        if i == n-2:
            count += 1
        pre = v

print(count)

Submission status: Wrong Answer

Solution code:
n,m = map(int,input().split())
path = list([False] * n for _ in range(n))
for i in range(m):
  a,b = map(int,input().split())
  a -= 1
  b -= 1
  path[a][b] = True
  path[b][a] = True
ans = 0
import itertools
for i in itertools.permutations(range(n),n):
  if i[0] == 0:
    for j in range(n):
      if j == n-1:
        ans += 1
        break
      if not path[j][j+1]:
        break
print(ans)

Submission status: Wrong Answer

Solution code:
import copy
def dfs(cur_node, pre_node, Node_num, map, l):
    #全てのノードを見たとき

    if Node_num == N or cur_node <= 0 or cur_node >= N:
        return
    elif l[pre_node][cur_node]==0: #飛んだ先が、Trueの時
        return
    elif map[cur_node]==True:
        return

    map[cur_node]=True

    #このTrueは妥当か? pre_node以外に行き場所ばない場合戻る
    count = 0
    for i in range(N):
        if l[pre_node][i] == 0 and pre_node != i:
            count = count + 1

    if count ==N-2:
        map[cur_node]=False
        return

    for i in range(N):
        if i != cur_node:
            dfs(i, cur_node, Node_num+1, map, l)


S = input()
S = list(map(int, S.split()))

N = S[0]
M = S[1]


map = [False]*N
map[0] = True

lst = []

for i in range(N):
    lst.append([0]*N)

for i in range(M):
    S = input()
    S = list(S.split())
    idx1 = int(S[0])
    idx2 = int(S[1])
    lst[idx1-1][idx2-1] = 1
    lst[idx2-1][idx1-1] = 1


graph_count = 0
#全探索
for i in range(1, N, 1):
    map_copy = copy.copy(map)
    lst_copy = copy.copy(lst)

    dfs(i, 0, 0, map_copy, lst_copy)
    count = 0

    for i in map_copy:
        if i == True:
            count = count + 1
    if count == N:
        graph_count = graph_count + 1

print(graph_count)

Submission status: Wrong Answer

Solution code:
import copy
def dfs(cur_node, pre_node, Node_num, map, l):
    #全てのノードを見たとき

    if Node_num == N or cur_node <= 0 or cur_node >= N:
        return
    elif l[pre_node][cur_node]==0: #飛んだ先が、Trueの時
        return
    elif map[cur_node]==True:
        return

    print(pre_node)
    print(cur_node)
    map[cur_node]=True
    for i in range(N):
        if i != cur_node and map[pre_node] == True:
            dfs(i, cur_node, Node_num+1, map, l)


S = input()
S = list(map(int, S.split()))

N = S[0]
M = S[1]


map = [False]*N
map[0] = True

lst = []

for i in range(N):
    lst.append([0]*N)

for i in range(M):
    S = input()
    S = list(S.split())
    idx1 = int(S[0])
    idx2 = int(S[1])
    lst[idx1-1][idx2-1] = 1
    lst[idx2-1][idx1-1] = 1


graph_count = 0
#全探索
for i in range(1, N, 1):
    map_copy = copy.copy(map)
    lst_copy = copy.copy(lst)

    dfs(i, 0, 0, map_copy, lst_copy)
    count = 0

    for i in map_copy:
        if i == True:
            count = count + 1
    if count == N:
        graph_count = graph_count + 1

print(graph_count)

Submission status: Wrong Answer

Solution code:
import copy
def dfs(cur_node, pre_node, Node_num, map, l):
    #全てのノードを見たとき

    if Node_num == N or cur_node <= 0 or cur_node >= N:
        return
    elif l[pre_node][cur_node]==0: #飛んだ先が、Trueの時
        return
    elif map[cur_node]==True or map[pre_node]==True:
        return
        
    print(pre_node)
    print(cur_node)
    map[cur_node]=True
    for i in range(N):
        if i != cur_node:
            dfs(i, cur_node, Node_num+1, map, l)


S = input()
S = list(map(int, S.split()))

N = S[0]
M = S[1]


map = [False]*N
map[0] = True

lst = []

for i in range(N):
    lst.append([0]*N)

for i in range(M):
    S = input()
    S = list(S.split())
    idx1 = int(S[0])
    idx2 = int(S[1])
    lst[idx1-1][idx2-1] = 1
    lst[idx2-1][idx1-1] = 1


graph_count = 0
#全探索
for i in range(1, N, 1):
    map_copy = copy.copy(map)
    lst_copy = copy.copy(lst)

    dfs(i, 0, 0, map_copy, lst_copy)
    count = 0

    for i in map_copy:
        if i == True:
            count = count + 1
    if count == N:
        graph_count = graph_count + 1

print(graph_count)

Submission status: Wrong Answer

Solution code:
import copy
def dfs(cur_node, pre_node, Node_num, map, l):
    #全てのノードを見たとき

    if Node_num == N or cur_node <= 0 or cur_node >= N:
        return
    elif l[pre_node][cur_node]==0: #飛んだ先が、Trueの時
        return
    elif map[cur_node]==True:
        return

    map[cur_node]=True
    for i in range(N):
        if i != cur_node:
            dfs(i, cur_node, Node_num+1, map, l)


S = input()
S = list(map(int, S.split()))

N = S[0]
M = S[1]


map = [False]*N
map[0] = True

lst = []

for i in range(N):
    lst.append([0]*N)

for i in range(M):
    S = input()
    S = list(S.split())
    idx1 = int(S[0])
    idx2 = int(S[1])
    lst[idx1-1][idx2-1] = 1
    lst[idx2-1][idx1-1] = 1


graph_count = 0
#全探索
for i in range(1, N, 1):
    map_copy = copy.copy(map)
    lst_copy = copy.copy(lst)

    dfs(i, 0, 0, map_copy, lst_copy)
    count = 0

    for i in map_copy:
        if i == True:
            count = count + 1
    if count == N:
        graph_count = graph_count + 1

print(graph_count)

Submission status: Wrong Answer

Solution code:
from itertools import permutations

n,m = map(int,input().split(' '))
choices = permutations(range(1,n))
nords = [[]for _ in range(n)]
for i in range(m):
    a, b = map(lambda x : int(x)-1,input().split(" "))
    nords[a].append(b)
    nords[b].append(a)


ans = 0
for choice in choices:
    for i,nextnord in enumerate(choice):
        if i== n -2:
            ans += 1
            
        if not nextnord in nords[i]:
            break
       

print(ans)

Submission status: Wrong Answer

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


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


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

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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


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


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

if __name__ == '__main__':
    main()