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: Runtime Error

Solution code:
n, m = map(int, input().split())
l = []
for i in range(m+1):
  l.append([])
types = set()
combo = []
for i in range(m):
  f, t = map(int, input().split())
  if not t in l[f]:
    l[f].append(t)
  
  if not f in l[t]:
    l[t].append(f)

def dfs(path, now):
  if len(set(path)) == n and not path in combo:
    combo.append(path)
    return

  for i in l[now]:
    if not i in path:
      temp = path[:]
      temp.append(i)
      dfs(temp, i)

  return
if m < n-1:
  print(0)
else:
  dfs([1], 1)
  print(len(combo))

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())
l = []
for i in range(m+1):
  l.append([])
types = set()
combo = []
for i in range(m):
  f, t = map(int, input().split())
  if not t in l[f]:
    l[f].append(t)
  
  if not f in l[t]:
    l[t].append(f)

def dfs(path, now):
  if len(set(path)) == n and not path in combo:
    combo.append(path)
    return

  for i in l[now]:
    if not i in path:
      temp = path[:]
      temp.append(i)
      dfs(temp, i)

  return

dfs([1], 1)
print(len(combo))

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

n,m = map(int,input().split())
H = [[0 for _ in range(n)] for _ in range(n) ]

for _ in range(m):
    a, b = map(int,input().split())
    edge_list.append([a-1,b-1])
    H[a-1][b-1] = 1
    H[b-1][a-1] = 1
    
l = [0 for _ in range(n)]
ans = 0

def dfs(node,visited):
    global ans
    if visited.count(0) == 0:
        ans += 1 
        return 0
    else:
        visited[node] = 1
        for node_,edge_ in enumerate(H[node]):
            if edge_ == 1 and visited[node_] != 1:
                visited[node_] = 1
                visited[node] = 1
                dfs(node_,visited)
                visited[node_] = 0

dfs(0,l)
print(ans)

Submission status: Runtime Error

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

for _ in range(m):
    a, b = map(int,input().split())
    edge_list.append([a-1,b-1])
    H[a-1][b-1] = 1
    H[b-1][a-1] = 1
    
l = [0 for _ in range(n)]
ans = 0

def dfs(node,visited):
    global ans
    if visited.count(0) == 0:
        ans += 1 
        return 0
    else:
        visited[node] = 1
        for node_,edge_ in enumerate(H[node]):
            if edge_ == 1 and visited[node_] != 1:
                visited[node_] = 1
                visited[node] = 1
                dfs(node_,visited)
                visited[node_] = 0

dfs(0,l)
print(ans)

Submission status: Runtime Error

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

for _ in range(m):
    a, b = map(int,input().split())
    edge_list.append([a-1,b-1])
    H[a-1][b-1] = 1
    H[b-1][a-1] = 1
    
l = [0 for _ in range(n)]
ans = 0

def dfs(node,visited):
    global ans
    if visited.count(0) == 0:
        ans += 1 
        return 0
    else:
        visited[node] = 1
        for node_,edge_ in enumerate(H[node]):
            if edge_ == 1 and visited[node_] != 1:
                visited[node_] = 1
                visited[node] = 1
                dfs(node_,visited)
                visited[node_] = 0                
dfs(0,l)
print(ans)

Submission status: Runtime Error

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

for _ in range(m):
    a, b = map(int,input().split())
    edge_list.append([a-1,b-1])
    H[a-1][b-1] = 1
    H[b-1][a-1] = 1
    
l = [0 for _ in range(n)]
ans = 0

def dfs(node,visited):
    global ans
    if visited.count(0) == 0:
        ans += 1 
        return 0
    else:
        visited[node] = 1
        for node_,edge_ in enumerate(H[node]):
            if edge_ == 1 and visited[node_] != 1:
                visited[node_] = 1
                visited[node] = 1
                dfs(node_,visited)
                visited[node_] = 0                
dfs(0,l)
print(ans)

Submission status: Runtime Error

Solution code:
from itertools import permutations

