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:
import sys
# 再帰上限を引き上げる
sys.setrecursionlimit(10**6)

####
# DFS(深さ優先探索

count = 0
def dfs(graph, v, seen):
    #print(seen)
    # Falseがない、つまり頂点が1個しかない場合は、1を返す
    if not False in seen:
        global count
        count +=1
        return
    
    # 頂点Vから行ける頂点を全探索
    for i in graph[v]:
        # 行ける場所はTrueである。
        if seen[i]:
            continue
        
        # いったんTrueにして
        seen[i] = True
        # 探索したら
        dfs(graph, i, seen)
        # 戻す
        seen[i] = False
        
    return
        
        

####

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

# グラフを作る
graph = [[] for i in range(N)]
#print(graph)

for i in range(M):
    a, b = map(int, input().split())
    # index番号にあわせたいので、1引く
    a -= 1
    b -= 1
    graph[a].append(b)
    graph[b].append(a)
    
seen = [False for i in range(M)]
seen[0] = True
#print(seen)

dfs(graph, 0, seen)

# 全探索できた数を表示
print(count)

Submission status: Runtime Error

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

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

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

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

def dfs(v, visited):
  if all(visited):
    return 1
  total = 0
  for cv in g[v]:
    if not visited[cv]:
      visited[cv] = True
      total += dfs(v, visited)
      visited[cv] = False
  return total
    
visited[0] = True
ret = dfs(0, visited)
print(ret)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(1000000)
N, M = map(int, input().split())
G = {k: [] for k 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)

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


def dfs(v):
    if all(visited):
        return 1
    r = 0
    for nv in G[v]:
        if visited[nv] is False:
            visited[nv] = True
            r += dfs(nv)
            visited[nv] = False
    return r


print(dfs(0))

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(1000000)
N, M = map(int, input().split())
G = {k: [] for k in range(N+1)}
for _ in range(N):
    a, b = map(int, input().split())
    # 無向グラフ
    G[a-1].append(b-1)
    G[b-1].append(a-1)

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


def dfs(v):
    if all(visited):
        return 1
    r = 0
    for nv in G[v]:
        if visited[nv] is False:
            visited[nv] = True
            r += dfs(nv)
            visited[nv] = False
    return r


print(dfs(0))

Submission status: Runtime Error

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

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


def dfs(v):
    if all(visited):
        return 1
    r = 0
    for nv in G[v]:
        if visited[nv] is False:
            visited[nv] = True
            r += dfs(nv)
            visited[nv] = False
    return r


print(dfs(0))

Submission status: Runtime Error

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

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


def dfs(v):
    if all(visited):
        ans += 1
        return
    for nv in G[i]:
        if visited[nv] is False:
            visited[nv] = True
            dfs(nv)
            visited[nv] = False
    return


ans = 0
dfs(0)
print(ans)

Submission status: Runtime Error

Solution code:
import itertools


N, M = map(int, input().split())
graph = [[False]*N for _ in range(M)]

for _ in range(M):
    a, b = map(lambda x: int(x)-1, input().split())
    graph[a][b] = True
    graph[b][a] = True

ans = 0
for x in itertools.permutations(range(1, N)):
    # このxの順番で訪問できるか確かめる
    flag = True
    now = 0
    for e in x:
        if not graph[now][e]:
            flag = False
        now = e
    if flag:
        ans += 1
print(ans)

Submission status: Runtime Error

Solution code:
import sys

sys.setrecursionlimit(10 ** 9)

def dfs(v, n, graph, visited):
    all_visited = 1

    for i in range(n):
        if visited[i] == 0:
            all_visited = 0
            break

    if all_visited:
        return 1

    n_paths = 0

    for i in range(0, n):
        if not graph[v][i]:
            continue
        if visited[i]:
            continue

        visited[i] = 1
        n_paths += dfs(i, n, graph, visited)
        visited[i] = 0

    return n_paths


