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**7) #再帰関数の呼び出し制限
N, M = map(int, input().split())
A = [0]*(N+1)
for i in range(M):
    a, b = map(int, input().split())
    A[a].append([b])
    A[b].append([a])
visited=[1]+[0]*N
ans = 0
def DFS(x):
    if visited[x] == 1:
        return
    if sum(visited) == N:
        ans += 1
    visited[x] = 1
    for i in range(N):
        DFS(A[x][i])
print(ans)

Submission status: Runtime Error

Solution code:
from collections import deque

def dfs(v, P, visited, N):
    if len(list(filter(lambda x: x == True, visited))) == N:
        return 1

    c = 0
    for i in P[v]:
        if visited[i]: continue
        visited[i] = True
        c += dfs(i, P, visited, N)
        visited[i] = False

    return c

def resolve():
    N, M = map(int, input().split())
    P = [[] for _ in range(M)]
    for i in range(N):
        pp, ss = map(int, input().split())
        P[pp-1].append(ss-1)
        P[ss-1].append(pp-1)

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

    print(dfs(0, P, visited, N))

resolve()

Submission status: Runtime Error

Solution code:
from collections import deque

def dfs(v, P, visited, N):
    if len(list(filter(lambda x: x == True, visited))) == N:
        return 1

    c = 0
    for i in P[v]:
        if visited[i]: continue
        visited[i] = True
        c += dfs(i, P, visited, N)
        visited[i] = False

    return c

def resolve():
    N, M = map(int, input().split())
    P = [[] for _ in range(N)]
    for i in range(N):
        pp, ss = map(int, input().split())
        P[pp-1].append(ss-1)
        P[ss-1].append(pp-1)

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

    print(dfs(0, P, visited, N))

resolve()

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
dict = {i+1:[] for i in range(M)}
for _ in range(M):
    a, b = map(int, input().split())
    dict[a].append(b)
    dict[b].append(a)
    
def DFS(visited, sight, cnt):
    if(len(visited) == N):
        return cnt+1
    for num in dict[sight]:
        if num in visited:
            continue
        cnt = DFS(visited+[num], num, cnt)
    return cnt

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

Submission status: Runtime Error

Solution code:
import sys
from math import *
from collections import deque, Counter, defaultdict
from fractions import gcd
from itertools import permutations
input = lambda: sys.stdin.readline().rstrip()

def eprint(s):
    sys.stderr.write('DEBUG: {}'.format(s))
    return


def main():
    n,m = map(int, input().split())
    graph = [[0 for _ in range(m)] for _ in range(m)]
    for i in range(m):
        a,b = map(int, input().split())
        graph[a-1][b-1] = 1
        graph[b-1][a-1] = 1
    # n!通りの並べ方があり，各並べ方について成立するかどうかを調べる．
    # 成立しないと判明した時点で探索をやめる
   
    a = [i+1 for i in range(n)]
    p = permutations(a)

    def check(x):
        # x: (1,3,4,6,7,2)
        for i in range(n-1):
            if not graph[x[i]-1][x[i+1]-1]:
                return False
        return True
    cnt = 0
    for x in p:
        if x[0] != 1:
            continue
        if check(x):
            cnt += 1       
    print(cnt)
    return

if __name__ == '__main__':
    main()

Submission status: Runtime Error

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

def my_permutations(nums, t, path):
    if len(nums) == 0:
        path.append(t)
        return
    for i in range(len(nums)):
        my_permutations(nums[:i] + nums[i + 1:], t + [nums[i]], path)

def dfs(graph, permu, n):
    visited = [False] * (n + 1)
    next_nodes = set([1])
    for p in permu:
        if visited[p]:
            return False
        if p not in next_nodes:
            return False
        visited[p] = True
        next_nodes = set(graph[p])
    return True

path = []
my_permutations([i for i in range(1, n + 1)], [], path)
ans = 0
for permu in path:
    if permu[0] != 1:
        continue
    if dfs(graph, permu, n):
        ans += 1
