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 _ in range(m)]
for i in range(m):
  a, b  = map(int, input().split())
  l[a-1].append(b-1)
  l[b-1].append(a-1)

import itertools
ans = 0
for p in itertools.permutations(range(n)):
    if p[0] == 0:
        flag = 1
    else:
        flag = 0
        for i in range(n-1):
            if not p[i+1] in l[p[i]]:
                flag = 0
        if flag == 1:
            ans += 1
print(ans)

Submission status: Runtime Error

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

import itertools
ans = 0
for p in itertools.permutations(range(n)):
    if p[0] == 0:
        flag = 1
        for i in range(n-1):
            if not p[i+1] in l[p[i]]:
                flag = 0
        if flag == 1:
            ans += 1
print(ans)

Submission status: Runtime Error

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

import itertools
ans = 0
for p in itertools.permutations(range(n)):
    if p[0] == 0:
        flag = 1
        for i in range(n-1):
            if p[i+1] in l[p[i]]:
                pass
            else:
                flag = 0
    if flag == 1:
        ans += 1
print(ans)

Submission status: Runtime Error

Solution code:
from functools import reduce
import math
import itertools

def main():
    # N! を求める
    # f = math.factorial(N)
    
    # 切り捨て
    # 4 // 3
    # 切り上げ
    #-(-4 // 3)
    
    # 初期値用:十分大きい数(100億)
    # 1e10

    # 初期値用:十分小さい数(-100億)
    # -1e10
    
    # 1文字のみを読み込み
    # 入力:2
    # a = input().rstrip()
    # 変数:a='2'
    
    # スペース区切りで標準入力を配列として読み込み
    # 入力:2 4 5 7
    # a, b, c, d = (int(_) for _ in input().split())  
    # 変数:a=2 b=4 c=5 d =7
    
    # 1文字ずつ標準入力を配列として読み込み
    # 入力:2 4 5 7
    # a = list(int(_) for _ in input().split())
    # 変数:a = [2, 4, 5, 7]    

    # 1文字ずつ標準入力を配列として読み込み
    # 入力:2457
    # a = list(int(_) for _ in input())
    # 変数:a = [2, 4, 5, 7]    
    N,M = (int(_) for _ in input().split())
    a = []
    b = []
    for i in range(N):
        c, d = (int(_) for _ in input().split())
        a.append(c)
        b.append(d)
    l = list(_ for _ in range(2,N+1))
    d = []
    for elem in itertools.permutations(l,len(l)):
        elem = list(elem)
        elem.insert(0,1)
        d.append(elem)
    ans = 0
    for l1 in d:
        flag = True
        for i in range(len(l1)-1):
            for j in range(M):
                if(a[j]==l1[i] and b[j] ==l1[i+1]) or (b[j]==l1[i] and a[j] ==l1[i+1]):
                    flag = True
                    break
                flag = False
            if flag == False:
                break
        if flag:
            ans += 1

    print(ans)
if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(100000)

ans=0


def dfs(v,n,visi):
    allv=True

    for i in visi:
        if not i:
            allv=False

    if allv:
        return 1

    ret=0

    for i in range(n):
        if G[v][i]==False:
            continue
        if visi[i]:
            continue
        visi[i]=True
        ret+=dfs(i,n,visi)
        visi[i]=False

    return ret

n,m=map(int,input().split())
ab=[list(map(int,input().split()))for i in range(m)]
G=[[False for i in range(n)]for i in range(m)]

for a,b in ab:
    G[a-1][b-1]=G[b-1][a-1]=True

visi=[False for i in range(n)]

visi[0]=True

print(dfs(0,n,visi))

Submission status: Runtime Error

Solution code:
from collections import defaultdict
vertices, edges = map(int, input().split(" "))
connect = defaultdict(set)
for i in range(vertices):
    a, b = map(int, input().split(" "))
    connect[a] |= {b}
    connect[b] |= {a}

answer = 0
queue = [[set(), 1]]
while queue:
    visited, now = queue.pop()
    visited |= {now}
    # print(visited, now, need_visit)
    if len(visited) == vertices:
        answer += 1
    else:
        for conn in connect[now]:
            if conn not in visited:
                queue.append([visited | {conn}, conn])
        # print(visited, now, need_visit)

print(answer)

Submission status: Runtime Error