def main():
    n, m = [int(i) for i in input().split()]
    if m == 0:
      print(0)
      return None
    graph = [[0] * m for _ in range(m)]
    for _ in range(m):
        a, b = [int(i) for i in input().split()]
        graph[a-1][b-1] = 1
        graph[b-1][a-1] = 1

    visited = [0] * n

    visited[0] = 1
    n_paths = dfs(0, n, graph, visited)
    print(n_paths)


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
import sys

sys.setrecursionlimit(10 ** 9)

def dfs(v, n, graph, visited):
    all_visited = 1

    for i in range(n):
        if visited[i] == 0:
            all_visited = 0
            break

    if all_visited:
        return 1

    n_paths = 0

    for i in range(0, n):
        if not graph[v][i]:
            continue
        if visited[i]:
            continue

        visited[i] = 1
        n_paths += dfs(i, n, graph, visited)
        visited[i] = 0

    return n_paths


def main():
    n, m = [int(i) for i in input().split()]
    graph = [[0] * m for _ in range(m)]
    for _ in range(m):
        a, b = [int(i) for i in input().split()]
        graph[a-1][b-1] = 1
        graph[b-1][a-1] = 1

    visited = [0] * n

    visited[0] = 1
    n_paths = dfs(0, n, graph, visited)
    print(n_paths)


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
def dfs(v, n, graph, visited):
    all_visited = 1

    for i in range(n):
        if visited[i] == 0:
            all_visited = 0
            break

    if all_visited:
        return 1

    n_paths = 0

    for i in range(0, n):
        if not graph[v][i]:
            continue
        if visited[i]:
            continue

        visited[i] = 1
        n_paths += dfs(i, n, graph, visited)
        visited[i] = 0

    return n_paths


def main():
    n, m = [int(i) for i in input().split()]
    graph = [[0] * m for _ in range(m)]
    for _ in range(m):
        a, b = [int(i) for i in input().split()]
        graph[a-1][b-1] = 1
        graph[b-1][a-1] = 1

    visited = [0] * n

    visited[0] = 1
    n_paths = dfs(0, n, graph, visited)
    print(n_paths)


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
N, M = map( int, input().split() )
ab = [ [ int(x) for x in input().split() ] for y in range(M) ]
e = [ [ 0 for x in range(N) ] for y in range(N) ]
flag = [ False for x in range(N) ]
dp = [ 0 for x in range(N) ] #number of path from 1 to i
for i in range(M) :
    e[ ab[i][0]-1 ][ ab[i][1]-1 ] = 1
    e[ ab[i][1]-1 ][ ab[i][0]-1 ] = 1
print( e )         
ct = 0
for i in range(N) :
    for j in range(N) :
        if i == 0 and e[i][j]==1: 
            dp[j] = 1
            flag[j]=True
        elif e[j][i]==1 :
            dp[i] += dp[j]
            flag[j]=True
    if !False in flag :
        ct += 1

print( dp[N-1] )            
#does not count the path which goes through ALL nodes

Submission status: Runtime Error

Solution code:
import itertools

def main():
    N, M = map(int, input().split())
    VE = tuple(tuple(map(lambda x: int(x)-1, input().split())) for _ in range(M))
    # print(VE)

    adj_mat = [[0 for _ in range(N)] for _ in range(M)]
    for ve in VE:
        adj_mat[ve[0]][ve[1]] = 1
        adj_mat[ve[1]][ve[0]] = 1
    # for row in adj_mat:
    #     print(row)

    ans = 0
    for perm in itertools.permutations([i for i in range(1, N)]):
        # print(perm)
        flag = True
        now_V = 0
        for next_V in perm:
            # print('{} to {}'.format(now_V, next_V))
            # print('{}'.format(adj_mat[now_V][next_V]))
            if not adj_mat[now_V][next_V]:
                flag = False
                break
            now_V = next_V
        if flag:
            ans += 1

    print(ans)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())
q = []
for i in range(m):
    a, b = map(int, input().split())
    q.append({a, b})
cnt = 0
array = list(range(1, m+1))
while cnt != 10000:
    a = q.pop()
    for j in q:
        if len(j & a) != 0:  # jとaに共通の値があるならば
            j |= a
            count = 0
            break
        else:  # jとaに共通の値がなければ
            q = [a] + q
    if count > len(q):
        break
    count += 1
    for i in q:
        tmp = list(i)
        if tmp == array:
            cnt += 1