print(ans)

Submission status: Runtime Error

Solution code:
#054_C
from itertools import permutations
n,m=map(int,input().split())
edges=[[False for _ in range(n)] for _ in range(n)]
for _ in range(m):
    a,b=map(int,input().split())
    a,b=a-1,b-1
    edges[a][b]=edges[b][sa]=True

ans=0
for l in permutations(range(1,n),n-1):
    l=[0]+list(l)
    if all(edges[l[i]][l[i+1]] for i in range(n-1)):
        ans+=1
print(ans)

Submission status: Runtime Error

Solution code:
res = 0
def main():
    import sys
    #input = sys.stdin.readline
    sys.setrecursionlimit(10000000)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations
    #from itertools import accumulate, product, permutations
    from math import floor, ceil

    #mod = 1000000007


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

    visited = [0]*N

    def dfs(node):
      	global res
        visited[node]=1
        if all(visited):
            res += 1
            return
        for n_node in g[node]:
                if not visited[n_node]:
                    dfs(n_node)
                    visited[n_node] = 0
    dfs(0)
    print(res)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
from itertools import permutations
n, m = map(int, input().split())
LST = [[0]*2 for _ in range(m)]
for i in range(m):
    a, b = map(int, input().split())
    LST[i][0] = a - 1
    LST[i][1] = b - 1

roots = list(permutations(range(m)))
ans = 0

for root in roots:
    tmp = 0
    if root[0] != 0:
        continue
    for i in range(n-1):
        path = sorted([root[i], root[i+1]])
        if path in LST:
            tmp += 1
    if tmp == n - 1:
        ans += 1

print(ans if m != 0 else 0)

Submission status: Runtime Error

Solution code:
from itertools import permutations
n, m = map(int, input().split())
LST = [[0]*2 for _ in range(m)]
for i in range(m):
    a, b = map(int, input().split())
    LST[i][0] = a - 1
    LST[i][1] = b - 1

roots = list(permutations(range(m)))
ans = 0
for root in roots:
    tmp = 0
    if root[0] != 0:
        continue
    for i in range(n-1):
        path = sorted([root[i], root[i+1]])
        if path in LST:
            tmp += 1
    if tmp == n - 1:
        ans += 1

print(ans)

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
graph ={i+1:[] for i in range(N)}
for _ in range(N):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)
    
def DFS(graph, start, end):
    stack = [start]
    visited = []
    cnt = 0
    while stack:
        label = stack.pop(0)
        if label == end:
            visited.append(label)
            cnt += 1
        if label not in visited:
            visited.append(label)
            stack = graph.get(label, [])+stack
    return cnt
print(DFS(graph, 1, N))

Submission status: Runtime Error

Solution code:
import itertools

n, m = map(int, input().split())
am = [[False]*m for _ in range(n)]

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

ans = 0
for p in itertools.permutations(list(range(n)), n):
    if p[0] != 0:
        continue

    isok = True
    for i in range(len(p)-1):
        if not am[p[i]][p[i+1]]:
            isok = False
            break

    if isok:
        ans += 1

print(ans)

Submission status: Runtime Error

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

for _ in range(M):
	a, b = map(int, input().split())
	V[a - 1].append(b - 1)
	V[b - 1].append(a - 1)
	
	
ctr = 0	
	
def dfs(a, lst):
	lst.append(a)
	global ctr
	if len(lst) == N:
		ctr += 1
		return 0
	for v in V[a]:
		if v in lst: continue
		return dfs(v, lst)
		
dfs(0, [])

print(ctr)

Submission status: Runtime Error

Solution code:
#深さ優先探索
N, M = map(int,input().split())
graph = [[] for j in range(N)]
for i in range(M):
  a, b = map(int,input().split())
  graph[a-1].append(b-1)
  graph[b-1].append(a-1)
judge = [False]*N

