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 = list(map(int, input().split()))
paths = [list(map(int, input().split())) for _ in range(m)]

visited = [1]
rest = [i for i in range(2, n + 1)]
ans = 0

def dfs(num):
    if rest == []:
        print(visited)
        global ans
        ans += 1
    for i in range(m):
        if num in paths[i]:
            other = paths[i][1 - paths[i].index(num)]
            if other in rest:
                # print(other)
                visited.append(other)
                rest.remove(other)
                # print(visited, rest)
                dfs(other)
                visited.remove(other)
                rest.append(other)

dfs(1)
print(ans)

Submission status: Wrong Answer

Solution code:
def bfs(g, n):
	tovisit = []
	for i in range(0, n):
		tovisit.append(i)
	queue = []
	tovisit.remove(0)
	queue.append([0, tovisit])
	cnt = 0

	while queue != []:
		status = queue.pop(0)
		now = status[0]
		currenttovisit = status[1]
		if currenttovisit == []: cnt = cnt + 1
		else:
			for i in range(0, n):
				newtovisit = currenttovisit
				if i in currenttovisit and graph[now][i]:
					newtovisit.remove(i)
					queue.append([i, newtovisit])
	return cnt

N, M = map(int, raw_input().split())
graph = []
for i in range(0, N):
	arrow = []
	for j in range(0, N):
		arrow.append(False)
	graph.append(arrow)

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

print bfs(graph, N)

Submission status: Wrong Answer

Solution code:
def dfs(now,flags):
    global graph

    if len(flags) == len(graph)-1:
        return 1

    flags.add(now)
    ans = 0
    for vis in graph[now]:
        if not vis in flags:
            #print("now:",now,"vis:",vis,"flags:",flags)
            ans += dfs(vis,flags)
    #flags.remove(now)
    return ans

nums = [int(x) for x in input().split()]
N, M = nums[0], nums[1]
graph = {i:[] for i in range(1,N+1)}

for i in range(M):
    nums = [int(x) for x in input().split()]
    graph[nums[0]].append(nums[1])
    graph[nums[1]].append(nums[0])

print(dfs(1,set()))

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
dic = {i+1:[] for i in range(N)}

for i in range(M):
    f,g = map(int,input().split())
    dic[f].append(g)

visited = [0 for i in range(N)]

stack = [[1,1]]
root = 0
while len(stack) >0:
    now = stack[-1][0]
    length = stack[-1][1]
    del stack[-1]
    for next in dic[now]:
        if length +1<N-1:
            stack.append([next,length+1])
        else:
            root += 1

print(root)

Submission status: Wrong Answer

Solution code:
def dfs(g, v, i):
    if len(v) == len(g) - 1: return 1
    v.add(i)
    c = 0
    for u in g[i]:
        if u not in v: c += dfs(g, v, u)
    return c

n, m = map(int, input().split())
g = [list() for _ in range(n)]
for _ in range(m):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    g[a].append(b)
    g[b].append(a)
print(dfs(g, set(), 0))

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
path=[[0]*n for i in range(n)]
for i in range(m):
    a,b=map(int,input().split())
    path[a-1][b-1]=1
    path[b-1][a-1]=1#隣接グラフを作成
visited=[0]*n#どこを通ったか記憶
visited[0]=1#１は最初に通る
def dfs(position,visited,n):#深さ優先探索
    all_visited=1
    for i in range(n):
        if visited[i]==0:
            all_visited=0#行ったことがない点があれば０
            break#どこかで見つかったらループ終了
    if all_visited==1:
        return 1#全部回れたら１回カウント
    count=0#経路の個数をカウント
    for next in range(n):#次に移動する点
        if path[position][next]==0:
            continue#道がなければ次へ
        if visited[next]==1:
            continue#行ったことがあれば次へ
        visited[next]=1
        count+=dfs(next,visited,n)
        #visited[i]=0#行った記録を消去して前のループに戻る
    visited[position]=0

    return count
print(dfs(0,visited,n))

Submission status: Wrong Answer

Solution code:
def i1():
 return int(input())
def i2():
 return [int(i) for i in input().split()]
[n,m]=i2()
e=[[] for i in range(n)]
for i in range(m):
 x=i2()
 e[x[0]-1].append(x[1]-1)
 e[x[1]-1].append(x[0]-1)