def f(n, m, uu, vv):
    a = [[0] * n for _ in range(n)]
    for u, v in zip(uu, vv):
        a[u][v] = 1
        a[v][u] = 1
    res = 0
    for p in permutations(range(n)):
        if p[0] != 0:
            break
        ok = True
        for i in range(n-1):。
            if a[p[i][p[i+1]] == 0:
                ok = False
                break
        if ok:
            res += 1
    return res


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

print(f(n, m, a, b))

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(50000)

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

array = [[int(x) for x in input().split()] for x in range(m)]

if m == 0 or m == 1:
    print(1)
    sys.exit()

adjacency_list = [[] for x in range(n + 1)]

for i in array:
    adjacency_list[i[0]].append(i[1])
    adjacency_list[i[1]].append(i[0])

searched = [False for x in range(m+1)]


def calc(start, maze, searched):
    res = 0
    if searched[start]:
        return 0
    searched[start] = True

    if searched.count(True) == n:
        return 1
    else:
        for next in maze[start]:
            res += calc(next, maze, list(searched))
    return res


print(calc(1, adjacency_list, searched))

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
n, m = [int(x) for x in input().split()]
adj = [[0]*n for i in range(n)]
visited = [0]*n
for i in range(n):
    a, b = [int(x) for x in input().split()]
    adj[a-1][b-1] = 1
    adj[b-1][a-1] = 1

ans = 0
def dfs(v):
    global ans
    if sum(visited) == n:
        ans += 1
    for i in range(n):
        if adj[v-1][i] == 1 and visited[i] == 0:
            visited[i] = 1
            dfs(i+1)
            visited[i] = 0

visited[0] = 1
dfs(1)
print(ans)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
n, m = [int(x) for x in input().split()]
adj = [[0]*m for i in range(m)]
visited = [0]*m
for i in range(m):
    a, b = [int(x) for x in input().split()]
    adj[a-1][b-1] = 1
    adj[b-1][a-1] = 1

ans = 0
def dfs(v):
    global ans
    if sum(visited) == m:
        ans += 1
    for i in range(m):
        if adj[v-1][i] == 1 and visited[i] == 0:
            visited[i] = 1
            dfs(i+1)
            visited[i] = 0

visited[0] = 1
dfs(1)
print(ans)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
n, m = [int(x) for x in input().split()]
adj = [[0]*m for i in range(m)]
visited = [0]*m
for i in range(m):
    a, b = [int(x) for x in input().split()]
    adj[a-1][b-1] = 1
    adj[b-1][a-1] = 1

ans = 0
def dfs(v):
    global ans
    if sum(visited) == m:
        ans += 1
    for i in range(m):
        if adj[v-1][i] == 1 and visited[i] == 0:
            visited[i] = 1
            dfs(i)
            visited[i] = 0

dfs(1)
print(ans)

Submission status: Runtime Error

Solution code:
import sys

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

array = [[int(x) for x in input().split()] for x in range(m)]

if m == 0 or m == 1:
    print(1)
    sys.exit()

adjacency_list = [[] for x in range(n + 1)]

for i in array:
    adjacency_list[i[0]].append(i[1])
    adjacency_list[i[1]].append(i[0])

searched = [False for x in range(m+1)]


def calc(start, maze, searched):
    res = 0
    if searched[start]:
        return 0
    searched[start] = True

    if searched.count(True) == n:
        return 1
    else:
        for next in maze[start]:
            res += calc(next, maze, list(searched))
    return res


print(calc(1, adjacency_list, searched))

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
path=[[[0]*n]*n]
for i in range(m):
    a,b=map(int,input().split())
    path[a][b]=1
    path[b][a]=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(0,n,visited)

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
def dfs(v,n,visited):#深さ優先探索
    all_visited=1#全ての点を通ったか調べる
      
    for i in range(n):
        if visited[i]==0:
            all_visited=0
    if all_visited==1:
        return 1
    count=0
    for i in range(n):
        if path[v][i]!=0:
            continue 
        if visited[i]==1:
            continue
        visited[i]=1
        count+=dfs(i,n,visited)
        visited[i]=0
    return count

n,m=map(int,input().split())
path=[[0]*n for i in range(n)]
for i in range(n):
    a,b=map(int,input().split())
    path[a-1][b-1]=1
    path[b-1][a-1]=1#隣接していれば１
visited=[0]*n
visited[0]=1#1は初めに通る
print(dfs(0,n,visited))

Submission status: Runtime Error

Solution code:
nmax = 8
def dfs(v, N, visited):
    all_visited=True
    for i in range(N):
        if visited[i]==False:
            all_visited=False

    if all_visited==True:
        return 1

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

        visited[i]=True
        ret+=dfs(i,N,visited)
        visited[i]=False

    return ret

N, M = map(int, input().split())
graph = [[False]*M for i in range(N)]
for i in range(M):
    A, B = map(int, input().split())
    graph[A-1][B-1]=True
    graph[B-1][A-1]=True

visited = [False]*N

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

Submission status: Runtime Error

Solution code:
import sys

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

array = [[int(x) for x in input().split()] for x in range(m)]

if m == 0 or m == 1:
    print(1)
    sys.exit()

adjacency_list = [[] for x in range(m + 1)]

for i in array:
    adjacency_list[i[0]].append(i[1])
    adjacency_list[i[1]].append(i[0])

searched = [False for x in range(m+1)]


def calc(start, maze, searched):
    res = 0
    if searched[start]:
        return 0
    searched[start] = True

    if searched.count(True) == n:
        return 1
    else:
        for next in maze[start]:
            res += calc(next, maze, list(searched))
    return res


print(calc(1, adjacency_list, searched))

Submission status: Runtime Error

Solution code:
import sys

n, m = map(int, input().split())
if m == 0:
    print(1)
    sys.exit()

array = [[int(x) for x in input().split()] for x in range(m)]

adjacency_list = [[] for x in range(m + 1)]

for i in array:
    adjacency_list[i[0]].append(i[1])
    adjacency_list[i[1]].append(i[0])

searched = [False for x in range(m+1)]


def calc(start, maze, searched):
    res = 0
    if searched[start]:
        return 0
    searched[start] = True

    if searched.count(True) == n:
        return 1
    else:
        for next in maze[start]:
            res += calc(next, maze, list(searched))
    return res


print(calc(1, adjacency_list, searched))

Submission status: Runtime Error

Solution code:
import sys

sys.setrecursionlimit(100000)


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

array = [[int(x) for x in input().split()] for x in range(m)]

adjacency_list = [[] for x in range(m + 1)]

for i in array:
    adjacency_list[i[0]].append(i[1])
    adjacency_list[i[1]].append(i[0])

searched = [False for x in range(m+1)]


def calc(start, maze, searched):
    res = 0
    if searched[start]:
        return 0
    searched[start] = True

    if searched.count(True) == n:
        return 1
    else:
        for next in maze[start]:
            res += calc(next, maze, list(searched))
    return res


print(calc(1, adjacency_list, searched))

Submission status: Runtime Error

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

array = [[int(x) for x in input().split()] for x in range(m)]

adjacency_list = [[] for x in range(m + 1)]

for i in array:
    adjacency_list[i[0]].append(i[1])
    adjacency_list[i[1]].append(i[0])

searched = [False for x in range(m+1)]


def calc(start, maze, searched):
    res = 0
    if searched[start]:
        return 0
    searched[start] = True

    if searched.count(True) == n:
        return 1
    else:
        for next in maze[start]:
            res += calc(next, maze, list(searched))
    return res


print(calc(1, adjacency_list, searched))

Submission status: Runtime Error

Solution code:
import sys

sys.setrecursionlimit(1000000)


def judge(now, edges, searched):
    pattern = 0

    if searched[now] == "searched":
        return 0

    searched[now] = "searched"

    if searched.count("searched") == len(searched) - 1:
        return 1

    for next in edges[now]:
        pattern += judge(next, edges, list(searched))
    return pattern


def main():
    n, m = map(int, input().split())
    edges = [[int(x) for x in input().split()] for x in range(m)]
    adjacent_edges = [[] for x in range(m + 1)]
    for edge in edges:
        adjacent_edges[edge[0]].append(edge[1])
        adjacent_edges[edge[1]].append(edge[0])
    searched = ["yet" for x in range(n + 1)]

    print(judge(1, adjacent_edges, searched))


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
def judge(now, edges, searched):
    pattern = 0

    if searched[now] == "searched":
        return 0

    searched[now] = "searched"

    if searched.count("searched") == len(searched) - 1:
        return 1

    for next in edges[now]:
        pattern += judge(next, edges, list(searched))
    return pattern


def main():
    n, m = map(int, input().split())
    edges = [[int(x) for x in input().split()] for x in range(m)]
    adjacent_edges = [[] for x in range(m + 1)]
    for edge in edges:
        adjacent_edges[edge[0]].append(edge[1])
        adjacent_edges[edge[1]].append(edge[0])
    searched = ["yet" for x in range(n + 1)]

    print(judge(1, adjacent_edges, searched))


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import numpy as np
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]:
        for j not in visited:
            dfs(j,visited+[j])