def dfs(v,judge):#vは今いる場所
  if all(judge):
    return 1
  res = 0
  for nv in graph(v):#vと隣り合っている場所
    if judge[nv] == True:#すでに探索済み
      continue #if文の初めに戻る
    judge[nv] = True
    res += dfs(nv,judge)
    judge[nv] = False
  return res
print(dfs(0,judge))

Submission status: Runtime Error

Solution code:
N,M = gets.split.map(&:to_i)
 
g = Array.new(N){Array.new(N)}
 
M.times do |i|
  
  a,b = gets.split.map(&:to_i).sort.reverse
  a -= 1
  b -= 1
  g[a][b] = g[b][a] = 1
end
 
pattern = [*1...N].permutation.to_a.map{ |k| [0] + k }

ans = 0
pattern.each do |p|
  
  f = true
  (1...N).each do |i|
    p [p[i-1], p[i]]
    if g[p[i-1]][p[i]].nil?
      f = false
      break
    end
  end
  ans += 1 if f
end
 
puts ans

Submission status: Runtime Error

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

visited = [False] * N
visited[0] = True
d = {}
for a, b in A:
    d.setdefault(b-1, []).append(a-1)
    d.setdefault(a-1, []).append(b-1)

l = sorted(d.items())

def dfs(v, seen):
    if False not in seen: return 1
    
    c = 0
    for i in d[v]:
        if (seen[i]): continue
        seen[i] = True
        c += dfs(i, seen)
        seen[i] = False
    return c
    
print(dfs(0, visited))

Submission status: Runtime Error

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

visited = [False] * N
visited[0] = True
d = {}
for a, b in A:
    d.setdefault(a, []).append(b)
    d.setdefault(b, []).append(a)

l = sorted(d.items())

# print(d)
def dfs(v, c):
    if visited[v-1]: return 0
    visited[v-1] = True
    if False not in visited:
        c += 1
    
    # print(visited, False not in visited, c)
    
    # print('vertex', v)
    
    for next_v in d[v]:
        c += dfs(next_v, c)
    
    return c

c = 0
ans = 0
for i in l[0][1]:
    ans += dfs(i, c)
    
print(ans)

Submission status: Runtime Error

Solution code:
def df_search(searchNode,node,sss,i):
    global cnt
    ss=sss+1
    sn=searchNode
    sn.append(i)
    if(hantei==sorted(sn)):
        if(ans==[]):
            cnt+=1
            ans.append(searchNode)
        else:
            for an in ans[:]:
                if(an != searchNode):
                    cnt+=1
                    ans.append(searchNode)
    for i in node:
        if(i not in sn):
            df_search(sn[:],df_dic[i],ss,i)

ans=[]
lis=[]
df_dic=dict()

NODES,EDGE=map(int,input().split())
df_flag = [0 for i in range(NODES)]  # 探索状況[0:未探索, 1:探索済み] 初期値：0
for i in range(EDGE):
    lis.append(list(map(int,input().split())))
    df_dic[i+1]=[]
for i in lis:
    df_dic[i[0]].append(i[1])
    df_dic[i[1]].append(i[0])
cnt=0
hantei=[i for i in range(1,EDGE+1)]
df_search([],df_dic[1],0,1)
print(cnt)

Submission status: Runtime Error

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

count = 0
def func(path,p):
  if len(path) == n:
    count += 1
    return
  for i in graph[p]:
    if i in path:
      continue
    func(path+[i],i)
print(count)

Submission status: Runtime Error

Solution code:
N, M = list(map(int, input().split()))
ab = {i:[] for i in range(N)}
for _ in range(M):
    a, b = list(map(int, input().split()))
    ab[a-1].append(b-1)
    ab[b-1].append(a-1)
    
cand = [[0]+[one] for one in ab[0]]
while len(cand)>0:
    tmp_cand = []
    for c in cand:
        last = c[-1]
        n = []
        for nc in ab[last]:
            if nc not in c:
                n.append(c+[nc])
        tmp_cand.extend(n)
    cand = tmp_cand
    if len(cand[0])==N:
        break