print(cnt)

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())
q = []
for i in range(m):
    a, b = map(int, input().split())
    q.append({a, b})
cnt = 0
array = list(range(1, n+1))
while cnt != 10000:
    a = q.pop()
    for j in q:
        if len(j & a) != 0:  # jとaに共通の値があるならば
            j |= a
            count = 0
            break
        else:  # jとaに共通の値がなければ
            q = [a] + q
    if count > len(q):
        break
    count += 1
    for i in q:
        tmp = list(i)
        if tmp == array:
            cnt += 1
print(cnt)

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())
q = []
for i in range(m):
    a, b = map(int, input().split())
    q.append({a, b})
cnt = 0
while cnt != 10000:
    a = q.pop()
    for j in q:
        if len(j & a) != 0:  # jとaに共通の値があるならば
            j |= a
            count = 0
            break
        else:  # jとaに共通の値がなければ
            q = [a] + q
    if count > len(q):
        break
    count += 1
    for i in q:
        tmp = list(i)
        if tmp == array:
            cnt += 1
print(cnt)

Submission status: Runtime Error

Solution code:
import itertools
n, m = map(int, input().split())
array = list(range(1, n + 1))
p = list(itertools.permutations(array))
q = []
for i in range(m):
    a, b = map(int, input().split())
    q.append({a, b})
cnt = 0
while cnt != 10000:
    a = q.pop()
    for j in q:
        if len(j & a) != 0:  # jとaに共通の値があるならば
            j |= a
            count = 0
            break
        else:  # jとaに共通の値がなければ
            q = [a] + q
    if count > len(q):
        break
    count += 1
    for i in q:
        tmp = list(i)
        if tmp == array:
            cnt += 1
print(cnt)

Submission status: Runtime Error

Solution code:
import sys
import itertools
import math
input = sys.stdin.readline
#sys.setrecursionlimit(1e9)
N,M = map(int,input().split())

ab = [list(map(int,input().split())) for _ in range(M)]

graph=[[0]*8 for _ in range(8)]
def dfs(v,visited):
    if sum(visited) == N:
        return 1
    ret =0
    for i in range(N):
        if graph[v][i] == 1 and visited[i] == 0:
            visited[i]=1
            ret += dfs(i,visited)
            visited[i]=0
    return ret
def main():
    """code here"""

    for i in range(N):
        a=ab[i][0]
        b=ab[i][1]
        graph[a-1][b-1]=1
        graph[b-1][a-1]=1

    visited=[0]*N
    visited[0]=1
    print(dfs(0,visited))




    
    
if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import sys
import itertools
import math
input = sys.stdin.readline
#sys.setrecursionlimit(1e9)
N,M = map(int,input().split())

ab = [list(map(int,input().split())) for _ in range(M)]

graph=[[0]*N for _ in range(N)]
def dfs(v,visited):
    if sum(visited) == N:
        return 1
    ret =0
    for i in range(N):
        if graph[v][i] == 1 and visited[i] == 0:
            visited[i]=1
            ret += dfs(i,visited)
            visited[i]=0
    return ret
def main():
    """code here"""

    for i in range(N):
        a=ab[i][0]
        b=ab[i][1]
        graph[a-1][b-1]=1
        graph[b-1][a-1]=1

    visited=[0]*N
    visited[0]=1
    print(dfs(0,visited))




    
    
if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
from itertools import permutations
n,m=map(int,input().split())
side=[[] for _ in range(n+1)]
for i in range(m):
  a,b=map(int,input().split())
  side[a].append(b)
  side[b].append(a)
route=[i for i in range(2,n+1)]
ans=0
for x in permutations(route):
  x=(1)+x
  for i in range(n-1):
    if x[i+1] not in side[x[i]]:
      break
  else:
    ans+=1
print(ans)

Submission status: Runtime Error