dp=[[0 for i in range(n)] for j in range(1<<n)]
def d(v,s):
  dp[s][v]=1
  q=[[s,v]]
  while len(q):
   w=q.pop(0)
   v=w[1]
   s=w[0]
   for i in range(len(e[v])):
    if s-(1<<e[v][i])>0:
     dp[s][v]+=dp[s-(1<<v)][e[v][i]]
    if s&(1<<e[v][i])==0:
     q.append([s | (1<<e[v][i]),e[v][i]])
  
  

d(0,0|(1<<0))
print(sum(dp[(1<<n)-1]))

Submission status: Wrong Answer

Solution code:
def i1():
 return int(input())
def i2():
 return [int(i) for i in input().split()]
[n,m]=i2()
e=[[] for i in range(n)]
for i in range(m):
 x=i2()
 e[x[0]-1].append(x[1]-1)
 e[x[1]-1].append(x[0]-1)
dp=[[0 for i in range(n)] for j in range(1<<n)]
def d(v,s):
  dp[s][v]=1
  q=[[s,v]]
  while len(q):
   w=q.pop(0)
   v=w[1]
   s=w[0]
   for i in range(len(e[v])):
    if s&(1<<e[v][i])==0:
     dp[s | 1<<e[v][i]][e[v][i]]+=dp[s][v]
     q.append([s | (1<<e[v][i]),e[v][i]])
  

d(0,0|(1<<0))
print(sum(dp[(1<<n)-1]))

Submission status: Wrong Answer

Solution code:
def i1():
 return int(input())
def i2():
 return [int(i) for i in input().split()]
[n,m]=i2()
e=[[] for i in range(n)]
for i in range(m):
 x=i2()
 e[x[0]-1].append(x[1]-1)
 e[x[1]-1].append(x[0]-1)
dp=[[0 for i in range(n)] for j in range(1<<n)]
def d(v,s):
  
  for i in range(len(e[v])):
   if s&(1<<e[v][i])==0:
    dp[s | 1<<e[v][i]][e[v][i]]+=dp[s][v]
    d(e[v][i],s | (1<<e[v][i]))
  
dp[0|(1<<0)][0]=1
d(0,0|(1<<0))
print(sum(dp[(1<<n)-1]))

Submission status: Wrong Answer

Solution code:
def i1():
 return int(input())
def i2():
 return [int(i) for i in input().split()]
[n,m]=i2()
e=[[] for i in range(n)]
for i in range(m):
 x=i2()
 e[x[0]-1].append(x[1]-1)
 e[x[1]-1].append(x[0]-1)
dp=[[0 for i in range(n)] for j in range(1<<n)]
def d(v,s):
  
  for i in range(len(e[v])):
   if s&1<<e[v][i]==0:
    dp[s | 1<<e[v][i]][e[v][i]]+=dp[s][v]
    d(e[v][i],s | 1<<e[v][i])
  
dp[0|1<<0][0]=1
d(0,0|1<<0)
print(sum(dp[(1<<n)-1]))

Submission status: Wrong Answer

Solution code:
n,m=[int(i) for i in input().split()]
es=set()
for _ in range(m):
    u,v=map(int,input().split())
    u,v=u-1,v-1
    es|={(u,v),(v,u)}


p=[[0]]
x=0
while p:  
  p1=p.pop()
  for l0,l1 in es:
    if l0==p1[len(p1)-1] and l1 not in p1:
      if len(p1)==m-1:
        x+=1
      else:
        p.append(p1+[l1])

print(x)

Submission status: Wrong Answer

Solution code:
n,m = map(int,input().split())
graph = [[0]*(n) for i in range(n)]

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

print(graph)
visited = [True] + [False]*(n-1)
ans = 0


def dfs(x):
    global ans
    global visited
    
    if all(visited):
        ans += 1
        return
    
        
    for j in [j for j,v2 in enumerate(graph[x]) if v2 == 1 and not visited[j]]:
        visited[j] = True
        dfs(j)
        visited[j] = False

dfs(0)
print(ans)

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
if m==0:
    print(0)
    exit()
ans=[[] for i in range(n)]
for i in range(m):
    a,b=map(int,input().split())
    ans[a-1].append((b-1))
    ans[b-1].append((a-1))
v=[]#全ての点を訪問済み
def dfs(now,visited=[]):
    global v
    if len(visited)==n:
        v.append([visited])
        return
    for j in ans[now]:
        if j not in visited:
            dfs(j,visited+[j])