print(len(cand))

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
matrix=[[0]*N for i in range(N)]
for i in range(M):
    a, b = map(int, input().split())
    matrix[a-1][b-1]=1
    matrix[b-1][a-1]=1
import itertools 
count=0
for i in itertools.permulations(range(N)):
    if i[0]==0:
        for j in range(N-1):
            result=1
            result*=matrix[i[j]][i[j+1]]
            if result==1:
                count+=1
    else:
        break
print(count)

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
matrix=[[0]*N for i in range(N)]
for i in range(M):
    a, b = map(int, input().split())
    matrix[a-1][b-1]=1
    matrix[b-1][a-1]=1
import itertools 
count=0
for i in itertools.permulations(range(N)):
    if i[0]==0:
        for j in range(N-1):
            result=1
            result*=matrix[i[j]][i[j+1]]
            if result=1:
                count+=1
    else:
        break
print(count)

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
matrix=[[0]*N for i in range(N)]
for i in range(M):
    a, b = map(int, input().split())
    matrix[a-1][b-1]=1
    matrix[b-1][a-1]=1
import itertools 
count=0
result=1
for i in itertools.permulations(range(N)):
    if i==0:
        for j in range(N-1):
            result*=matrix[i[j]][i[j+1]]
            if result=1:
                count+=1
            else:
                result=1
    else:
        break
print(count)

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
matrix=[[0]*N for i in range(N)]
for i in range(M):
    a, b = map(int, input().split())
    matrix[a-1][b-1]=1
    matrix[b-1][a-1]=1
import itertools 
count=0
result=1
for i in itertools.permulations(range(1, N+1)):
    if i==1:
        for j in range(N-1):
            result+=matrix[i[j]][i[j+1]]
            if result=1:
                count+=1
            else:
                result=1
    else:
        break
print(count)

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
matrix=[[0]*N for i in range(N)]
for i in range(M):
    a, b = map(int, input().split())
    matrix[a-1][b-1]=1
    matrix[b-1][a-1]=1
import itertools 
count=0
result=1
for i in itertools.permulations(range(1, N+1)):
    if i==1:
        for j in range():
            result+=matrix[i[j]][i[j+1]]
            if result=1:
                count+=1
            else:
                result=1
print(count)

Submission status: Runtime Error

Solution code:
def dfs(v,been):
    if len(been) == n:
        ans.append(1)
        #print(been)
        return
    for i in graph[v]:
        if i in been:
            pass
        else:
            been.add(i)
            dfs(i,been)
            been.remove(i)
    return

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

ans = []

dfs(1,set([1]))
print(sum(ans))

Submission status: Runtime Error

Solution code:
from itertools import permutations

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

ans = 0
for p in permutations(range(N), r=N):
    if p[0] != 0:
        continue
    for i in range(1, N):
        f, t = p[i-1:i+1]
        if adjacent[f][t] != 1:
            break
    else:
        ans += 1
print(ans)

Submission status: Runtime Error

Solution code:
from itertools import permutations

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

ans = 0
for p in permutations(range(1, N), r=N-1):
    start, end = 0, p[0]
    if adjacent[start][end] != 1:
        continue
    for i in range(1, N-1):
        start, end = end, p[i]
        if adjacent[start][end] != 1:
            break
    else:
        ans += 1
print(ans)

Submission status: Runtime Error

Solution code:
def search(node, searched, goal):
  if searched == goal:
    return 1
  v = 0
  for nei in edges[node]:
    if searched & (1 << nei):
      continue
    v += search(nei, searched | (1<<nei), goal)
    
  return v
n, m = map(int, input().split())
edges = [[] for _ in range(n)]
for i in range(n):
  a, b = map(lambda x: int(x) - 1, input().split())
  edges[a].append(b)
  edges[b].append(a)
print(search(0, 1, (1<<n) - 1))

Submission status: Runtime Error

Solution code:
from itertools import permutations, tee

N, M = map(int, input().split())
edges = set()
for _ in range(N):
   a, b = map(int, input().split())
   edges.add((a, b))   