Solution code:
n,m = map(int, input().split())
ls = [tuple(map(int, input().split())) for _ in range(m)]
neighborls = []
for i in range(1,n+1):
    neighbors = []
    for j in range(1, m+1):
        if (i,j) in ls or (j,i) in ls:
            neighbors.append(j)
    neighborls.append(neighbors)

ans = 0

def main():
    global ans
    visitedls = [1]
    ans = dfs(1, visitedls, ans)

    print(ans)
    
        
def dfs(a, visitedls, ans):
    global ans
    if len(visitedls) == n:
        ans += 1
    for i in range(1,n+1):
        if i not in visitedls and i in neighborls[a-1]:
            visitedls.append(i)
            ans = dfs(i, visitedls, ans)
            visitedls.remove(i)
    return ans


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
n,m = map(int, input().split())
ls = [tuple(map(int, input().split())) for _ in range(m)]
neighborls = []
for i in range(1,n+1):
    neighbors = []
    for j in range(1, m+1):
        if (i,j) in ls or (j,i) in ls:
            neighbors.append(j)
    neighborls.append(neighbors)

ans = 0

def main():
    visitedls = [1]
    ans = dfs(1, visitedls, ans)

    print(ans)
    
        
def dfs(a, visitedls, ans):
    if len(visitedls) == n:
        ans += 1
        return ans
    for i in range(1,n+1):
        if i not in visitedls and i in neighborls[a-1]:
            visitedls.append(i)
            ans = dfs(i, visitedls, ans)
            visitedls.remove(i)
    return ans


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
Bs = [[] for _ in range(N + 1)]
for _ in range(M):
    a, b = map(int, input().split())
    Bs[a].append(b)
    Bs[b].append(a)
import heapq

st = []
heapq.heappush(st, (1, {1: True}))
c = 0
while len(st) > 0:
    (node, log) = heapq.heappop(st)
    for b in Bs[node]:
        if b in log:
            continue
        elif len(log) == N - 1:
            c += 1
        else:
            newlog = log.copy()
            newlog[b] = True
            heapq.heappush(st, (b, newlog))
print(c)

Submission status: Runtime Error

Solution code:
import itertools
n,m=map(int,input().split())
p=[[False]*n for i in range(n)]

for i in range(m):
    a,b=map(int,input().split())
    a-=1
    b-=1
    p[a][b]=True
    p[b][a]=True
ans=0
for i in itertools.permutations(range(1,n),n-1):
    list=[0]+[i]
    if all(p[list[j]][list[j+1]]==True for j in range(n)):
        ans+=1
print(ans)

Submission status: Runtime Error

Solution code:
import itertools
n,m=map(int,input().split())
p=[[False]*n for i in range(n)]
ans=0
for i in range(n):
    a,b=map(int,input().split())
    a-=1
    b-=1
    p[a][b]=True
    p[b][a]=True

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

Submission status: Runtime Error

Solution code:
# ABC054C
# 方針：階乗の全探索

import itertools
N, M = map(int, input().split())
# Graph の作成
graph = [[] * N for _ in range(N)]
for i in range(M):
    u, v = map(int, input().split())
    u -= 1
    v -= 1
    graph[u].append(v)
    graph[v].append(u)

# パターンの全列挙
lst = [_ for _ in range(0, N)]
search_list = itertools.permutations(lst)

ans = 0
for lst in search_list:
    flag = True
    if lst[0] != 0:    # 1度でも先頭が0以外ならそれ以降は全てダメ
        break
    for i in range(M-1):
        if lst[i+1] in graph[lst[i]]:   # 今の数字が次の数字と繋がっているかどうか
            pass
        else:
            flag = False
            break
    if flag:
        ans += 1

print(ans)

Submission status: Runtime Error

Solution code:
import itertools

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

p = list(itertools.permutations(range(N)))

Sum = 0

for i in range(len(p)):
    if p[i][0] != 0:
        break
    for j in range(N - 1):
        if graph[p[i][j]][p[i][j + 1]] != 1:
            break
        if j == N - 2:
            Sum += 1

print(Sum)

Submission status: Runtime Error