Solution code:
from collections import defaultdict
vertices, edges = map(int, input().split(" "))
connect = defaultdict(set)
for i in range(vertices):
    a, b = map(int, input().split(" "))
    connect[a] |= {b}
    connect[b] |= {a}

comb_answers = defaultdict(int)

def bfs(start, connect, visited):
    queue = [start]
    while queue:
        here = queue.pop()
        visited |= {here}
        for conn in connect[here]:
            if conn not in visited:
                visited |= {conn}
                queue.append(conn)
    return visited
    
for e in connect[1]:
    need_visit = bfs(e, connect, {1})
    temp_answer = 0
    queue = [[{1}, e]]
    while queue:
        visited, now = queue.pop()
        visited |= {now}
        # print(visited, now, need_visit)
        for conn in connect[now]:
            if conn not in visited:
                queue.append([visited | {conn}, conn])
        if visited == need_visit:
            for c in comb_answers.keys():
                if c in visited:
                    comb_answers[c] += 1
                    break
            else:
                comb_answers[e] += 1
            # print(visited, now, need_visit)
answer = 1
for v in comb_answers.values():
    answer *= v

print(answer)

Submission status: Runtime Error

Solution code:
N,M = map(int,input().split())
dict = {}
for m in range(M):
    a,b = map(int,input().split())
    if a in dict:
        dict[a].append(b)
    else:
        dict[a] = [b]
    if b in dict:
        dict[b].append(a)
    else:
        dict[b] = [a]
ans = 0
l = [0 for i in range(N+1)]
l[1] = 1
def dfs(now):
    global l
    global ans
    if sum(l) == N:
        ans += 1
        return(0)
    for i in dict[now]:
        if l[i] == 0:
            l[i] += 1
            now = i
            dfs(l,now)
            l[i] -= 1
        else:
            continue
dfs(l,1)
print(ans)

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
ab = [list(map(int, input().split())) for i in range(M)]
visited = {i:False for i in range(M)}
visited[0] = True
ans = 0

def DFS(x):
  global ans
  nextx = []
  if False not in visited.values():
    ans += 1
    return
  for i in range(M):
    if x in ab[i]:
      xcol = ab[i].index(x)
      if visited[ab[i][1-xcol]-1]:
        continue
      else:
        nextx.append(ab[i][1-xcol])
  for i in nextx:
    visited[i-1] = True
    DFS(i)
    visited[i-1] = False
  return

DFS(1)
print(ans)

Submission status: Runtime Error

Solution code:
from collections import deque
def dfs(v,N,memo):
    ans =0
    if not False in memo.values():
        return 1
    for u in E[v]:
        if memo[u]!=True:
            memo[u] = True
            ans += dfs(u,N,memo)
            memo[u] = False
    return ans
N,M = list(map(int,input().split()))
memo = {i:False for i in range(1,N+1)}
E = {i: []for i in range(1,M+1)}
for i in range(M):
    u,v = list(map(int,input().split()))
    E[u].append(v)
    E[v].append(u)
memo[1] = True
print(dfs(1,N,memo))

Submission status: Runtime Error

Solution code:
from collections import defaultdict
vertices, edges = map(int, input().split(" "))
connect = defaultdict(set)
for i in range(vertices):
    a, b = map(int, input().split(" "))
    connect[a] |= {b}
    connect[b] |= {a}

answer = 0
queue = [[set(), 1]]
while queue:
    visited, now = queue.pop()
    visited |= {now}
    if len(visited) == vertices:
        answer += 1
        continue
    for conn in connect[now]:
        if conn not in visited:
            queue.append([visited | {conn}, conn])
print(answer)

Submission status: Runtime Error

Solution code:
N,M = map(int,input().split())
edge_list = [list() for i in range(N)]
for i in range(M):
        a,b = map(int,input().split())
        edge_list[a-1].append(b-1)
        edge_list[b-1].append(a-1)
done = [0] * n
chk = 0
def dfs(s,done):
    done = done[:]
    global chk
    done[s] = True 
    if all(done):
        chk += 1
    for i in edges[u]:
        if not done[i]:
            dfs(i.done)
    return 0
dfs(0,done)
print(chk)

Submission status: Runtime Error