def each_cons(iterable):
  a, b = tee(iterable)
  next(b, None)
  return zip(a, b)

cases = list(permutations(range(2, N + 1), N - 1))

count = 0

def is_available(edge):
  return edge in edges or edge[::-1] in edges

for numbers in cases:
  if all(map(is_available, each_cons((1,) + numbers))):
    count += 1
         
print(count)

Submission status: Runtime Error

Solution code:
from itertools import permutations
n,m=map(int,input().split())
l=[list(map(int,input().split())) for i in range(m)]
p=[i for i in range(1,n+1)]
np=list(permutations(p))
edge=[[] for i in range(m)]
for i in range(m):
  edge[l[i][0]-1].append(l[i][1]-1)
  edge[l[i][1]-1].append(l[i][0]-1)
ans=0
for i in range(len(np)):
  if np[i][0]!=1:
    continue
  else:
    ok=True
    for j in range(n-1):
      if np[i][j]-1 not in edge[np[i][j+1]-1]:
        ok=False
    if ok:
      ans+=1
print(ans)

Submission status: Runtime Error

Solution code:
import sys
import copy
from queue import Queue
sys.setrecursionlimit(1000000000)

def dfs(start, paths, count):
    if count <= 1:
        return 1
    
    indixies = findNodeIndex(start, paths)
    if len(indixies) == 0:
        return 0
    count = 0
    for i in indixies:
        nextNode = paths[i][1] if paths[i][0] == start else  paths[i][0]
        newPaths = copy.deepcopy(paths)
        newPaths.pop(i)
        count += dfs(nextNode, newPaths, count - 1)
    return count

def findNodeIndex(node, paths):
    return [i for (i, row) in filter(lambda x: x[1][0] == node or x[1][1] == node, [(i, row) for i, row in enumerate(paths)])]

N, M = map(int, input().split())
PATHS = [list(map(int, input().split())) for _ in range(N)]
#start = findNodeIndex(1, PATHS)

print(dfs(1, PATHS, M))

Submission status: Runtime Error

Solution code:
#include <bits/stdc++.h>
using namespace std;
#define ll unsighned long int

int n,m;

int ans = 0;



void solve(vector<vector<int> > v,vector<int> dist,int pos = 1,int k = 1){
    //cout << ans << endl;
    if(k == n){
        ans++;
        return ;
    }
    for(int i = 0; i < v[pos - 1].size(); ++i){
        if(dist[v[pos - 1][i] - 1] != 1){
            dist[v[pos - 1][i] - 1] = 1;
            solve(v,dist,v[pos - 1][i],k + 1);
            dist[v[pos - 1][i] - 1] = -1;
        }
    }
}


int main(){
    cin >> n >> m;
    //cout << n << " " << m << endl;

    vector<vector<int> > v(n,0);

    vector<int> dist(n,-1);


    dist[0] = 1;

    for(int i = 0; i < m; ++i){
        int a,b;
        cin >> a >> b;
        v[a - 1].push_back(b);
        v[b - 1].push_back(a);
    }
    solve(v,dist);
    cout << ans << endl;
}

Submission status: Runtime Error

Solution code:
#include <bits/stdc++.h>
using namespace std;
#define ll unsighned long int

int n,m;

int ans = 0;



void solve(vector<vector<int> > v,vector<int> dist,int pos = 1,int k = 1){
    //cout << ans << endl;
    if(k == n){
        ans++;
        return ;
    }
    for(int i = 0; i < v[pos - 1].size(); ++i){
        if(dist[v[pos - 1][i] - 1] != 1){
            dist[v[pos - 1][i] - 1] = 1;
            solve(v,dist,v[pos - 1][i],k + 1);
            dist[v[pos - 1][i] - 1] = -1;
        }
    }
}


int main(){
    cin >> n >> m;
    //cout << n << " " << m << endl;

    vector<vector<int> > v(n);

    vector<int> dist(n,-1);


    dist[0] = 1;

    for(int i = 0; i < m; ++i){
        int a,b;
        cin >> a >> b;
        v[a - 1].push_back(b);
        v[b - 1].push_back(a);
    }
    solve(v,dist);
    cout << ans << endl;
}