print(v)
dfs(0,[0])
print(len(v))

Submission status: Wrong Answer

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

def dfs(v):
    if vis==[1]*n:
        return 1
    count=0
    for i in edges[v]:
        if vis[i]==0:
            vis[i]=1
            count+=dfs(i)
            vis[i]=0
        else:
            return count
print(dfs(0))

Submission status: Wrong Answer

Solution code:
import itertools
import collections
N,M=map(int,raw_input().split())
#print N,M
a=[map(int,raw_input().split()) for i in range(M)]
#print a
b=list(itertools.permutations(range(1,N+1)))
#print b

cnt=0
for i in b:
	if i[0]!=1:
		continue
	c=[]
	for j in i:
		#print i,j
		if len(c)<2:
			c.append(j)

		if len(c)==2:
			if c in a or c[::-1] in a:
				cnt=1
			else:
				cnt=0
				break
			c.pop(0)
	cnt+=1
print cnt

Submission status: Wrong Answer

Solution code:
import itertools
import collections
N,M=map(int,raw_input().split())
#print N,M
a=[map(int,raw_input().split()) for i in range(M)]
#print a
b=list(itertools.permutations(range(1,N+1)))
#print b

cnt=0
for i in b:
	if i[0]!=1:
		continue
	c=[]
	for j in i:
		#print i,j
		if len(c)<2:
			c.append(j)
		else:
			if c in a or c[::-1] in a:
				cnt=1
			else:
				cnt=0
				break

			c.pop(0)
			c.append(j)
	cnt+=1
print cnt

Submission status: Wrong Answer

Solution code:
import itertools
import collections
import heapq
N,M=map(int,raw_input().split())
#print N,M
a=[tuple(map(int,raw_input().split())) for i in range(M)]
#print a
b=list(itertools.combinations(a,N-1))
#print b


cnt=0
for i in b:
	c=[]
	for j,k in i:
		#print j,k
		c.append(j)
		c.append(k)
	#print c
	t_c=collections.Counter(c)
	t_c_v = collections.Counter(c).values()
	t_c_v = map(lambda n:n*-1, t_c_v)
	#print t_c, t_c_v
	heapq.heapify(t_c_v)
	if t_c[1]==1 and t_c_v[0]>=-2:
		cnt+=1

print cnt

Submission status: Wrong Answer

Solution code:
import itertools
import collections
N,M=map(int,raw_input().split())
#print N,M
a=[tuple(map(int,raw_input().split())) for i in range(M)]
#print a
b=list(itertools.combinations(a,N-1))
#print b


cnt=0
for i in b:
	c=[]
	for j,k in i:
		#print j,k
		c.append(j)
		c.append(k)
	#print c
	t_c=collections.Counter(c)
	t_c_v=(collections.Counter(c)).values()
	#print t_c,t_c_v
	if t_c[1]==1:
		for m in t_c_v:
			if m>=3:
				break
		else:
			cnt+=1

print cnt

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)

memo = {}
All_used = (1 << N) -1

def dfs(v, used):
    if used == All_used:
        return 1
    
    key = (v, used)
    if key in memo:
        return memo[key]
    
    ans = 0
    for u in g[v]:
        if (used >> u) & 1 == 1:
            continue
        
        used ^= (1 << u)
        ans += dfs(u, used)
        
    memo[key] = ans
    return ans

print(dfs(0, 1))

Submission status: Wrong Answer

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

graph = [list() for i in range(N+1)]

for i in range(M):
    a, b = list(map(int, input().split(" ")))
    graph[a].append(b)
    graph[b].append(a)
    
def DFS(node, prev, visited):
    visited.append(node)
    if len(visited) == N:
        return 1
    
    res = 0
    for edge in graph[node]:
        if edge == prev:
            continue
        elif edge in visited:
            continue
        res += DFS(edge, node, visited)
        
    return res

print(DFS(1, 0, []))

Submission status: Wrong Answer

Solution code:
# Suplemental: ABC54 C
N, M = map(int, input().split())
E = [[False for i in range(N+1)] for j in range(N+1)]
for i in range(1,M+1):
    a,b = map(int, input().split())
    E[a][b] = True
    E[b][a] = True
    
num_of_paths = 0
def paths(passed, start):
    for i, e in enumerate(E[start]):
        i += 1
        if e == False:
            continue
        if i in passed:
            continue
        
        passed.append(start)
        if len(passed):
            global num_of_paths
            num_of_paths += 1
        else:
            paths(passed, i) # visit e
    
