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())
ab = []
for _ in range(n):
  a,b=map(int,input().split())
  a,b=a-1,b-1
  ab.append({a,b})
import itertools

cnt = 0
for v in itertools.permutations(range(1,n)):
  l = 0
  ok = True
  for v2 in v:
    if {l,v2} not in ab:
      ok = False
      break
    l = v2
  if ok == True:
    cnt += 1
  
print(cnt)

Submission status: Runtime Error

Solution code:
import itertools
n, m = map(int, input().split())
path = [[False] * n for i 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
for i itertools.permutations(range(n), n):
    if i[0] == 0:
        for j in range(n):
            if j == n - 1:
                ans += 1
                break
            if not path[i[j]][i[j+1]]:
                break
print(ans)

Submission status: Runtime Error

Solution code:
def ser(visited,now):
  visited.append(now)
  if len(visited)==n:
    return 1
  cnt=0
  for i in bri[now]:
    if i not in visited:
      cnt+= ser(visited[:],i)
  return cnt

n,m=map(int,input().split())
bri=[[] for _ in range(m)]
for i in range(m):
  a,b=map(int,input().split())
  bri[a-1].append(b-1)
  bri[b-1].append(a-1)
print(ser([],0))

Submission status: Runtime Error

Solution code:
import copy
import sys
sys.setrecursionlimit(10**7)
N, M = map(int, input().split())
edges = [[] for _ in range(M)]
for _ in range(M):
    a, b = map(int, input().split())
    edges[a - 1].append(b - 1)
    edges[b - 1].append(a - 1)
ans = 0
def dfs(start,path):
    next_path = copy.copy(path)
    global ans
    next_path.append(start)
    if len(next_path) == N:
        ans += 1
        return
    for i in edges[start]:
        if i not in next_path:
            dfs(i,next_path)
dfs(0,[])
print(ans)

Submission status: Runtime Error

Solution code:
import math
import sys
from collections import deque
import copy
import itertools
from itertools import permutations
def mi() : return map(int,input().split())
def i() : return int(input())
from scipy.special import perm #print(perm(4,2,exact=True))=4P2=3
a,b=mi()
ans=0
l=[[] for _ in range(a)]
for i in range(b):
  u,v=mi()
  l[u-1].append(v-1)
  l[v-1].append(u-1)
S=[]
for i in range(1,a):
  S.append(i)
lst=list(itertools.permutations(S))
for i in lst:
  x=0
  t=True
  for w in range(len(i)):
    if not i[w] in l[x]:
      t=False
      break
    x=i[w]
  if t:
    ans+=1
print(ans)

Submission status: Runtime Error

Solution code:
import math
import sys
from collections import deque
import copy
import itertools
from itertools import permutations
def mi() : return map(int,input().split())
def i() : return int(input())
from scipy.special import perm #print(perm(4,2,exact=True))=4P2=3
a,b=mi()
ans=0
l=[[] for _ in range(a)]
for i in range(b):
  u,v=mi()
  l[u-1].append(v-1)
  l[v-1].append(u-1)
S=[]
for i in range(1,a):
  S.append(i)
lst=list(permutations(S))
for i in lst:
  x=0
  t=True
  for w in range(len(i)):
    if not i[w] in l[x]:
      t=False
      break
    x=i[w]
  if t:
    ans+=1
print(ans)

Submission status: Runtime Error

Solution code:
import itertools
n,m=map(int,input().split())
path=[[False]*n for i 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;

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[i[j]][i[j]+1]:
                break
print(ans)

Submission status: Runtime Error

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

import itertools
p_con = list(itertools.combinations(p_list,n-1))
output =0
for con in p_con:
  bou= sum(con,[])
  syuten = 0
  for i in range(2,n+1):
    if bou.count(i) == 1 and syuten == 0:
      syuten = i
    elif bou.count(i) != 2:
      break
  else:
    output += 1
    continue
  
print(output)

Submission status: Runtime Error

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

def dfs(t,seen):
  if all(seen):
    return 1
  ret=0
  l=g[t]
  for li in l:
    if seen[li]==0:
      seenli=seen.copy()
      seenli[li]=1
      ret+=dfs(li,seenli)
  return ret
seen=[0]*n
seen[0]=1
print(dfs(0,seen))

Submission status: Runtime Error

Solution code:
import itertools as itl
n, m=map(int, input().split())
#ここでリストを作成する
hen=[]
check=0
if m==0:
  print(0)
  exit()
for _ in range(m):
  hen.append(list(map(int, input().split())))
#print(hen)
l=list(range(2, n+1))
for v in itl.permutations(l):
  #print(v)
  for i in range(n-2):
    if not(sorted(v[i:i+2]) in hen) or not(list([1, v[0]]) in hen):
      break
  else:
    if i==n-3:
      check+=1
    continue
print(check)

Submission status: Runtime Error

Solution code:
import itertools as itl
n, m=map(int, input().split())
#ここでリストを作成する
hen=[]
check=0
for _ in range(m):
  hen.append(list(map(int, input().split())))
#print(hen)
l=list(range(2, n+1))
for v in itl.permutations(l):
  #print(v)
  for i in range(n-2):
    if not(sorted(v[i:i+2]) in hen) or not(list([1, v[0]]) in hen):
      break
  else:
    if i==n-3:
      check+=1
    continue
    break 
print(check)

Submission status: Runtime Error

Solution code:
import itertools as itl
n, m=map(int, input().split())
#ここでリストを作成する
hen=[]
check=0
for _ in range(m):
  hen.append(tuple(map(int, input().split())))
#print(hen)
l=list(range(2, n+1))
for v in itl.permutations(l):
  #print(v)
  for i in range(n-2):
    if not(tuple(sorted(v[i:i+2])) in hen) or not(tuple([1, v[0]]) in hen):
      break
  else:
    if i==n-3:
      check+=1
    continue
    break 
print(check)

Submission status: Runtime Error

Solution code:
import itertools as itl
n, m=map(int, input().split())
#ここでリストを作成する
hen=[]
check=0
for _ in range(m):
  hen.append(tuple(map(int, input().split())))
#print(hen)
l=list(range(2, n+1))
for v in itl.permutations(l):
  #print(v)
  for i in range(n-2):
    if not(tuple(sorted(v[i:i+2])) in hen) or not(tuple([1, v[0]]) in hen):
      #print(sorted(v[i:i+2]))
      break
  else:
    if i==n-3:
      check+=1
    continue
print(check)

Submission status: Runtime Error

Solution code:
def abc054_c_one_stroke_paths():
    import copy
    N, E = map(int, input().split())

    # create graph G
    G = {}
    for m in range(M):
        a, z = map(int, input().split())
        G[a] = G.get(a, [])
        G[a].append(z)
        G[z] = G.get(z, [])
        G[z].append(a)

    # print(G)

    # find all paths
    if G.get(1, 0) == 0:
        print(0)
        return

    paths = []

    def solve(a, path):
        path.append(a)
        if len(path) == N:
            paths.append(path)
            return
        for z in G.get(a):
            p = copy.copy(path)
            if z in p:
                continue
            solve(z, p)

    solve(1, [])
    # print(paths)
    print(len(paths))


##########
if __name__ == "__main__":
    abc054_c_one_stroke_paths()

Submission status: Runtime Error

Solution code:
def abc054_c_one_stroke_paths():
    import copy
    N, E = map(int, input().split())

    # create graph G
    G = {}
    for n in range(N):
        a, z = map(int, input().split())
        G[a] = G.get(a, [])
        G[a].append(z)
        G[z] = G.get(z, [])
        G[z].append(a)

    # print(G)

    # find all paths
    if G.get(1) is None:
        print(0)
        return

    paths = []

    def solve(a, path):
        path.append(a)
        if len(path) == N:
            paths.append(path)
            return
        for z in G.get(a):
            p = copy.copy(path)
            if z in p:
                continue
            solve(z, p)

    solve(1, [])
    # print(paths)
    print(len(paths))


##########
if __name__ == "__main__":
    abc054_c_one_stroke_paths()

Submission status: Runtime Error

Solution code:
def abc054_c_one_stroke_paths():
    import copy
    N, E = map(int, input().split())

    # create graph G
    G = {}
    for n in range(N):
        a, z = map(int, input().split())
        G[a] = G.get(a, [])
        G[a].append(z)
        G[z] = G.get(z, [])
        G[z].append(a)

    print(G)

    # find all paths
    if G.get(1) is None:
        print(0)
        return

    paths = []

    def solve(a, path):
        path.append(a)
        if len(path) == N:
            paths.append(path)
            return
        for z in G.get(a):
            p = copy.copy(path)
            print(p, a, z)
            if z in p:
                continue
            solve(z, p)

    solve(1, [])
    print(paths, len(paths))


##########
if __name__ == "__main__":
    abc054_c_one_stroke_paths()

Submission status: Runtime Error

Solution code:

from itertools import permutations

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

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

Submission status: Runtime Error

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)

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

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


def dfs(i, depth):
    if visited[i]:
        return 0
    if depth == N - 1:
        return 1

    visited[i] = 1
    ret = 0
    for j in range(0, N):
        if graph[i][j]:
            ret += dfs(j, depth + 1)

    visited[i] = 0

    return ret


print(dfs(0, 0))

Submission status: Runtime Error

Solution code:
import sys

sys.setrecursionlimit(1000000)

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

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


def dfs(i, depth):
    if visited[i]:
        return 0
    if depth == N - 1:
        return 1

    visited[i] = 1
    ret = 0
    for j in range(0, N):
        if graph[i][j]:
            ret += dfs(j, depth + 1)

    visited[i] = 0

    return ret


print(dfs(0, 0))

Submission status: Runtime Error

Solution code:
import sys

sys.setrecursionlimit(100000)

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

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


def dfs(i, depth):
    if visited[i]:
        return 0
    if depth == N - 1:
        return 1

    visited[i] = 1
    ret = 0
    for j in range(0, N):
        if graph[i][j]:
            ret += dfs(j, depth + 1)

    visited[i] = 0

    return ret


print(dfs(0, 0))

Submission status: Runtime Error

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

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


def dfs(i, depth):
    if visited[i]:
        return 0
    if depth == N - 1:
        return 1

    visited[i] = 1
    ret = 0
    for j in range(0, N):
        if graph[i][j]:
            ret += dfs(j, depth + 1)

    visited[i] = 0

    return ret


print(dfs(0, 0))

Submission status: Runtime Error

Solution code:
def DFS(now, visited):
    ans = 0
    if all(visited):
        return 1
    for i in range(N):
        if path[now][i] and visited[i] == False:
            visited[i] = True
            ans += DFS(i, visited)
            visited[i] = False
    return ans
    


N, M = map(int, input().split())
path = [[0]*N for i in range(M)]
for i in range(M):
    a, b = map(int, input().split())
    path[a-1][b-1] = 1
    path[b-1][a-1] = 1
visited = [False]*N
visited[0] = True
print(DFS(0, visited))

Submission status: Runtime Error

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

count = 0
for i in range(n):
    a, b = map(int, input().split())
    if a == 1 or b == 1:
        count += 1

print(count)

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
# input
from collections import deque
import itertools

n, m = map(int, input().split())
a, b = [0] * (n), [0] * (n)
path = [[] for _ in range(n)]
for i in range(m):
    a[i], b[i] = map(int, input().split())
    a[i] -= 1
    b[i] -= 1
    path[a[i]].append(b[i])
    path[b[i]].append(a[i])
# n-1 ! を全探索する
all_lis = itertools.permutations(range(1, n))  # 1(0)は出発点なので除く
# print(all_lis)

ans = 0
for i in all_lis:
    start = 0
    ok = 1
    for j in range(n - 1):
        if i[j] not in path[start]:
            ok = 0
            break
        else:
            start = i[j]
    if ok:
        ans += 1
print(ans)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(100000000)

N, M = map(int, input().split())
adj = [[] for _ in range(M)]
visited = [0] * N

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

ans = []

def dfs(x):
  visited[x-1] = 1
  if visited == [1] * N:
    ans.append(1)
  for i in range(len(adj[x-1])):
    if visited[adj[x-1][i] - 1] == 0:
      dfs(adj[x-1][i])
  visited[x-1] = 0
      
dfs(1)
print(sum(ans))

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(100000)

N, M = map(int, input().split())
adj = [[] for _ in range(M)]
visited = [0] * N

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

ans = []

def dfs(x):
  visited[x-1] = 1
  if visited == [1] * N:
    ans.append(1)
  for i in range(len(adj[x-1])):
    if visited[adj[x-1][i] - 1] == 0:
      dfs(adj[x-1][i])
  visited[x-1] = 0
      
dfs(1)
print(sum(ans))

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
adj = [[] for _ in range(M)]
visited = [0] * N

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

ans = []

def dfs(x):
  visited[x-1] = 1
  if visited == [1] * N:
    ans.append(1)
  for i in range(len(adj[x-1])):
    if visited[adj[x-1][i] - 1] == 0:
      dfs(adj[x-1][i])
  visited[x-1] = 0
      
dfs(1)
print(sum(ans))

Submission status: Runtime Error

Solution code:
import sys

sys.setrecursionlimit(500 * 500)

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

visit = [0] * (n + 1)


def dfs(now, depth):
    if visit[now]:
        return 0
    if depth == n:
        return 1

    count = 0
    visit[now] = 1
    if graph[now]:
        for i in graph[now]:
            count += dfs(i, depth + 1)
    visit[now] = 0

    return count


ans = dfs(1, 1)
print(ans)

Submission status: Runtime Error

Solution code:
import sys

sys.setrecursionlimit(500 * 500)

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

visit = [0] * (n + 1)
ans = 0


def dfs(now, depth):
    global ans
    if visit[now]:
        pass
    if depth == n:
        ans += 1

    visit[now] = 1
    if graph[now]:
        for i in graph[now]:
            if visit[i] == 0:
                dfs(i, depth + 1)
    visit[now] = 0


dfs(1, 1)
print(ans)

Submission status: Runtime Error

Solution code:
from collections import deque

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

visit = [0] * (n + 1)
ans = 0


def dfs(now, depth):
    global ans
    if visit[now]:
        pass
    if depth == n:
        ans += 1

    visit[now] = 1
    if graph[now]:
        for i in graph[now]:
            if visit[i] == 0:
                dfs(i, depth + 1)
    visit[now] = 0


dfs(1, 1)
print(ans)

Submission status: Runtime Error

Solution code:
from collections import deque

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

visit = [0] * (n + 1)
ans = 0


def dfs(now, depth):
    global ans
    if visit[now]:
        pass
    if depth == n:
        ans += 1

    visit[now] = 1
    for i in graph[now]:
        if visit[i] == 0:
            dfs(i, depth + 1)
    visit[now] = 0


dfs(1, 1)
print(ans)

Submission status: Runtime Error

Solution code:
from collections import deque

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

visit = [0] * (n + 1)
q = deque([1])
while q:
    now = q.popleft()
    visit[now] = 1
    for i in graph[now]:
        if visit[i] == 0:
            q.append(i)


def dfs(now, count, seen):
    global ans
    if count == depth:
        ans += 1
    else:
        for i in graph[now]:
            if seen[i] == 0:
                seen[now] = 1
                dfs(i, count + 1, seen)
                seen[now] = 0


depth = sum(visit)
ans = 0
seen = [0] * (n + 1)
dfs(1, 1, seen)
print(ans)

Submission status: Runtime Error

Solution code:
from collections import deque
import sys

sys.setrecursionlimit(500 * 500)

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

visit = [0] * (n + 1)
q = deque([1])
while q:
    now = q.popleft()
    visit[now] = 1
    for i in graph[now]:
        if visit[i] == 0:
            q.append(i)

depth = sum(visit)
ans = 0
visit = [0] * (n + 1)


def dfs(now, count):
    global ans
    if count == depth:
        ans += 1
    else:
        for i in graph[now]:
            if visit[i] == 0:
                visit[now] = 1
                dfs(i, count + 1)
                visit[now] = 0


dfs(1, 1)
print(ans)

Submission status: Runtime Error

Solution code:
from collections import deque

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

visit = [0] * (n + 1)
q = deque([1])
while q:
    now = q.popleft()
    visit[now] = 1
    for i in graph[now]:
        if visit[i] == 0:
            q.append(i)

depth = sum(visit)
ans = 0
visit = [0] * (n + 1)


def dfs(now, count):
    global ans
    if count == depth:
        ans += 1
    else:
        for i in graph[now]:
            if visit[i] == 0:
                visit[now] = 1
                dfs(i, count + 1)
                visit[now] = 0


dfs(1, 1)
print(ans)

Submission status: Runtime Error

Solution code:

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

def mkmap(N, M):
    mapdic = {}
    for i in range(1, M+1):
        mapdic[str(i)] = [] 
    for j in range(N):
        pathA, pathB = map(str, input().split())
        mapdic[pathA] = mapdic[pathA] + [pathB]
        mapdic[pathB] = mapdic[pathB] + [pathA]
    return mapdic

mapdic = mkmap(N, M)
import copy

roots = [[]]*N
roots[0] = ["1"]
for i in range(N-1):
    root = copy.deepcopy(roots[i])
    for nowroot in root:
        for nextroot in mapdic[nowroot[-1]]:
            if  i >= 1:
                if not nextroot in nowroot:                    
                    roots[i+1] = roots[i+1] + [nowroot + nextroot]
                else:
                    pass
            else:
                roots[i+1] = roots[i+1] + [nowroot + nextroot]


List = [str(n+1) for n in range(N)]
check = "".join(List)
ans = 0
for i in roots[-1]:
    TF = "".join(sorted(list(i))) == check
    if TF:
        ans = ans + 1

print(ans)

Submission status: Runtime Error

Solution code:

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

def mkmap(N, M):
    mapdic = {}
    for i in range(1, M+1):
        mapdic[str(i)] = [] 
    for j in range(N):
        pathA, pathB = map(str, input().split())
        mapdic[pathA] = mapdic[pathA] + [pathB]
        mapdic[pathB] = mapdic[pathB] + [pathA]
    return mapdic

mapdic = mkmap(N, M)
import copy

roots = [[]]*N
roots[0] = ["1"]
for i in range(N-1):
    root = copy.deepcopy(roots[i])
    for nowroot in root:
        for nextroot in mapdic[nowroot[-1]]:
            if  i >= 1:
                if not nextroot in nowroot:                    
                    roots[i+1] = roots[i+1] + [nowroot + nextroot]
                else:
                    pass
            else:
                roots[i+1] = roots[i+1] + [nowroot + nextroot]

print(len(roots[-1]))

Submission status: Runtime Error

Solution code:
import networkx as nx
n,m=map(int,input().split())
s=[list(map(int,input().split())) for _ in range(m)]
g=nx.Graph()
g.add_edges_from(s)
 
#各部屋の通じてる部屋番のリストを作る
l=[[] for _ in range(n)]
for i in range(m):
    a,b=s[i][0],s[i][1]
    l[a-1].append(b)
    l[b-1].append(a)
#深さのリストを作る
l1=sum(l, []) #一次元化
l1.insert(0,1)
l_depth=list(dict.fromkeys(l1))#深さのリスト
 
# スタート地点からゴール地点までのすべての単純路 (同じ頂点を通らないパス)
k=list(nx.all_simple_paths(g, source=1, target=l_depth[-1]))
 
c=0
ma=0
for i in range(len(k)):
    if len(k[i])>ma:
        ma=len(k[i])
        c-=c+1
    if len(k[i])==ma:
        c+=1
print(c)

Submission status: Runtime Error

Solution code:
import networkx as nx
n,m=map(int,input().split())
s=[list(map(int,input().split())) for _ in range(m)]
g=nx.Graph()
g.add_edges_from(s)
 
#各部屋の通じてる部屋番のリストを作る
l=[[] for _ in range(n)]
for i in range(m):
    a,b=s[i][0],s[i][1]
    l[a-1].append(b)
    l[b-1].append(a)
#深さのリストを作る
l1=sum(l, []) #一次元化
l1.insert(0,1)
l_depth=list(dict.fromkeys(l1))#深さのリスト
 
# スタート地点からゴール地点までのすべての単純路 (同じ頂点を通らないパス)
k=list(nx.all_simple_paths(g, source=1, target=l_depth[-1]))
 
c=0
ma=0
for i in range(len(k)):
    if len(k[i])>ma:
        ma=len(k[i])
        c-=c+1
    elif len(k[i])==ma:
        c+=1
print(c)

Submission status: Runtime Error

Solution code:
import networkx as nx
n,m=map(int,input().split())
s=[list(map(int,input().split())) for _ in range(m)]
g=nx.Graph()
g.add_edges_from(s)
 
#各部屋の通じてる部屋番のリストを作る
l=[[] for _ in range(n)]
for i in range(m):
    a,b=s[i][0],s[i][1]
    l[a-1].append(b)
    l[b-1].append(a)
#深さのリストを作る
l1=sum(l, []) #一次元化
l1.insert(0,1)
l_depth=list(dict.fromkeys(l1))#深さのリスト
 
# スタート地点からゴール地点までのすべての単純路 (同じ頂点を通らないパス)
k=list(nx.all_simple_paths(G, source=1, target=l_depth[-1]))
 
c=0
ma=0
for i in range(len(k)):
    if len(k[i])>ma:
        ma=len(k[i])
        c-=c+1
    elif len(k[i])==ma:
        c+=1
print(c)

Submission status: Runtime Error

Solution code:
import networkx as nx
n,m=map(int,input().split())
s=[list(map(int,input().split())) for _ in range(m)]
g=nx.Graph()
g.add_edges_from(s)

#各部屋の通じてる部屋番のリストを作る
l=[[] for _ in range(n)]
for i in range(m):
    a,b=s[i][0],s[i][1]
    l[a-1].append(b)
    l[b-1].append(a)
#深さのリストを作る
l1=sum(l, []) #一次元化
l1.insert(0,1)
l_depth=list(dict.fromkeys(l1))#深さのリスト

# スタート地点からゴール地点までのすべての単純路 (同じ頂点を通らないパス)
k=list(nx.all_simple_paths(G, source=1, target=l_depth[-1]))

c=0
ma=0
for i in range(k):
    if len(k[i])>ma:
        ma=len(k[i])
        c-=c+1
    elif len(k[i])==ma:
        c+=1
print(c)

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
pathmat=[[0]*N for _ in range(N)]
for _ in range(M):
    a, b = map(int, input().split())
    pathmat[a-1][b-1] = 1
    pathmat[b-1][a-1] = 1

visited =  [False]*N
visited[0] = True
ans = 0

def DFS(now, visited):
    if all(visited):
        return 1
    for i in range(N):
        if not pathmat[now][i]:
            continue
        if visited[i]:
            continue
        visited[i]=True
        ans += DFS(i, visited)
        visited[i]=False
    return ans

print(DFS(0,visited))

Submission status: Runtime Error

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

ans=0
x=[i for i in range(2,n+1)]
cand=permutations(x)
for i in cand:
  crnt=1
  for nxt in i:
    if set([crnt,nxt]) in s:
      crnt=nxt
    else:
      break
  else:
    ans+=1
print(ans)

Submission status: Runtime Error

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

ans=0
x=[i for i in range(2,n+1)]
cand=itertools.permutations(x)
for i in cand:
  crnt=1
  for nxt in i:
    if set([crnt,nxt]) in s:
      crnt=nxt
    else:
      break
  else:
    ans+=1
print(ans)

Submission status: Runtime Error

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

ans=0
x=[i for i in range(2,n+1)]
print(x)
cand=itertools.permutations(x)
print(cand)
for i in cand:
  crnt=1
  for nxt in i:
    if set([crnt,nxt]) in s:
      crnt=nxt
    else:
      break
  else:
    ans+=1
print(ans)

Submission status: Runtime Error

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

N, M = map(int, input().split())
ab = [list(map(int, input().split())) for n in range(N)]
branch = [[False]* N for n in range(N)]

for m in range(M):
  a = ab[m][0] - 1
  b = ab[m][1] -1 
  branch[a][b] = True
  branch[b][a] = True

ans = 0
pattern = list(itertools.permutations(range(1, N+1),N))
for l in pattern:
  if l[0] != 1:
    continue
  for n in range(N):
    if n == N - 1:
      ans += 1
      break
    p = l[n] -1
    np = l[n+1] -1
    if not(branch[p][np]):
      break

print(ans)

Submission status: Runtime Error

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

N, M = map(int, input().split())
ab = [list(map(int, input().split())) for m in range(M)]
branch = [[False]* N for n in range(N)]

for m in range(M):
  a = ab[m][0] - 1
  b = ab[m][1] -1 
  branch[a][b] = True
  branch[b][a] = True

ans = 0
pattern = list(itertools.permutations(range(1, M+1),M))
for l in pattern:
  if l[0]  != 1:
    continue
  for m in range(M):
    if m == M - 1:
      ans += 1
      break
    p = l[m] -1
    np = l[m+1] -1
    if not(branch[p][np]):
      break

print(ans)

Submission status: Runtime Error

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

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

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

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

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

    return ans

print(dfs(0))

Submission status: Runtime Error

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

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

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

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

    return ans

print(dfs(0, visited))

Submission status: Runtime Error

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

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

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

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

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

    return ans

print(dfs(0, visited))

Submission status: Runtime Error

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

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

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

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

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

    return ans

print(dfs(0, visited))

Submission status: Runtime Error

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

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

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

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

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

    return ans

print(dfs(0, visited))

Submission status: Runtime Error

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

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

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

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

    return ans

print(dfs(0, visited))

Submission status: Runtime Error

Solution code:
import itertools
n,m=map(int,input().split())
edge=[0]*m
ans=0
for i in range(0,m):
  a,b=map(int,input().split())
  edge[i]=[a,b]
edge.sort  
print(edge)
if len(node)==0:
  ans=ans+1
print(ans)

Submission status: Runtime Error

Solution code:
import itertools

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