Solution code:
import sys
n,m=map(int,input().split())
number=[[int(i) for i in l.split()] for l in sys.stdin]
visit=[0]*(n+1)
visit[1]=1
node=[[] for i in range(n+1)]
for i in number:
  node[i[0]].append(i[1])
  node[i[1]].appedn(i[0])
ans=0
def dfs(x):
  global ans
  if visit.count(1)==n:
    ans+=1
    return 0
  for i in node[x]:
    if visit[i]==0:
      visit[i]=1
      dfs(i)
      visit[i]=0
  return 0
dfs(1)
print(ans)

Submission status: Runtime Error

Solution code:
import sys
n,m=map(int,input().split())
number=[[int(i) for i in l.split()] for l in sys.stdin]
visit=[0]*(n+1)
node=[[] for i in range(n+1)]
for i in number:
  node[i[0]].append(i[1])
  node[i[1]].appedn(i[0])
ans=0
def dfs(x):
  global ans
  if visit.count(1)==n:
    ans+=1
    return 0
  for i in node[x]:
    if visit[i]==0:
      visit[i]=1
      dfs(i)
      visit[i]=0
  return 0
dfs(1)
print(ans)

Submission status: Runtime Error

Solution code:
import sys
n,m=map(int,input().split())
number=[[int(i) for i in l.split()] for l in sys.stdin]
visit=[0]*(n+1)
node=[[] for i in range(n+1)]
for i in number:
  node[i[0]].append(i[1])
  node[i[1]].appedn(i[0])
ans=0
def dfs(x):
  global ans
  if visit.count(1)==n:
    ans+=1
    return 0
  for i in visit[x]:
    if visit[i]==0:
      visit[i]=1
      dfs(i)
      visit[i]=0
  return 0
dfs(1)
print(ans)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(20)
n,m=map(int,input().split())
number=[[int(i) for i in l.split()] for l in sys.stdin]
startwithone=[i for i in number if i[0]==1]
notstartwithone=[i for i in number if i[0]!=1]
if len(startwithone)==0:
  print(0)
  exit()
if len(startwithone)==0:
  if n==2:
    print(1)
    exit()
  print(0)
  exit()
ans=0
flag2=0
def find(x):
  if root[x]==x:
    return x
  return find(root[x])
def check(x,y):
  return find(x)==find(y)
def union(x,y):
  if find(1)==find(x):
    root[y]=x
  else:
    root[x]=y
def dfs(i,flag):
  global ans
  global root
  global flag2
  flag2=flag
  if bin(flag)[2:].count("1")!=n-2 or len(notstartwithone)<i:
    if len(notstartwithone)<i:
      return 0
    dfs(i+1,flag|2**i)
    dfs(i+1,flag)
  root=[i for i in defroot]
  rank=[i for i in defrank]
  for j in range(len(notstartwithone)):
    if flag&2**j>0:
      union(notstartwithone[j][0],notstartwithone[j][1])
  for j in range(1,n):
    if check(j,j+1)==False:
      return 0
  if len(set(root))==n:
    ans+=1
for i in startwithone:
  root=[i for i in range(n+1)]
  rank=[0]*(n+1)
  union(i[0],i[1])
  defroot=[i for i in root]
  defrank=[i for i in rank]
  dfs(0,0)
print(ans)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(20)
n,m=map(int,input().split())
number=[[int(i) for i in l.split()] for l in sys.stdin]
startwithone=[i for i in number if i[0]==1]
notstartwithone=[i for i in number if i[0]!=1]
ans=0
flag2=0
def find(x):
  if root[x]==x:
    return x
  return find(root[x])
def check(x,y):
  return find(x)==find(y)
def union(x,y):
  if find(1)==find(x):
    root[y]=x
  else:
    root[x]=y
def dfs(i,flag):
  global ans
  global root
  global flag2
  flag2=flag
  if bin(flag)[2:].count("1")!=n-2 or len(notstartwithone)<i:
    if len(notstartwithone)<i:
      return 0
    dfs(i+1,flag|2**i)
    dfs(i+1,flag)
  root=[i for i in defroot]
  rank=[i for i in defrank]
  for j in range(len(notstartwithone)):
    if flag&2**j>0:
      union(notstartwithone[j][0],notstartwithone[j][1])
  for j in range(1,n):
    if check(j,j+1)==False:
      return 0
  if len(set(root))==n:
    ans+=1