paths([], 1)
print(num_of_paths)

Submission status: Wrong Answer

Solution code:
# Subplemental: ABC54 C
N, M = map(int, input().split())
E = [[False for i in range(N+1)] for j in range(N+1)]
for i in range(1,M+1):
    a,b = map(int, input().split())
    E[a][b] = True
    E[b][a] = True

def paths(passed, start):
    num_of_paths = 0
    for i, e in enumerate(E[start]):
        i += 1
        if e == False:
            continue
        if i in passed: # e has been visited already
            continue
        
        # e has not been visited yet
        passed.append(start) # add current start to passed
        if len(passed):
            num_of_paths += 1
        else:
            num_of_paths += paths(passed, i) # visit e
    return num_of_paths
    
passed = []
print(paths(passed, 1))

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python
from itertools import permutations
N,M=map(int,raw_input().split())
path=[]
all_list=[]
count=0
 
for i in range(M):
    path.append(map(int,raw_input().split()))
 
NN=N*(N-1)/2
all_list=map(list,permutations(range(1,NN+1),2))
for i in range(len(all_list)):
    for j in range(M):
        if all_list[i]==path[j]:
            count=count+1
 
print count

Submission status: Wrong Answer

Solution code:
import itertools


n, m = map(int, input().split())
road = [[0] * n for i in range(n)]

graph = [[] for i in range(n)]
for j in range(m):
    x, y = map(int, input().split())
    road[x - 1][y - 1] += 1
    road[y - 1][x - 1] += 1
    graph[x-1].append(y-1)
    graph[y-1].append(x-1)
#print(road)
#print(graph)

count = 0

for can in itertools.permutations(range(n)):
    if can[0] != 0:
        break
#    print(can)
    plus = 1
    for k in range(n-1):
#        print(road[can[k]][can[k + 1]])
        plus *= road[can[k]][can[k + 1]]
    count += plus


def dfs(node, prev, visited):
    visited.append(node)
    if len(visited) == n:
        return 1

    res = 0
    for edge in graph[node]:
        if edge == prev:
            continue
        if edge in visited:
            continue
        res += dfs(edge, prev, visited)

    return res

dfs = dfs(0, -1, [])

if count == dfs:
    print(dfs)

Submission status: Wrong Answer

Solution code:
N=7
M=7
_A=[1,2,3,4,4,5,6]
_B=[3,7,4,5,6,6,7]
A=_A+_B
B=_B+_A


def gen_get_to(_fr):
    global A
    global B
    global nodes
    global step
    for itr in range(0,len(A)):
        if A[itr]==_fr:
            if not B[itr] in nodes[0:step]:
                yield B[itr]

def move(): #returns whether "move" succeeded or not
    global nodes
    global possible_memo
    global step
    global counter
    global N
    global end_flag
    try:
        _=next(possible_memo[step])
        nodes[step+1]=_
        step+=1
        #print("success move to {}".format(nodes[step]))
        #print("map: {}".format(nodes[0:step+1]))
        #print("I am at {}th node".format(step+1))
        if step==N-1:
            counter+=1
            #print('REACHED GOAL!!!')
        possible_memo[step]=gen_get_to(nodes[step])
    except StopIteration:
        step-=1
        #print("failed to move")
        if not step==-1:
            pass#print("map: {}".format(nodes[0:step+1]))
            #print("I am at {}th node".format(step+1))
        if step==-1:
            #print("I fell from the first node")
            end_flag=True

nodes=[0]*N
possible_memo=[0]*N
counter=0
step=0
nodes[step]=1
possible_memo[step]=gen_get_to(nodes[0])
end_flag=False

while not end_flag:
    move()


print(counter)

Submission status: Wrong Answer

Solution code:
import numpy as np

class Node:
    def __init__(self, id):
        self.id = id
        self.nexts = []
        self.visited = False

    def add_next(self, node):
        self.nexts.append(node)

def saiki(node, count, judge):
    node.visited = True
    judge[node.id] = True
    if(all(judge)):
        count[0]+=1

    for next in node.nexts:
        if(not next.visited):
            saiki(next, count, judge)
    node.visited = False
    judge[node.id] = False