Solution code:
from itertools import permutation
N,M=map(int,input().split())
ab=[list(map(int,input().split())) for i in range(M)]
g=[[False]*N for i in range(N)]
for a,b in ab:
  g[a-1][b-1]=True
  g[b-1][a-1]=True
nodes=[i for i in range(N)]
ans=0
for route in permutation(nodes):
  for i in range(N):
    if i == N-1:
      ans+=1
      break
    if g[route[i]][route[i+1]]:
      continue
    else:
      break
print(ans)

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
nexts=[None for i in range(n)]
for i in range(n):
  a,b=map(int,input().split())
  a,b=a-1,b-1
  if nexts[a]==None:
    nexts[a]=[b]
  elif b not in nexts[a]:
    nexts[a].append(b)
  if nexts[b]==None:
    nexts[b]=[a]
  elif a not in nexts[b]:
    nexts[b].append(a)

ans=0
stack=[]
stack.append([0,[]])
while stack:
  node=stack.pop()
  v=node[0]
  seen=node[1][:]
  seen.append(v)
  if len(seen)==n:
    ans+=1
    continue
  childs=nexts[v]
  if childs:
    for child in (set(childs)-set(seen)):
      stack.append([child,seen])
  
print(ans)

Submission status: Runtime Error

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

ans=0
stack=[]
stack.append([0,[]])
while stack:
  node=stack.pop()
  v=node[0]
  seen=node[1][:]
  seen.append(v)
  if len(seen)==n:
    ans+=1
    continue
  childs=nexts[v]
  if childs:
    for child in (set(childs)-set(seen)):
      stack.append([child,seen])
  
print(ans)

Submission status: Runtime Error

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

ans=0
stack=[]
stack.append([0,set()])
while stack:
  node=stack.pop()
  v=node[0]
  seen=set(node[1])
  seen.add(v)
  if len(seen)==n:
    ans+=1
    continue
  childs=nexts[v]
  if childs:
    for child in (set(childs)-seen):
      stack.append([child,seen])
  
print(ans)

Submission status: Runtime Error

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

ans=0
stack=[]
stack.append([0,[]])
while stack:
  node=stack.pop()
  v=node[0]
  seen=node[1]
  seen.append(v)
  if len(seen)==n:
    ans+=1
    continue
  childs=nexts[v]
  if childs:
    for child in (set(childs)-set(seen)):
      stack.append([child,seen])
  
print(ans)

Submission status: Runtime Error

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

ans=0
stack=[]
stack.append([0,[]])
while stack:
  node=stack.pop()
  v=node[0]
  seen=node[1]
  seen.append(v)
  if len(seen)==n:
    ans+=1
    continue
  childs=nexts[v]
  if childs:
    for child in (set(childs)-seen):
      stack.append([child,seen])
  
print(ans)

Submission status: Runtime Error

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

ans=0
stack=[]
stack.append([0,set()])
while stack:
  node=stack.pop()
  v=node[0]
  seen=node[1]
  seen.add(v)
  if len(seen)==n:
    ans+=1
    continue
  childs=nexts[v]
  if childs:
    for child in (set(childs)-seen):
      stack.append(child,seen)
  
print(ans)

Submission status: Runtime Error

Solution code:
from itertools import permutations
import numpy as np
N, M = map(int, input().split(" "))#N頂点M辺
mat = [[0] * n for _ in range(n)]
for _ in range(M):
    v1, v2 = map(int, input().split(" "))
    mat[v1 - 1][v2 - 1] = mat[v2 - 1][v1 - 1] = 1

count = 0
for line in permutations(np.arange(N - 1) + 2):
    vtxs = [1] + list(line)
    for i in range(N - 1):
        v1, v2 = vtxs[i], vtxs[i + 1]
        if mat[v1 - 1][v2 - 1] == 0:
            break
    else:
        count += 1
print(count)

Submission status: Runtime Error

Solution code:
nmax = 8
graph = [[0]*nmax for i in range(nmax)]
visited = [0] * nmax