for i in startwithone:
  root=[i for i in range(n+1)]
  rank=[0]*(n+1)
  union(i[0],i[1])
  defroot=[i for i in root]
  defrank=[i for i in rank]
  dfs(0,0)
print(ans)

Submission status: Runtime Error

Solution code:
import sys
n,m=map(int,input().split())
number=[[int(i) for i in l.split()] for l in sys.stdin]
ans=0
root=[i for i in range(n)]
rank=[0]*(n+1)
def find(x):
  if root[x]==x:
    return x
  root[x]=find(root[x])
  return root[x]
def check(x,y):
  return find(x)==find(y)
def union(x,y):
  x=find(x)
  y=find(y)
  if rank[x]>=rank[y]:
    root[y]=x
  else:
    root[x]=y
  if rank[x]==rank[y]:
    rank[x]+=1
def dfs(i,flag):
  if str(flag).count(1)!=n-1:
    if i==m:
      return 0
    dfs(i+1,flag|2**i)
    dfs(i+1|flag)
  root=[i for i in range(n)]
  rank=[0]*(n+1)
  for j in range(m):
    if flag&2**j>0:
      union(number[j][0],number[j][1])
  for j in range(1,n):
    if check(i,i+1)==False:
      return 0
  ans+=1
dfs(0,0)
print(ans)

Submission status: Runtime Error

Solution code:
from log import logger

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

logger.info('key_value: {}\n'.format(key_value))

closed_list = [False] * N
closed_list[0] = True
cnt = 0


def dfs(target):
    global cnt
    logger.info('key_value[target]: {}'.format(key_value[target]))
    if all(closed_list):
        cnt += 1
        return
    for node in key_value[target]:
        logger.info('node: {}'.format(node))
        # 探索済みでない場合
        if closed_list[node] is False:
            closed_list[node] = True
            dfs(node)
            closed_list[node] = False
        logger.info('closed_list: {}\n'.format(closed_list))
    return


dfs(0)
print(cnt)

Submission status: Runtime Error

Solution code:
from log import logger

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

key_value = {}
for i in range(M):
    a, b = input().split()
    try:
        key_value[a].append(b)
    except KeyError:
        key_value[a] = [b]
    try:
        key_value[b].append(a)
    except KeyError:
        key_value[b] = [a]

logger.info("key_value: {}\n".format(key_value))

"""深さ優先探索: depthFirst
# 初期化
# nodeを展開し，nodeをclosed_listに入れる
# 2つの条件を満たしたら，childrenをopen_listに入れる
# # 1. open_listに同じchildrenがない
# # 2. closedに同じchildrenがない
# 条件を満たせばcntをインクリメントする
"""
# 初期化
node = "1"
# 探索対象
open_list = [node]
# 探索済み
closed_list = []

cnt = 0
while True:
    # for i in range(10):
    logger.info(
        "[before] open_list: {}, closed_list: {}".format(open_list, closed_list)
    )
    if len(open_list) == 0:
        break
    else:
        # 先頭を削除し，探索済みに追加する
        node = open_list[0]
        open_list = open_list[1:]
        closed_list.append(node)
        # 結果の照合
        if sorted(closed_list) == list(map(str, range(1, N + 1))):
            cnt += 1
        else:
            # nodeの展開
            try:
                children = key_value[node]
                for i in range(len(children)):
                    if children[i] not in open_list and children[i] not in closed_list:
                        open_list.append(children[i])
            except KeyError:
                pass
    logger.info(
        "[after] open_list: {}, closed_list: {}\n".format(open_list, closed_list)
    )
print(cnt)

Submission status: Runtime Error

Solution code:
n,m=(int(i) for i in input().split())
mtrx=[[int(i) for i in input().split()] for j in range(m)]
mtrx=[[mtrx[j][0]-1,mtrx[j][1]-1] for j in range(m)]

adjacent=[[] for i in range(n)]
#print(adjacent)
for i in range(n):
    adjacent[mtrx[i][0]]+=[mtrx[i][1]]
    adjacent[mtrx[i][1]]+=[mtrx[i][0]]
#print(adjacent)

cnt=[]
def dfs(path):
    p=path[-1]
    if len(set(path))==n:
#        print(path)
        cnt.append(1)
        return
    else:
        for x in adjacent[p]:
            if x in path:
                continue
            else:
                path.append(x)
                dfs(path)
                path.pop()