if __name__=="__main__":
    inputs = lambda : input().replace("\n", "").split(" ")
    N, M = [int(number) for number in inputs()]

    nodes = [Node(i) for i in range(N)]
    for i in range(N):
        x, y = [int(number)-1 for number in inputs()]
        nodes[x].add_next(nodes[y])
        nodes[y].add_next(nodes[x])

    judge = [False]*N
    count = [0]
    saiki(nodes[0], count , judge)
    print(count[0])

Submission status: Wrong Answer

Solution code:

def ggg(now, edges, vertices, N):
#    print edges
#    print vertices
    if len(vertices)==N:
#        print 'found'
        return 1
    cnt = 0
    for i in xrange(len(edges)):
        nexte=-1
        if now == edges[i][0]:
            nexte=1
        elif now == edges[i][1]:
            nexte=0
        if nexte != -1:
#            print 'now' + str(i)
            e=edges[:]
            v=vertices.copy()
            v.add(edges[i][0])
            v.add(edges[i][1])
            e.pop(i)
            c = ggg(edges[i][nexte], e, v, N)
            cnt += c
    return cnt


N,M=map(int, raw_input().split())
#print N,M
E=[]
for i in xrange(M):
    E.append(map(int, raw_input().split()))
#print E
V=set()
cnt = ggg(1, E, V, N)
print cnt

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

def dfs(graph, start, end):
    stack = [start]
    visited = []
    while stack:
        label = stack.pop(0)
        if label == end:
            visited.append(label)
            return visited
        if label not in visited:
            visited.append(label)
            stack = graph.get(label, []) + stack
    return visited

cnt = 0
n,m = map(int,input().strip().split())
edges = defaultdict(list)
for _ in range(m):
    a,b = map(int,input().strip().split())
    edges[a].append(b)
    for i in range(2,n+1):
        res = dfs(edges,1,i)
        if sorted(res) == sorted(list(range(1,n+1))):
            cnt += 1

print(cnt)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

def dfs(graph, start, end):
    stack = [start]
    visited = []
    while stack:
        label = stack.pop(0)
        if label == end:
            visited.append(label)
            return visited
        if label not in visited:
            visited.append(label)
            stack = graph.get(label, []) + stack
    return visited

cnt = 0
n,m = map(int,input().strip().split())
edges = defaultdict(list)
for _ in range(m):
    a,b = map(int,input().strip().split())
    edges[a].append(b)
    for i in range(2,n+1):
        res = dfs(edges,1,i)
        if set(res) == set(list(range(n+1))):
            cnt +=1

print(cnt)

Submission status: Wrong Answer

Solution code:
n,m = map(int, raw_input().split())
edges = {}

# setting up the graph
for i in range(0, m):
	a,b = map(int, raw_input().split())
	if a not in edges:
		edges[a] = set([b])
	else:
		set_a = edges[a]
		set_a.add(b)
		edges[a] = set_a
	if b not in edges:
		edges[b] = set([a])
	else:
		set_b = edges[b]
		set_b.add(a)
		edges[b] = set_b

def search_wrapper():
	visited = []
	total = 0
	def dfs_search(visited, node):

		if len(visited) == n:
			return 1
		else:
			total = 0
			children = edges[node]
			for x in children:
				if x not in visited:
					result = dfs_search(visited+[x], x)
					if result:
						total+=1
		return total	
	total = dfs_search([], 1)
	print total
search_wrapper()

Submission status: Wrong Answer

Solution code:
import itertools

n,m = map(int,raw_input().split())
al = [[] for i in xrange(n)]
for i in xrange(m):
	a,b = map(int,raw_input().split())
	a = a-1
	b = b-1
	al[a].append(b)
	al[b].append(a)

count = 0
perms = list(itertools.permutations(range(n)))
for perm in perms:
	if perm[0] == 1:
		pathexist = True
		for i in range(len(perm)-1):
			if (perm[i] not in al[perm[i+1]]) or (perm[i+1] not in al[perm[i]]):
				pathexist = False
		if pathexist:
			count += 1
print count

Submission status: Wrong Answer

Solution code:
from copy import deepcopy as dcopy
def main():
    global count,N,M,edges,stack
    N, M = map(int, input().split())
    edges = [[0]*N for n in range(N)]
    for m in range(M):
        a,b = map(lambda x:int(x)-1,input().split())
        edges[a][b] = 1
        edges[b][a] = 1

    count = 0
    stack = [[[0], [0]]]
    while len(stack) != 0:
        tansaku = stack.pop()
        next_list = [n for n,v in enumerate(edges[tansaku[0][-1]]) if v == 1]
        search(tansaku, next_list)
    print(count)