def dfs(v, N, visitied):
  all_visited = True
  for i in range(N):
    if visitied[i] == 0:
      all_visited = False
    if all_visited:
      return 1
  
  ret = 0
  for i in range(N):
    if graph[v][i] == 0:
      continue
    if visited[i] == 0:
      continue
    visited[i] = 1
    ret += dfs(i, N, visited)
    visited[i] = False
  return ret
      

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

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

Submission status: Runtime Error

Solution code:
N,M = map(int,input().split())
G = [[] for i in range(N+1)]
for i in range(M):
    a,b = map(int,input().split())
    G[a].append(b)
    G[b].append(a)
l = [i for i in range(2,N+1)]
import itertools
ans = 0
for v in itertools.permutations(l):
    s = 1
    t = 1
    while v:
        s = t
        t = v.pop(0)
        if t not in G[s]:
            break
    if len(v) == 0:
        ans += 1
print(ans)

Submission status: Runtime Error

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

#1以外の頂点リストを作成
vertex = []
for i in range(N-1):
    vertex.append(i+2)
#順列作成
X = list(itertools.permutations(vertex))

#各値ごとに有無をチェック
ans = 0
for i in X:
    start = 1
    localcount = 0
    for j in i:
        tmp = [start,j]
        tmp.sort()
        if tmp in K:            
            localcount += 1   
        start = j
            
    if localcount == N-1:
        ans += 1

print(ans)

Submission status: Runtime Error

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

#1以外の頂点リストを作成
vertex = []
for i in range(N-1):
    vertex.append(i+2)
#順列作成
X = list(itertools.permutations(vertex))

#各値ごとに有無をチェック
ans = 0
for i in X:
    start = 1
    localcount = 0
    for j in i:
        tmp = [start,j]
        tmp.sort()
        if tmp in K == False:
            break            
        else:
            localcount += 1
            start = j
            
    if localcount == N-1:
        ans += 1

print(ans)

Submission status: Runtime Error

Solution code:
import itertools

N,M=map(int,input().split())
if M==0:
    print(0)
    exit()
S=[list(map(int,input().split()))for _ in range(N) ]

a=[]
for i in range(N):
    a.append(i+1)

L=list(itertools.permutations(a))


cnt=0

for l in L:
    tmp=1
    if l[0]!=1:
        break
    for j in range(N-1):
        if ([l[j],l[j+1]] in S) or ([l[j+1],l[j]] in S):
            tmp=1
        else:
            tmp=0
            break
    if tmp==1:
        cnt+=1

print(cnt)

Submission status: Runtime Error

Solution code:
import itertools

N,M=map(int,input().split())
S=[list(map(int,input().split()))for _ in range(N) ]

a=[]
for i in range(N):
    a.append(i+1)

L=list(itertools.permutations(a))


cnt=0

for l in L:
    tmp=1
    if l[0]!=1:
        break
    for j in range(N-1):
        if ([l[j],l[j+1]] in S) or ([l[j+1],l[j]] in S):
            tmp=1
        else:
            tmp=0
            break
    if tmp==1:
        cnt+=1

print(cnt)

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
g = [[] for _ in range(M + 1)]
for _ in range(M):
    a, b = map(int, input().split())
    g[a].append(b)
    g[b].append(a)

ans = 0
def walk(cur, visited):
    global ans
    tmp = visited + [cur]
    if len(tmp) == N:
        ans += 1
    for nex in g[cur]:
        if nex not in tmp:
            walk(nex, tmp)
walk(1, [])
print(ans)

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
g = [list() for _ in range(M + 1)]
for _ in range(M):
    a, b = map(int, input().split())
    g[a].append(b)
    g[b].append(a)

ans = 0
def walk(cur, visited):
    global ans
    tmp = visited + [cur]
    if len(tmp) == N:
        ans += 1
    for nex in g[cur]:
        if nex not in tmp:
            walk(nex, tmp)
walk(1, [])
print(ans)

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
g = [list() for _ in range(M + 1)]
for _ in range(M):
    a, b = map(int, input().split())
    g[a].append(b)
    g[b].append(a)