dfs([0])

print(len(cnt))

Submission status: Runtime Error

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

d = [0]*n
d[0] = 1
cnt = 0


def dfs(x):
    global cnt
    if all(d):
        cnt += 1
        return
    for i in D[x]:
        if d[i] == 0:
            d[i] = 1
            dfs(i)
            d[i] = 0


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

d = [0]*n
d[0] = 1
cnt = 0


def dfs(x):
    global cnt
    if all(d):
        cnt += 1
        return
    for i in D[x]:
        if d[i] == 0:
            d[i] = 1
            dfs(i)
            d[i] = 0


dfs(0)
print(cnt)

Submission status: Runtime Error

Solution code:
n,m=(int(i) for i  in input().split())
#print(n,m)
mtrx=[[int(i)-1 for i in input().split()] for j in range(m)]
#print(mtrx)
adjacent=[[i] for i in range(n)]
#print(adjacent)
for i in range(n):
    adjacent[mtrx[i][0]]+=[mtrx[i][1]]
    adjacent[mtrx[i][1]]+=[mtrx[i][0]]
#print(adjacent)

cnt=[]
def dfs(goal,path):
    p=path[-1]
    if p==goal:
        cnt.append(len(set(path)))
        return
    else:
        for x in adjacent[p]:
            if x in path:
                continue
            else:
                path.append(x)
                dfs(goal,path)
                path.pop()

for i in range(1,n):
    dfs(i,[0])                
if m==0:
  print(0)
else:
  print(cnt.count(n))

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())
D = [list() for i in range(n)]
for i in range(m):
    a, b = map(int, input().split())
    D[a-1].append(b-1)
    D[b-1].append(a-1)
 
d = [0]*n
d[0] = 1
cnt = 0
 
 
def dfs(x):
    global cnt
    if all(d):
        cnt += 1
        return
    for i in D[x]:
        if d[i] == 0:
            d[i] = 1
            dfs(i)
            d[i] = 0
 
 
dfs(0)
print(cnt)
n, m = map(int, input().split())
D = [list() for i in range(n)]
for i in range(m):
    a, b = map(int, input().split())
    D[a-1].append(b-1)
    D[b-1].append(a-1)
 
d = [0]*n
d[0] = 1
cnt = 0
 
 
def dfs(x):
    global cnt
    if all(d):
        cnt += 1
        return
    for i in D[x]:
        if d[i] == 0:
            d[i] = 1
            dfs(i)
            d[i] = 0
 
 
dfs(0)
print(cnt)

Submission status: Runtime Error

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

d = [0]*n
d[0] = 1
cnt = 0


def dfs(x):
    global cnt
    if all(d):
        cnt += 1
        return
    for i in D[x]:
        if d[i] == 0:
            d[i] = 1
            dfs(i)
            d[i] = 0


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

d = [0]*n
d[0] = 1
cnt = 0


def dfs(x):
    global cnt
    if all(d):
        cnt += 1
        return
    for i in D[x]:
        if d[i] == 0:
            d[i] = 1
            dfs(i)
            d[i] = 0


dfs(0)
print(cnt)

Submission status: Runtime Error

Solution code:
n,m=(int(i) for i  in input().split())
#print(n,m)
mtrx=[[int(i)-1 for i in input().split()] for j in range(m)]
#print(mtrx)
adjacent=[[i] for i in range(n)]
#print(adjacent)
for i in range(n):
    adjacent[mtrx[i][0]]+=[mtrx[i][1]]
    adjacent[mtrx[i][1]]+=[mtrx[i][0]]
#print(adjacent)

cnt=[]
def dfs(goal,path):
    p=path[-1]
    if p==goal:
        cnt.append(len(set(path)))
        return
    else:
        for x in adjacent[p]:
            if x in path:
                continue
            else:
                path.append(x)
                dfs(goal,path)
                path.pop()

for i in range(1,n):
    dfs(i,[0])                

print(cnt.count(n))

Submission status: Runtime Error

Solution code:
n,m=(int(i) for i  in input().split())
#print(n,m)
mtrx=[[int(i)-1 for i in input().split()] for j in range(m)]
#print(mtrx)
adjacent=[[] for i in range(n)]
#print(adjacent)
for i in range(n):
    adjacent[mtrx[i][0]]+=[mtrx[i][1]]
    adjacent[mtrx[i][1]]+=[mtrx[i][0]]