dfs(0,[0])
print(len(v))

Submission status: Runtime Error

Solution code:
import numpy as np
n, m = map(int, input().split())
if m == 0:
    print(0)
    exit()
r = [[] for i in range(m)]
for i in range(m):
    f, s = map(int, input().split())
    r[f-1].append(s - 1)
    r[s-1].append(f - 1)
ans = []
def dfs(now, visited = []):
    global ans
    if len(visited) == n:
        ans.append([visited])
        return
    for j in r[now]:
        if j not in visited:
            dfs(j, visited + [j])
dfs(0, [0])
print(len(ans))

Submission status: Runtime Error

Solution code:
import numpy as np
n, m = map(int, input().split())
r = [[] for i in range(m)]
for i in range(m):
    f, s = map(int, input().split())
    r[f-1].append(s - 1)
    r[s-1].append(f - 1)
ans = []
def dfs(now, visited = []):
    try:
        global ans
        if len(visited) == n:
            ans.append([visited])
            return
        for j in r[now]:
            if j not in visited:
                dfs(j, visited + [j])
    except:
        return
dfs(0, [0])
print(len(ans))

Submission status: Runtime Error

Solution code:
import numpy as np
n, m = map(int, input().split())
r = [[] for i in range(m)]
for i in range(m):
    f, s = map(int, input().split())
    r[f-1].append(s - 1)
    r[s-1].append(f - 1)