Submission status: Runtime Error

Solution code:
#include <bits/stdc++.h>
using namespace std;
#define ll long int

int n,m;

int ans = 0;



void solve(vector<vector<int> > v,vector<int> dist,int pos = 1,int k = 1){
    //cout << ans << endl;
    if(k == n){
        ans++;
        return ;
    }
    for(int i = 0; i < v[pos - 1].size(); ++i){
        if(dist[v[pos - 1][i] - 1] != 1){
            dist[v[pos - 1][i] - 1] = 1;
            solve(v,dist,v[pos - 1][i],k + 1);
            dist[v[pos - 1][i] - 1] = -1;
        }
    }
}


int main(){
    cin >> n >> m;
    //cout << n << " " << m << endl;

    vector<vector<int> > v(n);

    vector<int> dist(n,-1);


    dist[0] = 1;

    for(int i = 0; i < m; ++i){
        int a,b;
        cin >> a >> b;
        v[a - 1].push_back(b);
        v[b - 1].push_back(a);
    }
    solve(v,dist);
    cout << ans << endl;

}

Submission status: Runtime Error

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

# depth-first search
def dfs(now, visited):
   if (False not in visited):
      return(1)

   ans = 0
   for i in range(1, n+1):
      if (edge[now-1][i-1] == 1  and visited[i-1] == False):
         visited[i-1] = True
         # recursive
         ans += dfs(i, visited)
         visited[i-1] = False

   return(ans)

visited = [False] * n
visited[0] = True
print(dfs(1, visited))

Submission status: Runtime Error

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

def dfs(now, visited):
   if (False not in visited):
      return(1)

   ans = 0
   for i in range(n):
      if (edge[now-1][i-1] == 1  and visited[i-1] == False):
         visited[i-1] = True
         ans += dfs(i, visited)
         visited[i-1] = False

   return(ans)

visited = [False] * n
visited[0] = True
print(dfs(1, visited))

Submission status: Runtime Error

Solution code:
import itertools

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

if n ==2:
    print(1)
    exit()

arr=[[_] for _ in range(n)]

for i in range(n):
    a,b=map(int,input().split())
    
    arr[a-1].append(b-1)
    arr[b-1].append(a-1)
for i in range(n):
    arr[i] = arr[i][1:]
#print("arr",arr)

route=list(itertools.permutations(range(1,n)))
#print("route",route) 
ans=0
for i in route:
    chk0=False
    chk=True
    if i[0] in arr[0]:
        #print(i)
        for j in range(1,n-1):
            if i[j] in arr[i[j-1]]:
                chk0=True
                #print(i[j],arr[j])
                pass
            else:
                chk=False
    if chk==True and chk0==True:
        #print(i)
        ans+=1

print(ans)

Submission status: Runtime Error

Solution code:
import itertools

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

if n ==2:
    print(1)
    exit()

arr=[[_] for _ in range(n)]

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

#print("arr",arr)

route=list(itertools.permutations(range(1,n)))
#print("route",route) 
ans=0
for i in route:
    chk0=False
    chk=True
    if i[0] in arr[0]:
        #print(i)
        for j in range(1,n-1):
            if i[j] in arr[i[j-1]]:
                chk0=True
                #print(i[j],arr[j])
                pass
            else:
                chk=False
    if chk==True and chk0==True:
        #print(i)
        ans+=1

print(ans)

Submission status: Runtime Error

Solution code:
def dfs(v):
    for i in range(len(seen)):
        if !seen[i] and i  != v:
            brea;
    else:
        res += 1

    seen[i] = True
    for nv in G[v]:
        if seen[nv]:
            continue
        def(nv)
    seen[i] = False

    