#print(adjacent)

cnt=[]
def dfs(goal,path):
    p=path[-1]
    if p==goal:
        cnt.append(len(path))
        return
    else:
        for x in adjacent[p]:
            if x in path:
                continue
            else:
                path.append(x)
                dfs(goal,path)
                path.pop()

for i in range(1,n):
    dfs(i,[0])                

print(cnt.count(n))

Submission status: Runtime Error

Solution code:
n,m=(int(i) for i  in input().split())
#print(n,m)
mtrx=[[int(i)-1 for i in input().split()] for j in range(m)]
#print(mtrx)
adjacent=[[i] for i in range(n)]
#print(adjacent)
for i in range(n):
    adjacent[mtrx[i][0]]+=[mtrx[i][1]]
    adjacent[mtrx[i][1]]+=[mtrx[i][0]]
#print(adjacent)

cnt=[]
def dfs(goal,path):
    p=path[-1]
    if p==goal:
        cnt.append(len(path))
        return
    else:
        for x in adjacent[p]:
            if x in path:
                continue
            else:
                path.append(x)
                dfs(goal,path)
                path.pop()

for i in range(1,n):
    dfs(i,[0])                

print(cnt.count(n))

Submission status: Runtime Error

Solution code:
n, m = [int(x) for x in input().split(' ')]

edges = set([tuple(input().split(' ')) for _ in range(n)])
edges.update([(x[1], x[0]) for x in list(edges)])


def dfs(node, history):
    ans = 0
    if len(history) == n - 1:
        return 1

    nextnodes = [
        x[1] for x in edges if x[1] not in history and x[0] == node and x[1] != node
    ]
    history.add(node)
    for next in nextnodes:
        ans += dfs(next, history)
    history.remove(node)
    return ans


print(dfs('1', set()))

Submission status: Runtime Error

Solution code:
n, m = [int(x) for x in input().split(' ')]

edges = set([tuple(input().split(' ')) for _ in range(n)])
edges.update([(x[1], x[0]) for x in list(edges)])


def dfs(node, history):
    ans = 0
    if len(history) == n - 1:
        print(history)
        return 1

    nextnodes = [
        x[1] for x in edges if x[1] not in history and x[0] == node and x[1] != node
    ]
    history.add(node)
    for next in nextnodes:
        ans += dfs(next, history)
    history.remove(node)
    return ans


print(dfs('1', set()))

Submission status: Runtime Error

Solution code:
n, m = [int(x) for x in input().split(' ')]

edges = set([tuple(input().split(' ')) for _ in range(n)])
edges.update([(x[1], x[0]) for x in list(edges)])


def dfs(node, history):
    ans = 0
    if len(history) == n:
        return 1

    nextnodes = [
        x[1] for x in edges if x[1] not in history and x[0] == node and x[1] != node
    ]
    for next in nextnodes:
        ans += dfs(next, history | set(next))
    return ans


print(dfs('1', set(['1'])))

Submission status: Runtime Error

Solution code:
import numpy as np
N, M = map(int, input().split())
 
G = np.zeros((N, M)) 
total_path_num = 0
not_reach_node = list(range(1, N))
node = 0
 
for i in range(M):
  a, b = map(int, input().split())
  G[a-1, b-1] += 1
  G[b-1, a-1] += 1
  
def search_path(G, not_reach_node, node):
  global total_path_num
  if len(not_reach_node) == 0:
    total_path_num += 1
    return total_path_num
  
  for x in np.where((G[node] == 1))[0]:
    try:
      if (x in not_reach_node):
        not_reach_node_copy = not_reach_node.copy()
        not_reach_node_copy.remove(x)
        search_path(G, not_reach_node_copy, x)
    except:
      pass
        
search_path(G, not_reach_node, node)      	
 
print(total_path_num)

Submission status: Runtime Error

Solution code:
import numpy as np
N, M = map(int, input().split())

G = np.zeros((N, M)) 
total_path_num = 0
not_reach_node = list(range(1, N))
node = 0

for i in range(M):
  a, b = map(int, input().split())
  G[a-1, b-1] += 1
  G[b-1, a-1] += 1
  