ans = []
def dfs(now, visited = []):
    global ans
    if len(visited) == n:
        ans.append([visited])
        return
    for j in r[now]:
        if j not in visited:
            dfs(j, visited + [j])
dfs(0, [0])
print(len(ans))

Submission status: Runtime Error

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(N)]
#print a
b=list(itertools.combinations(a,N-1))
#print b

#print collections.Counter(b[0])

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: Runtime Error

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: Runtime Error

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

l = []

for i in range(N):
    l.append(list(map(lambda x: int(x) - 1, input().split())))

lis = [[] for i in range(N)]

for i in range(N):
    lis[l[i][0]].append(l[i][1])
    lis[l[i][1]].append(l[i][0])


# 隣接行列
# list = [[0 for c in range(M)] for r in range(N)]
#
# for i in range(M):
#     tmp_n, tmp_m = map(int, input().split())
#     list[tmp_n - 1][tmp_m - 1] = 1
#
#
# def dot(index1, index2):
#     results = [[0 for c in range(M)] for r in range(N)]
#     for (i, j) in zip(index1, zip(*index2)):
#         print(i,j)
#     return results



# 再起関数
# def travel(now, nextnodes, visited):
#     ends.append(visited)
#     visited.append(now + 1)
#     for node in nextnodes:
#         if node in visited:
#             continue
#         travel(node - 1, lis[node - 1], visited[:])
#
#
# travel(0, lis[0], [])