N, M = map(int, input().split())
G = dict([[i, [] 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)

seen = [False]*N
res = 0
dfs(0)
print(res)

Submission status: Runtime Error

Solution code:
import sys

sys.setrecursionlimit(10**6)

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


def dfs(graph, visited, v):
    if all(visited):
        return 1

    cnt = 0
    for u in graph[v]:
        if visited[u]:
            continue
        visited[u] = True
        cnt += dfs(graph, visited, u)
        visited[u] = False

    return cnt


visited = [False] * len(graph)
visited[0] = True
ans = dfs(graph, visited, 0)
print(ans)

Submission status: Runtime Error

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


def dfs(graph, visited, v):
    if all(visited):
        return 1

    cnt = 0
    for u in graph[v]:
        if visited[u]:
            continue
        visited[u] = True
        cnt += dfs(graph, visited, u)
        visited[u] = False

    return cnt


visited = [False] * len(graph)
visited[0] = True
ans = dfs(graph, visited, 0)
print(ans)

Submission status: Runtime Error

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

used = []
connect = []
N = 0
M = 0


def main():
    global used
    global connect
    global N
    global M
    sc = Scan()
    N, M = sc.intarr()
    a = [0] * M
    b = [0] * M
    for i in range(M):
        aa, bb = sc.intarr()
        a[i] = aa - 1
        b[i] = bb - 1
    connect = [[0] * M for i in range(M)]
    used = [0] * N
    for i in range(M):
        connect[a[i]][b[i]] = 1
        connect[b[i]][a[i]] = 1

    print(dfs(0, 1))


def dfs(now, depth):
    global used
    global connect
    if used[now] == 1:
        return 0

    if depth == N:
        return 1
    ans = 0
    used[now] = 1
    for i in range(N):
        if connect[now][i] == 1:
            ans += dfs(i, depth+1)
    used[now] = 0
    return ans


class Scan():

    def intarr(self):
        num_array = list(map(int, input().split()))
        return num_array

    def intarr_ver(self, n):
        return [int(input()) for _ in range(n)]

    def strarr(self):
        line = input()
        array = line.split(' ')
        array[-1] = array[-1].strip('\n')
        return array


def display(array):
    for a in range(len(array)):
        if len(array) - a != 1:
            print(array[a], end=' ')
        else:
            print(array[a])


def gcd(a, b):  # 最大公約数
    while b:
        a, b = b, a % b
    return a


def lcm(a, b):  # 最小公倍数
    return a * b // gcd(a, b)


main()

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10 ** 6)

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

graph = [[] for i in range(M)]
for i in range(M):
    v, e = map(int, input().split())
    graph[v - 1].append(e - 1)
    graph[e - 1].append(v - 1)

def dfs(v, seen, res):
    end = True
    for i in range(len(seen)):
        if seen[i] == False and i != v:
            end = False
    if end:
        res[0] += 1
        return
    seen[v] = True
    for i in graph[v]:
        if seen[i]:
            continue
        dfs(i, seen, res)
    seen[v] = False

res = [0]
seen = [False] * N
dfs(0, seen, res)
print(res[0])

Submission status: Runtime Error

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

graph = [[] for i in range(M)]
for i in range(M):
    v, e = map(int, input().split())
    graph[v - 1].append(e - 1)
    graph[e - 1].append(v - 1)

def dfs(v, seen, res):
    end = True
    for i in range(len(seen)):
        if seen[i] == False and i != v:
            end = False
    if end:
        res[0] += 1
        return
    seen[v] = True
    for i in graph[v]:
        if seen[i]:
            continue
        dfs(i, seen, res)
    seen[v] = False

res = [0]
seen = [False] * N
dfs(0, seen, res)
print(res[0])

Submission status: Runtime Error

Solution code:
N,M=[int(x) for x in input().rstrip().split()]
dp=[0 for i in range(N)]

for i in range(N):
    a,b=[int(x) for x in input().rstrip().split()]
    dp[a-1]+=1
    dp[b-1]+=1
dp.sort()
print(dp[0])

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(N)]
seen[0] = True
#print(seen)

dfs(graph, 0, seen)

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