def search_path(G, not_reach_node, node):
  global total_path_num
  if len(not_reach_node) == 0:
    total_path_num += 1
    return total_path_num
  
  for x in np.where((G[node] == 1))[0]:
    if (x in not_reach_node):
      not_reach_node_copy = not_reach_node.copy()
      not_reach_node_copy.remove(x)
      search_path(G, not_reach_node_copy, x)
        
search_path(G, not_reach_node, node)      	

print(total_path_num)

Submission status: Runtime Error

Solution code:
import itertools

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

count = 0
for V in itertools.permutations(range(1, N)):
    if V[0] in E[0] and all(V[i] in E[V[i-1]] for i in range(1, N-1)):
        count += 1
print(count)

Submission status: Runtime Error

Solution code:
import itertools

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

count = 0
for V in itertools.permutations(range(1, N)):
    if V[0] in E[0] and all(V[i] in E[V[i-1]] for i in range(1, N-1)):
        count += 1
print(count)

Submission status: Runtime Error

Solution code:
import itertools

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

count = 0
#V = (1,2,3,4,5,6), (1,2,3,4,6,5) ... 
for V in itertools.permutations(range(1, N)):
    if V[0] in E[0] and all(V[i] in E[V[i-1]] for i in range(1, N-1)):
        count += 1
print(count)

Submission status: Runtime Error

Solution code:
import itertools

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

count = 0
for V in itertools.permutations(range(1, N)):
    if V[0] in E[0] and all(V[i] in E[V[i-1]] for i in range(1, N-1)):
        count += 1
print(count)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)


def read_int():
    return int(input())


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


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, M, AB):
    g = defaultdict(set)

    for a, b in AB:
        g[a].add(b)
        g[b].add(a)

    ans = 0
    for ns in permutations(range(2, N+1), N-1):
        ns = list(ns)
        ns.insert(0, 1)
        for i in range(N-1):
            if ns[i+1] not in g[ns[i]]:
                break
        else:
            ans += 1
    return ans


def main():
    N, M = read_int_n()
    AB = [read_int_n() for _ in range(N)]
    print(slv(N, M, AB))


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import itertools

n,m=(int(i) for i in input().split())
#print(n,m)
alist=[]
for i in range(m):
  a,b=(int(i) for i in input().split())
  alist.append(10*a+b)
  alist.append(10*b+a)

#print(alist)
ans=0
mylist=list(itertools.permutations(range(2,m+1)))
#print(mylist)
for j in range(len(mylist)):
  mylist1=[10+mylist[j][0]]
  for i in range(m-2):
    mylist1.append(10*mylist[j][i]+mylist[j][i+1])
#  print(mylist1)
  test=0
  for i in range(len(mylist1)):
    if alist.count(mylist1[i]) > 0:
      test+=1
  if len(mylist1)==test:
    ans+=1
    
print(ans)

Submission status: Runtime Error

Solution code:
#C問題
N,M = map(int,input().split())
ab=[list(map(int,input().split())) for i in range(M)]
reach=[-1]*(N)
reach[0]=0
ans=0
def cdfs(n):
    global ans
    global reach
    if sum(reach)==0:
        ans+=1
        reach=[-1]*(N)
        reach[0]=0
        return
    else:
        for j in range(N):
            if reach[j] == -1 and ([n+1,j+1] in ab or [j+1,n+1] in ab):
                reach[j] = 0
                cdfs(j)
                reach[j] = -1
            else:
                pass
        return
reach[0]=0
cdfs(0)
print(ans)

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
A = [list(map(int, input().split())) for _ in range(N)]

V = [i+1 for i in range(N)]
import itertools

ptr = list(itertools.permutations(V, N))

res = 0
for p in ptr:       
    if p[0] == 1:
        now = 1
        flag = [0 for _ in range(N)]
        flag[0] = 1
        for i in range(N-1):
            for j in range(M):
                if A[j][0] == now and A[j][1] == p[i+1]:
                    flag[A[j][1] - 1] += 1
                    now = p[i+1]
                if A[j][1] == now and A[j][0] == p[i+1]:
                    flag[A[j][0] - 1] += 1
                    now = p[i+1]
                    
        tmp = 1         
        for i in range(N):
            if flag[i] != 1:
                tmp = 0
                break
                
        res += tmp
 
print(res)