que = [[0, lis[0], []]]
ends = []

while que:
    now, nextnodes, visited = que.pop()
    ends.append(visited)
    visited.append(now)
    for node in nextnodes:
        if node in visited:
            continue
        que.append([node, lis[node], visited[:]])

print(len(list(filter(lambda i : len(i) is N, ends))))

Submission status: Runtime Error

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

l = []

for i in range(N):
    l.append(list(map(int, input().split())))

lis = [[] for i in range(N)]

for i in range(N):
    lis[l[i][0] - 1].append(l[i][1])
    lis[l[i][1] - 1].append(l[i][0])


# 隣接行列
# list = [[0 for c in range(M)] for r in range(N)]
#
# for i in range(M):
#     tmp_n, tmp_m = map(int, input().split())
#     list[tmp_n - 1][tmp_m - 1] = 1
#
#
# def dot(index1, index2):
#     results = [[0 for c in range(M)] for r in range(N)]
#     for (i, j) in zip(index1, zip(*index2)):
#         print(i,j)
#     return results



# 再起関数
# def travel(now, nextnodes, visited):
#     ends.append(visited)
#     visited.append(now + 1)
#     for node in nextnodes:
#         if node in visited:
#             continue
#         travel(node - 1, lis[node - 1], visited[:])
#
#
# travel(0, lis[0], [])

que = [[0, lis[0], []]]
ends = []

while que:
    now, nextnodes, visited = que.pop()
    ends.append(visited)
    visited.append(now + 1)
    for node in nextnodes:
        if node in visited:
            continue
        que.append([node - 1, lis[node - 1], visited[:]])

print(len(list(filter(lambda i : len(i) is N, ends))))

Submission status: Runtime Error

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

l = []

for i in range(N):
    l.append(list(map(int, input().split())))

lis = [[] for i in range(N)]

for i in range(N):
    lis[l[i][0] - 1].append(l[i][1])
    lis[l[i][1] - 1].append(l[i][0])


# 隣接行列
# list = [[0 for c in range(M)] for r in range(N)]
#
# for i in range(M):
#     tmp_n, tmp_m = map(int, input().split())
#     list[tmp_n - 1][tmp_m - 1] = 1
#
#
# def dot(index1, index2):
#     results = [[0 for c in range(M)] for r in range(N)]
#     for (i, j) in zip(index1, zip(*index2)):
#         print(i,j)
#     return results



# 再起関数
# def travel(now, nextnodes, visited):
#     ends.append(visited)
#     visited.append(now + 1)
#     for node in nextnodes:
#         if node in visited:
#             continue
#         travel(node - 1, lis[node - 1], visited[:])
#
#
# travel(0, lis[0], [])

que = [[0, lis[0], []]]
ends = []

while que:
    now, nextnodes, visited = que.pop()
    ends.append(visited)
    visited.append(now + 1)
    for node in nextnodes:
        if node in visited:
            continue
        que.append([node - 1, lis[node - 1], visited[:]])

print(len(list(filter(lambda i: len(i) is 3, ends))))

Submission status: Runtime Error

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

l = []

for i in range(N):
    l.append(list(map(int, input().split())))

lis = [[] for i in range(N)]

for i in range(N):
    lis[l[i][0] - 1].append(l[i][1])
    lis[l[i][1] - 1].append(l[i][0])

print(lis)

# 隣接行列
# list = [[0 for c in range(M)] for r in range(N)]
#
# for i in range(M):
#     tmp_n, tmp_m = map(int, input().split())
#     list[tmp_n - 1][tmp_m - 1] = 1
#
#
# def dot(index1, index2):
#     results = [[0 for c in range(M)] for r in range(N)]
#     for (i, j) in zip(index1, zip(*index2)):
#         print(i,j)
#     return results