def search(tansaku, next_list):
    global count, stack
    for node in next_list:
        tmp_tansaku = dcopy(tansaku)
        tmp_node = tmp_tansaku[0]
        houmonzumi = tmp_tansaku[1]
        if node in houmonzumi:
            pass
        else:
            houmonzumi.append(node)
            if len(houmonzumi) == N:
                count += 1
            else:
                tmp_node.append(node)
                stack.append([tmp_node, houmonzumi])

Submission status: Wrong Answer

Solution code:
from copy import deepcopy



def wfs(tree, root, node_num):
    lost_list = [root]

    def _wfs(tree, root, lost_list) -> int:
        if len(lost_list) == node_num:
            print(lost_list)
            return 1
        counter = 0
        for i in tree[root]:
            if i not in lost_list:
                tmp = deepcopy(lost_list)
                tmp.append(i)
                counter += _wfs(tree, i, tmp)
        return counter

    return _wfs(tree, 0, lost_list)


n, m = input().rstrip().split()
n, m = int(n), int(m)
v = [list() for i in range(n)]
for _ in range(m):
    line = [int(i) - 1 for i in input().rstrip().split()]
    v[line[0]].append(line[1])
    v[line[1]].append(line[0])

print(wfs(v, 0, n))

Submission status: Wrong Answer

Solution code:
from itertools import permutations

n,m=map(int,input().split())
es=set()
for _ in range(m):
    u,v=map(int,input().split())
    es|={(u-1,v-1),(v-1,u-1)}

print(sum(all((u,v) in es for u,v in zip(p,p[1:]))
          for p in permutations(range(n)) if p[0]))

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
from queue import Queue

q = Queue()
N, M = [int(n) for n in input().split()]
graph = {n:[] for n in range(1, N+1)}

for m in range(M):
    a, b = [int(n) for n in input().split()]
    graph[a].append(b)
    graph[b].append(a)

end = 0
for n in range(2, N+1):
    if len(graph[n]) == 1:
        end = n

ok = []
q.put([1, []])

while not q.empty():
    point, past = q.get()
    for d in graph[point]:
        if not d in past:
            if len(past + [point, d]) == M:
                ok.append(past + [point, d])
            else:
                q.put([d, past+[point]])

print(len(ok))

Submission status: Wrong Answer

Solution code:
import copy

data = raw_input()

n,m = map(int,data.split(" "))

db = []
ans = 0

def search(pos,vis):
  global db
  global ans
  global n,m
  for x in db:
    if x[0] == pos:
      if x[1] not in vis:
        if len(vis) == n-1:
          ans = ans + 1
          return
        vis2 = copy.deepcopy(vis)
        vis2.append(x[1])
        search(x[1],vis2)

    if x[1] == pos:
      if x[0] not in vis and x[0] != 1:
        if len(vis) == n-1:
          ans = ans + 1
          return
        vis2 = copy.deepcopy(vis)
        vis2.append(x[0])
        search(x[0],vis2)


for x in range(m):
  data = raw_input()
  a,b = map(int,data.split(" "))
  db.append([a,b])

for x in db:
  if x[0] == 1:
    search(x[1],[1,x[1]])

print ans

Submission status: Wrong Answer

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

road = [[] for _ in range(N)]

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

counter = 0
    
def search(pointStack):
    global counter
    if len(pointStack) == N:
        counter += 1
        pointStack.pop()
        return
    
    currentNode = pointStack[-1]
    for nextNode in road[currentNode]:
        if nextNode in pointStack:
            continue
        pointStack.append(nextNode)
        search(pointStack)

search([0])

print(counter)

Submission status: Wrong Answer

Solution code:
n,m=map(int,raw_input().split())
g=[[] for _ in xrange(n)]
for i in xrange(m):
    a,b=map(int,raw_input().split())
    a-=1;b-=1
    g[a].append(b)
    g[b].append(a)
dp=[[0]*(1<<n) for _ in xrange(n)]
dp[0][1]=1
for i in xrange(n):
    for j in xrange(1<<n):
        if j>>i&1:
            for k in g[i]:
                if j>>k&1:
                    continue
                dp[k][j|(1<<k)]+=dp[i][j]