ans = 0
def walk(cur, visited):
    global ans, g, N, M
    tmp = visited + [cur]
    if len(tmp) == N:
        ans += 1
    for nex in g[cur]:
        if nex not in tmp:
            walk(nex, visited + [cur])
walk(1, [])
print(ans)

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
g = [list() for _ in range(M + 1)]
for _ in range(M):
    a, b = map(int, input().split())
    g[a].append(b)
    g[b].append(a)

ans = 0
def walk(cur, visited):
    global ans
    tmp = visited + [cur]
    if len(tmp) == N:
        ans += 1
    for nex in g[cur]:
        if nex not in tmp:
            walk(nex, visited + [cur])
walk(1, [])
print(ans)

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
g = [list() for _ in range(M + 1)]
for _ in range(M):
    a, b = map(int, input().split())
    g[a].append(b)
    g[b].append(a)

ans = 0
def walk(cur, visited):
    global ans
    if cur == N:
        ans += 1
        return
    visited.append(cur)
    for nex in g[cur]:
        if nex not in visited:
            walk(nex, visited)
walk(1, [])
print(ans)

Submission status: Runtime Error

Solution code:
N,M = map(int,input().split())
x = [input().split() for i in range(M)]
y = [[] for _ in range(M)]
z = [0 for _ in range(M)]

for i in x:
  y[int(i[0])-1].append(int(i[1])-1)
  y[int(i[1])-1].append(int(i[0])-1)

tmp = y[0]
ans = 0
cnt = 0

while True:
  if cnt != N - 1:
    tmp2 = []
    for l in tmp:
      if z[l] == 0:
        z[l] += 1
        for n in y[l]:
          tmp2.append(n)
    tmp = tmp2
    cnt += 1
  else:
    ans = len(tmp)
    break

print(ans)

Submission status: Runtime Error

Solution code:
from itertools import permutations

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

cnt=0
for i in permutations(range(1,n)):
    if i[0] in tree[0]:
        t_cnt=1
        for j in range(1,len(i)):
            if i[j] in tree[i[j-1]]:
                t_cnt+=1
            else:
                break
        if t_cnt==n-1:
            cnt+=1
print(cnt)

Submission status: Runtime Error

Solution code:
from itertools import permutations

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

cnt=0
for i in permutations(range(1,n)):
    if i[0] in tree[0]:
        t_cnt=1
        for j in range(1,len(i)):
            if i[j] in tree[i[j-1]]:
                t_cnt+=1
            else:
                break
        if t_cnt==m-1:
            cnt+=1
print(cnt)

Submission status: Runtime Error

Solution code:
from itertools import permutations

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

cnt=0
for i in permutations(range(1,m)):
    if i[0] in tree[0]:
        t_cnt=1
        for j in range(1,len(i)):
            if i[j] in tree[i[j-1]]:
                t_cnt+=1
        if t_cnt==m-1:
            cnt+=1
print(cnt)

Submission status: Runtime Error

Solution code:
from collections import defaultdict

def c():
    n, m = map(int, input().split())
    graph = defaultdict(list)
    a1 = None
    for i in range(n):
        a, b = map(int, input().split())
        if i == 0:
            a1 = a
        graph[a].append(b)
        graph[b].append(a)
    stack = []
    count = 0

    if a1:
        stack.append((a1, set()))

    while stack:
        val, visited = stack.pop()
        visited.add(val)
        if len(visited) == m:
            count += 1
            continue

        for g in graph[val]:
            if g not in visited:
                stack.append((g, set(visited)))

    print(count)


if __name__ == '__main__':
    c()

Submission status: Runtime Error

Solution code:
def bfs(u):
  if used.count(True) == N:
    res[0] += 1
    return
  for v in adj[u]:
    if used[v]:
      continue
    used[v] = True
    bfs(v)
    used[v] = False

N, M = map(int, input().split())
adj = [[] for i in range(N)]
for i in range(N):
  u, v = map(lambda x: int(x)-1, input().split())
  adj[u].append(v)
  adj[v].append(u)

used = [False for i in range(N)]
used[0] = True
res = [0]
bfs(0)

print(res[0])