# 再起関数
# def travel(now, nextnodes, visited):
#     ends.append(visited)
#     visited.append(now + 1)
#     for node in nextnodes:
#         if node in visited:
#             continue
#         travel(node - 1, lis[node - 1], visited[:])
#
#
# travel(0, lis[0], [])

que = [[0, lis[0], []]]
ends = []
while que:
    now, nextnodes, visited = que.pop()
    ends.append(visited)
    visited.append(now + 1)
    for node in nextnodes:
        if node in visited:
            continue
        que.append([node - 1, lis[node - 1], visited[:]])

print(len(list(filter(lambda i: len(i) is 3, ends))))

Submission status: Runtime Error

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

l = []

for i in range(N):
    l.append(list(map(int, input().split())))

lis = [[] for i in range(N)]

for i in range(N):
    lis[l[i][0] - 1].append(l[i][1])
    lis[l[i][1] - 1].append(l[i][0])

print(lis)

# 隣接行列
# list = [[0 for c in range(M)] for r in range(N)]
#
# for i in range(M):
#     tmp_n, tmp_m = map(int, input().split())
#     list[tmp_n - 1][tmp_m - 1] = 1
#
#
# def dot(index1, index2):
#     results = [[0 for c in range(M)] for r in range(N)]
#     for (i, j) in zip(index1, zip(*index2)):
#         print(i,j)
#     return results



# 再起関数
# def travel(now, nextnodes, visited):
#     ends.append(visited)
#     visited.append(now + 1)
#     for node in nextnodes:
#         if node in visited:
#             continue
#         travel(node - 1, lis[node - 1], visited[:])
#
#
# travel(0, lis[0], [])

que = [[0, lis[0], []]]
ends = []
while que:
    now, nextnodes, visited = que.pop()
    ends.append(visited)
    visited.append(now + 1)
    for node in nextnodes:
        if node in visited:
            continue
        que.append([node - 1, lis[node - 1], visited[:]])

print(len(list(filter(lambda i: len(i) is 3, ends))))

Submission status: Runtime Error

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

l = []

for i in range(N):
    l.append(list(map(int, input().split())))

lis = [[] for i in range(N)]

for i in range(N):
    lis[l[i][0] - 1].append(l[i][1])
    lis[l[i][1] - 1].append(l[i][0])

# list = [[0 for c in range(M)] for r in range(N)]
#
# for i in range(M):
#     tmp_n, tmp_m = map(int, input().split())
#     list[tmp_n - 1][tmp_m - 1] = 1
#
#
# def dot(index1, index2):
#     results = [[0 for c in range(M)] for r in range(N)]
#     for (i, j) in zip(index1, zip(*index2)):
#         print(i,j)
#     return results

ends = []
que = []

# def travel(now, nextnodes, visited):
#     ends.append(visited)
#     visited.append(now + 1)
#     for node in nextnodes:
#         if node in visited:
#             continue
#         travel(node - 1, lis[node - 1], visited[:])
#
#
# travel(0, lis[0], [])

que = [[0, lis[0], []]]

while que:
    now, nextnodes, visited = que.pop()
    ends.append(visited)
    visited.append(now + 1)
    for node in nextnodes:
        if node in visited:
            continue
        que.append([node - 1, lis[node - 1], visited[:]])

print(len(list(filter(lambda i: len(i) is 3, ends))))

Submission status: Runtime Error

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

l = []

for i in range(N):
    l.append(list(map(int, input().split())))

lis = [[] for i in range(N)]

for i in range(N):
    lis[l[i][0] - 1].append(l[i][1])
    if l[i][1] == N:
        lis[l[i][1] - 1].append(l[i][0])

# list = [[0 for c in range(M)] for r in range(N)]
#
# for i in range(M):
#     tmp_n, tmp_m = map(int, input().split())
#     list[tmp_n - 1][tmp_m - 1] = 1
#
#
# def dot(index1, index2):
#     results = [[0 for c in range(M)] for r in range(N)]
#     for (i, j) in zip(index1, zip(*index2)):
#         print(i,j)
#     return results