ans=0
for i in xrange(1,n):
    ans+=dp[i][(1<<n)-1]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import itertools
N,M=map(int,input().split())
A,B,C,D=[0]*M,[0]*M,[],[]
for i in range(M):
    A[i],B[i]=map(int,input().split())
    if A[i]==1:
        C.append(i)
    else:
        D.append(i)

res=0
for j in C:
    for p in itertools.permutations(D,N-2):
        path=[1,B[j]]
        for i in p:
            if A[i]==path[-1]:
                if not B[i] in path:
                    path.append(B[i])
                else:
                    break
            elif B[i]==path[-1]:
                if not A[i] in path:
                    path.append(A[i])
                else:
                    break
            else:
                break
        else:
            path.sort()
            if path==list(range(1,N+1)):
                res+=1
print(res)

Submission status: Time Limit Exceeded

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

res=0
for p in itertools.permutations(range(M),N-1):
    path=[]
    if A[p[0]]==1:
        path.append(A[p[0]])
    else:
        continue
    path.append(B[p[0]])
    for i in range(len(p)-1):
        if A[p[i+1]]==path[-1]:
            if not B[p[i+1]] in path:
                path.append(B[p[i+1]])
            else:
                break
        elif B[p[i+1]]==path[-1]:
            if not A[p[i+1]] in path:
                path.append(A[p[i+1]])
            else:
                break
        else:
            break
    else:
        path.sort()
        if path==list(range(1,N+1)):
            res+=1
print(res)

Submission status: Time Limit Exceeded

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

res=0
for p in itertools.permutations(range(M),N-1):
    path=[]
    if A[p[0]]==1:
        path.append(A[p[0]])
    else:
        continue
    path.append(B[p[0]])
    for i in range(len(p)-1):
        if A[p[i+1]]==path[-1]:
            path.append(B[p[i+1]])
        elif B[p[i+1]]==path[-1]:
            path.append(A[p[i+1]])
        else:
            break
    else:
        path.sort()
        if path==list(range(1,N+1)):
            res+=1
print(res)

Submission status: Time Limit Exceeded

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

res=0
for m in range(M):
    m+=1
    for p in itertools.permutations(range(M),m):
        path=[]
        if A[p[0]]==1:
            path.append(A[p[0]])
        else:
            continue
        path.append(B[p[0]])
        for i in range(len(p)-1):
            if A[p[i+1]]==path[-1]:
                path.append(B[p[i+1]])
            elif B[p[i+1]]==path[-1]:
                path.append(A[p[i+1]])
            else:
                break
        else:
            path.sort()
            if path==list(range(1,N+1)):
                res+=1
print(res)

Submission status: Time Limit Exceeded

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)
x_all=list(range(1,N+1))
ans=0
for partern in all_parterns:
  x=1
  x_list=[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
    x_list.append(x)
  if IsOk and sorted(x_list)==x_all:
    ans+=1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
# 基本課題 3．経路探索の解を求める
#
# 5 つの地点 0 ～ 4 を結ぶ道路網が図のようにある ( 図は授業支援システム参照 )
# 始点を 0 とし終点を 4 とした時、0 から 4 に至る経路をすべて求めなさい。
# ただし、同じ地点を２度通ってはいけない
#
# -*- coding: utf-8 -*-

ANS2=[] #0から4までの経路列挙(2次元配列)

#引数
#G:道路網を表す2次元配列(隣接リスト)
#LT:今のところの経路(だんだん広げていく)(最初は[[0]])
#返り値
#広げられなくなるまで広げた経路
#副作用
#ANS2を更新
#ANS2:0から4までの経路
def loot(G,LT,N):
    if LT==[]:
        return []
    else:    
        ANS=[] #今の地点から一回広げた時点での経路
        for i in range(len(LT)):
            for j in range(len(G[LT[i][-1]])):
                if not(G[LT[i][-1]][j] in LT[i]):
                    TMP=LT[i]
                    ANS.append(TMP+[G[LT[i][-1]][j]])
                else:
                    if not LT[i] in ANS2:
                        if len(LT[i])==N:
                            ANS2.append(LT[i])         
        return loot(G,ANS,N)

#2次元リストを標準出力
def print_list(lst):
    for i in range(len(lst)):
        for j in range(len(lst[i])):
            print(ANS2[i][j],end=' ')
        print('')    

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

loot(G,[[0]],N)

cnt=0

print(len(ANS2))