ends = []
que = []

# def travel(now, nextnodes, visited):
#     ends.append(visited)
#     visited.append(now + 1)
#     for node in nextnodes:
#         if node in visited:
#             continue
#         travel(node - 1, lis[node - 1], visited[:])
#
#
# travel(0, lis[0], [])

que = [[0, lis[0], []]]

while que:
    now, nextnodes, visited = que.pop()
    ends.append(visited)
    visited.append(now + 1)
    for node in nextnodes:
        if node in visited:
            continue
        que.append([node - 1, lis[node - 1], visited[:]])

print(len(list(filter(lambda i: len(i) is 3, ends))))

Submission status: Runtime Error

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

l = []

for i in range(N):
    l.append(list(map(int, input().split())))

lis = [[] for i in range(N)]

for i in range(N):
    lis[l[i][0] - 1].append(l[i][1])
    if l[i][1] == N:
        lis[l[i][1] - 1].append(l[i][0])


# list = [[0 for c in range(M)] for r in range(N)]
#
# for i in range(M):
#     tmp_n, tmp_m = map(int, input().split())
#     list[tmp_n - 1][tmp_m - 1] = 1
#
#
# def dot(index1, index2):
#     results = [[0 for c in range(M)] for r in range(N)]
#     for (i, j) in zip(index1, zip(*index2)):
#         print(i,j)
#     return results

ends =[]


def travel(now, nextnodes, visited):
    ends.append(visited)
    visited.append(now+1)
    for node in nextnodes:
        if node in visited:
            continue
        travel(node-1, lis[node-1], visited[:])


travel(0, lis[0], [])
print(len(list(filter(lambda i : len(i) is 3, ends))))

Submission status: Runtime Error

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

abmap = {}
for a, b in ab:
    atarget = abmap.get(a)
    if atarget == None:
        abmap[a] = []
    abmap[a].append(b)

    btarget = abmap.get(b)
    if btarget == None:
        abmap[b] = []
    abmap[b].append(a)

que = [[1, abmap[1], []]]
ends = []
while que:
    now, nextnodes, visited = que.pop()
    ends.append(visited)
    visited.append(now)
    for node in nextnodes:
        if node in visited:
            continue
        mvisited = visited[:]
        que.append([node, abmap[node], mvisited])

print(len(filter(lambda x: len(x) == n, ends)))

Submission status: Runtime Error

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

bar = [[] for _ in range(m)]

for i in range(n):
    a,b = map(lambda x:int(x)-1,input().split(' '))
    bar[a].append(b)
    bar[b].append(a) 


result = 0

def search(root=[0]):
    global result
    if len(root) >= n:
        result += 1
        return
    nxt = set(bar[root[-1]])
    nxt = nxt - set(root)
    for nxt_ in nxt:
        search(root+[nxt_])

search()
print(result)

Submission status: Runtime Error

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

bar = [[] for _ in range(m)]

for i in range(n):
    a,b = map(lambda x:int(x)-1,input().split(' '))
    bar[a].append(b)
    bar[b].append(a) 


result = 0

def search(root=[0]):
    global result
    if len(root) >= n:
        result += 1
    nxt = set(bar[root[-1]])
    nxt = nxt - set(root)
    for nxt_ in nxt:
        search(root+[nxt_])

search()
print(result)

Submission status: Runtime Error

Solution code:
num = list(map(int,raw_input().split()))
point = num[0]
line = num[1]

d = {}
for i in range (point):
    d[i+1] = []
for i in range(point):
    pair = list(map(int,raw_input().split()))
    d[pair[0]].append(pair[1])
    d[pair[1]].append(pair[0])
old_list = []
new_list = [[1]]
for i in range (point-1):
    old_list = new_list[:]
    new_list =[]
    for j in old_list:
        for k in d[j[-1]]:
            if k in j:
                pass
            else:
                j.append(k)
                new_list.append(j[:])
                j.pop()
print len (new_list)