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 itertools

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

per=[i for i in range(2,N+1)]
permu=[]
for i in itertools.permutations(per):
    lst=[1]
    lst.extend(i)
    permu.append(lst)
num=0
for lst in permu:
    can=True
    for i in range(N-1):
        if not([lst[i],lst[i+1]] in ab) and not([lst[i+1],lst[i]] in ab):
            can=False
            break
    if can:
        num+=1
print(num)

Submission status: Runtime Error

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

def DFS(point,TFlist):
#  print(TFlist)
  if not False in TFlist:
    return 1
  ans=0
  for i in range(n):
    if not AdjacencyMatrix[point][i]:
      continue  #AMの0なら処理せず
    if TFlist[i]:
      continue  #探索済みなら処理せず
    TFlist[i]=True #探索したのでTFlistをTrue
    ans+=DFS(i,TFlist) #再帰的にansを加算
    TFlist[i]=False #枝を戻すためにTFlistをFalse
  return ans

TFlist=[True]+[False]*(n-1)
print(DFS(0,TFlist))

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())
array = [[int(x) for x in input().split()] for y in range(m)]
modify = [[] for x in range(m + 1)]

for value1, value2 in array:
    modify[value1].append(value2)
    modify[value2].append(value1)


def solver(start, array, visited, cnt):
    if visited[start]:
        return cnt
    else:
        visited[start] = True

    for i in array[start]:
        if len(set(visited)) == 1:
            return cnt+1
        else:
            cnt = solver(i, array, list(visited), cnt)

    return cnt



start = modify[1]
res = 0
for i in start:
    visited = [False if x != 0 and x != 1 else True for x in range(m + 1)]
    res += solver(i, modify, visited, 0)

print(res)

Submission status: Runtime Error

Solution code:
N,M = map(int,input().split())
a = [0]*M
b = [0]*M
for i in range(M):
    a_, b_ = map(int,input().split())
    # 配列の添字としたいので-1
    a[i] = a_ -1
    b[i] = b_ -1

route = [0]*N  # 通過済
connect=[[0]*M for _ in range(M)]
def dfs(now, depth):
    # print("#"*depth,now, depth)
    # 通過済ならNG
    if route[now]: return 0
    # depth = Nなら達成
    if depth == N: return 1
    
    route[now] = 1
    ans = 0
    for i in range(N):
        if connect[now][i]:
            ans += dfs(i, depth+1)
    route[now] = 0
    return ans

for i in range(M):
    connect[a[i]][b[i]] = connect[b[i]][a[i]] = 1

# for xx in connect:
#     print(xx)
print(dfs(0,1))

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10**9)
N,M = map(int,input().split())
note = [[0]*M for i in range(N)]
visited = [False]*N
visited[0] = True
ans = 0
for i in range(M):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    note[a][b] = 1
    note[b][a] = 1

def dfs(p=0, depth=0):
    if depth == N-1:
        global ans
        ans += 1
        return
    for i in range(N):
        if note[p][i] == 1 and visited[i] is False:
            visited[i] = True
            dfs(i,depth+1)
            visited[i] = False

dfs()
print(ans)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10**9)
N,M = map(int,input().split())
note = [[0]*M for i in range(N)]
visited = [False]*N
ans = 0
for i in range(M):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    note[a][b] = 1
    note[b][a] = 1

def dfs(p=0, depth=0):
    if depth == N-2:
        global ans
        ans += 1
        return
    visited[p] = True
    for i in range(N):
        if note[p][i] == 1 and visited[i] is False:
            dfs(i,depth+1)

dfs()
print(ans)

Submission status: Runtime Error

Solution code:
N,M = map(int,input().split())
note = [[0]*M for i in range(N)]
visited = [False]*N
ans = 0
for i in range(M):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    note[a][b] = 1
    note[b][a] = 1

def dfs(p = 0):
    True_count = 0
    False_count = 0
    for f in visited:
        if f is True:
            True_count += 1
        elif f is False:
            False_count += 1
    if True_count == N-1 and False_count == 1:
        global ans 
        ans += 1
        return
    visited[p] = True
    for i in range(N):
        if note[p][i] == 1 and visited[i] is False:
            dfs(i)

dfs()
print(ans)

Submission status: Runtime Error

Solution code:
def dfs(i):
    if all(visited):
        global ans
        ans += 1
        return
    for j in range(N):
        if g[i][j] and not visited[j]:
            visited[j] = True
            dfs(j)
            visited[j] = False

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

ans = 0
visited = [False] * N
visited[0] = True
dfs(0)
print(ans)

Submission status: Runtime Error

Solution code:
def dfs(i):
    if all(visited):
        global ans
        ans += 1
        return
    for j in range(N):
        if g[i][j] and not visited[j]:
            visited[j] = True
            dfs(j)
            visited[j] = False
    return

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

ans = 0
visited = [False] * N
visited[0] = True
dfs(0)

Submission status: Runtime Error

Solution code:
from itertools import permutations

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

Matrix = [[False for i in range(N)] for j in range(N)]

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

arange = list(range(2,N+1))

ans = 0
for pm in permutations(arange) :
    pm = [1] + list(pm)
    for row,col in zip(pm,pm[1:]) :
        row -= 1
        col -= 1
        if not Matrix[row][col] :
            break
    else :
        ans += 1
print(ans)

Submission status: Runtime Error

Solution code:
from itertools import permutations

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

Matrix = [[False for i in range(N)] for j in range(N)] #隣接行列

for i in range(N) :
    Matrix[i][i] = True

for i in range(N) :
    row,column = map(int,input().split())
    Matrix[row-1][column-1] = True
    Matrix[column-1][row-1] = True
    
arange = range(2,N+1)
ans = 0
for pm in permutations(arange) :
    P = [1] + list(pm)
    for row,column in zip(P,P[1:]) :
        if not Matrix[row-1][column-1] :
            break
    else :
        ans += 1
print(ans)

Submission status: Runtime Error

Solution code:
from itertools import permutations as pm

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

Matrix = [[False for i in range(N)] for j in range(N)] #隣接行列

for i in range(N) :
    Matrix[i][i] = True

for i in range(N) :
    row,column = map(int,input().split())
    Matrix[row-1][column-1] = True
    Matrix[column-1][row-1] = True
    
arange = list(range(2,N+1))
ans = 0
for pm in permutations(arange) :
    P = [1] + list(pm)
    for row,column in zip(P,P[1:]) :
        if not Matrix[row-1][column-1] :
            break
    else :
        ans += 1
print(ans)

Submission status: Runtime Error

Solution code:
from itertools import permutations

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

Matrix = [[False for i in range(N)] for j in range(N)] #隣接行列

for i in range(N) :
    Matrix[i][i] = True

for i in range(N) :
    row,column = map(int,input().split())
    Matrix[row-1][column-1] = True
    Matrix[column-1][row-1] = True
    
arange = list(range(2,N+1))
ans = 0
for pm in permutations(arange) :
    P = [1] + list(pm)
    for row,column in zip(P,P[1:]) :
        if not Matrix[row-1][column-1] :
            break
    else :
        ans += 1
print(ans)

Submission status: Runtime Error

Solution code:
from itertools import permutations

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

Matrix = [[False for i in range(N)] for j in range(N)] #隣接行列

#for i in range(N) :
#    Matrix[i][i] = True

for i in range(N) :
    row,column = map(int,input().split())
    Matrix[row-1][column-1] = True
    Matrix[column-1][row-1] = True
    
arange = list(range(2,N+1))
ans = 0
for pm in permutations(arange) :
    P = [1] + list(pm)
    for row,column in zip(P,P[1:]) :
        if not Matrix[row-1][column-1] :
            break
    else :
        ans += 1
print(ans)

Submission status: Runtime Error

Solution code:
import itertools
N,M=map(int,input().split())
edge=[]
for i in range(N+1):
  edge.append([0]*(N+1))
for j in range(N):
  a,b=map(int,input().split())
  edge[a][b]=1
  edge[b][a]=1
roots=list(itertools.permutations(range(2,N+1)))
ans=0
for root in roots:
  pos=1
  for i in range(N-1):
    nxt=root[i]
    if edge[pos][nxt]==1:
      pos=nxt
    else:
      break
  else:
    ans+=1
print(ans)

Submission status: Runtime Error

Solution code:
import queue
import copy
s=list()

N,M=map(int,raw_input().split())
n=[[0 for i in range(N)] for j in range(N)]
for i in range(M):
        a,b=map(int,raw_input().split())
        n[a-1][b-1]=1
        n[b-1][a-1]=1
arrived=[0 for i in range(N)]

arrived[0]=1
def solve(s,arrived):
        narrived=copy.deepcopy(arrived)
        global n
        global N
        op=False
        ans=0
        for i in range(N):
                arrived=copy.deepcopy(narrived)
                if(s[i]==1 and arrived[i]!=1):
                        op=True
                        arrived[i]=1
                        ans+=solve(n[i],arrived)
        
        if(sum(arrived)==N and op==False):
                return 1
        elif(op==False):
                return 0
        return ans
                        
print(solve(n[0],arrived))

Submission status: Runtime Error

Solution code:
m, n = map(int, input().split())
edge = [[False for j in range(n)] for i in range(n)]
for _ in range(m):
	a, b = map(int, input().split())
	edge[a-1][b-1] = edge[b-1][a-1] = True
visited = [False for _ in range(n)]
ans = 0
def dfs(v):
	visited[v] = True
	if all(x==True for x in visited):
		global ans
		ans += 1
		return
	for i in range(0, n):
		if edge[v][i]==True and visited[i]==False:
			dfs(i)
			visited[i] = False
			return
dfs(0)
print(ans)

Submission status: Runtime Error

Solution code:
m, n = map(int, input().split())
edge = [[False for j in range(n)] for i in range(n)]
for _ in range(m):
	a, b = map(int, input().split())
	edge[a-1][b-1] = edge[b-1][a-1] = True
visited = [False for _ in range(n)]
ans = 0
def dfs(v):
	visited[v] = True
	if all(x==True for x in visited):
		global ans
		ans += 1
		return
	for i in range(0, n):
		if edge[v][i]==True and visited[i]==False:
			dfs(i)
			visited[i] = False
dfs(0)
print(ans)

Submission status: Runtime Error

Solution code:
import copy


class Line:
    def __init__(self, a, b):
        self.a = a
        self.b = b


def generate_patterns(remains, current_pattern, patterns):
    if len(remains) == 0:
        patterns.append(current_pattern)
        return
    for remain in remains:
        _current_pattern = copy.copy(current_pattern)
        _current_pattern.append(remain)
        _remains = copy.copy(remains)
        _remains.remove(remain)
        generate_patterns(_remains, _current_pattern, patterns)
    return patterns


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

m = {}
for i in range(1, N+1):
    m[i] = {}
    for j in range(1, N+1):
        m[i][j] = False

for line in lines:
    m[line.a][line.b] = True
    m[line.b][line.a] = True

remains = []
for i in range(2, N+1):
    remains.append(i)
patterns = generate_patterns(remains, [1], [])

cnt = 0
for pattern in patterns:
    countable = True
    for i in range(len(pattern)-1):
        current = pattern[i]
        next = pattern[i+1]
        if not(m[current][next]):
            countable = False
            break
    if countable:
        cnt += 1

print(cnt)

Submission status: Runtime Error

Solution code:
import copy


class Line:
    def __init__(self, a, b):
        self.a = a
        self.b = b


def generate_patterns(remains, current_pattern, patterns):
    if len(remains) == 0:
        patterns.append(current_pattern)
        return
    for remain in remains:
        _current_pattern = copy.copy(current_pattern)
        _current_pattern.append(remain)
        _remains = copy.copy(remains)
        _remains.remove(remain)
        generate_patterns(_remains, _current_pattern, patterns)
    return patterns


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

m = {}
for line in lines:
    m.setdefault(line.a, {})
    m.setdefault(line.b, {})
    m[line.a][line.b] = True
    m[line.b][line.a] = True

remains = []
for i in range(2, N+1):
    remains.append(i)
patterns = generate_patterns(remains, [1], [])

cnt = 0
for pattern in patterns:
    countable = True
    for i in range(len(pattern)-1):
        current = pattern[i]
        next = pattern[i+1]
        if next not in m[current]:
            countable = False
            break
    if countable:
        cnt += 1

print(cnt)

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
A = []
B = []

for i in xrange(M):
    a, b = map(int, input().split())
    A.append(a)
    B.append(b)
for i in xrange(M):
    A.append(B[i])
    B.append(A[i])

result = []
stack = []

def path(start, visited):
    if len(visited) >= N:
        if visited not in result:
            result.append(visited[:])
        exit
    stack.append(start)
    if len(stack) > 0:
        nextpoint = stack.pop()
        if nextpoint not in visited:
            visited.append(nextpoint)
            for i in xrange(2*M):
                if A[i] == start:
                    path(B[i], visited)
            visited.pop()

path(1, [])
print(len(result))

Submission status: Runtime Error

Solution code:
def lensetlist(A):
    B = []
    for i in A:
        if i not in B:
            B.append(i)
    return len(B)

N, M = map(int, input().split())
A = []
B = []

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

result = []
stack = []
ans = 0
count = 0
def path(start, visited):
    count += 1
    if count > 10000:
        break
    if len(visited) == N:
        result.append(visited[:])
        exit
    stack.append(start)
    while len(stack) > 0:
        nextpoint = stack.pop()
        if nextpoint in visited:
            continue
        visited.append(nextpoint)
        for i in range(2*M):
            if A[i] == start:
                path(B[i], visited)
        visited.pop()

path(1, [])
print(lensetlist(result))

Submission status: Runtime Error

Solution code:
N,M=map(int,input().split())
A=[ list(input()) for i in range(N)]
B=[ list(input()) for i in range(M)]
ans='Yes'
for i in range(N-M+1):
    for j in range(N-M+1):
        
        for k in range(i,i+M):
            for l in range(j,j+M):
                if A[k][l]!=B[k-i][l-j]:
                    ans='No'
print(ans)

Submission status: Runtime Error

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

Visited = [False for i in range(N)]
Visited[0] = True
ans = 0
def DFS(i):
    allvisited = True
    for j in range(N):
        if Visited[j] == False:
            allvisited = False
    if allvisited:
        return 1
    else:
        ret = 0
        for node in Edge[i]:
            if Visited[node] == False:
                Visited[node] = True
                ret += DFS(node)
                Visited[node] = False
        return ret

print(DFS(0))

Submission status: Runtime Error

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

graph = [ [False] * 8 for _ in range(8) ]
visited = [False] * n

def dfs(a, N, visited):
    finish = True
    for i in range(N):
        if not visited[i]:
            finish = False
    if finish:
        return 1
    ans = 0
    for i in range(N):
        if not graph[a][i] or visited[i]:
            continue
        visited[i] = True
        ans += dfs(i,N,visited)
        visited[i] = False

for i in range(m):
    graph[ab[i][0]-1][ab[i][1]-1], graph[ab[i][1]-1][ab[i][0]-1] = True, True

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

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
E = [[0 for i in range(N)] for j in range(N)] #頂点のつながり
for i in range(M):
    a, b = map(int, input().split())
    E[a-1][b-1] = 1
    E[b-1][a-1] = 1

V = [ 0 for i in range(N)] #訪問済みの頂点が1
V[0] = 1 #頂点1は訪問済み

def DPS(now, V):
    res = 0 #全て訪問できた回数
    if 0 not in V:
        return 1
    for i in range(M):
        if (E[now][i] == 1) and (V[i] == 0): #現在の頂点と隣接してかつ未訪問の頂点
            V[i] = 1
            res = res + DPS(i, V)
            V[i] = 0
    return res

print(DPS(0, V))

Submission status: Runtime Error

Solution code:
import itertools
na = lambda: list(map(int, input().split()))

n, m = na()
t = [[0] * 10 for _ in range(10)]
for _ in range(m):
    a, b = na()
    a -= 1
    b -= 1
    t[a][b] = t[b][a] = 1

ans = 0
for l in itertools.permutations(range(m)):
    if l[0]: continue
    flag = 1
    for i in range(1, n):
        if t[l[i]][l[i-1]] == 0:
            flag = 0
            break
    if flag:
        ans += 1

print(ans)

Submission status: Runtime Error

Solution code:
import itertools
na = lambda: list(map(int, input().split()))

n, m = na()
t = [[0] * 10 for _ in range(10)]
for _ in range(m):
    a, b = na()
    a -= 1
    b -= 1
    t[a][b] = t[b][a] = 1

ans = 0
for l in itertools.permutations(range(m)):
    if l[0]: continue
    flag = 1
    for i in range(1, n):
        if t[l[i]][l[i-1]] == 0:
            flag = 0
    if flag:
        ans += 1

print(ans)

Submission status: Runtime Error

Solution code:
import copy
def explore(key, flags):
    flags = copy.copy(flags)
    if flags[key-1]:
        return 0
    flags[key-1] = True
    if False not in flags:
        return 1
    elif key in graph:
        value = graph[key]
        ans = 0
        for i in value:
            ans += explore(i, flags)
        return ans
    else:
        return 0

n, m = map(int, input().split())
graph = {}
for i in range(m):
    a, b = map(int, input().split())
    if a in graph:
        graph[a].append(b)
    else:
        graph[a] = [b]
    if b in graph:
        graph[b].append(a)
    else:
        graph[b] = [a]

flags = [False for i in range(m)]
ans = explore(1, flags)
print(ans)

Submission status: Runtime Error

Solution code:
def search(node):
    global ans

    if sum(is_visit) == n:
        ans += 1

    for i in range(n):
        if is_neighbor[node][i]:
            if not is_visit[i]:
                is_visit[i] = True
                search(i)
                is_visit[i] = False

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

is_neighbor = [[False for j in range(n)] for i in range(n)]
for i in range(n):
    a, b = map(int, input().split())
    is_neighbor[a - 1][b - 1] = True
    is_neighbor[b - 1][a - 1] = True

is_visit = [False for _ in range(n)]

ans = 0

is_visit[0] = True
search(0)
print(ans)

Submission status: Runtime Error

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

for a, b in G:
    edges[a - 1].add((b - 1, 1))
    edges[b - 1].add((a - 1, 1))

def dfs(start, edges, path):
    path.append(start)
    if len(path) == n:
        path.pop()
        return 1
    ans = 0
    for u in edges[start]:
        if u in path:
            continue
        ans += dfs(u, path)
    path.pop()
    return ans    

print(dfs(0, []))

Submission status: Runtime Error

Solution code:
from itertools import permutations

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

for i in range(n) :
    _a, _b = map(int, input().split())
    # paths.add((_a, _b))
    # paths.add((_b, _a))
    
# print(sum(all(s in paths for s in zip((1,) + p, p)) for p in permutations(range(2, n + 1))))

Submission status: Runtime Error

Solution code:
from itertools import permutations

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

for i in range(n) :
    _a, _b = map(int, input().split())
    paths.add((_a, _b))
    paths.add((_b, _a))
    
# print(sum(all(s in paths for s in zip((1,) + p, p)) for p in permutations(range(2, n + 1))))

Submission status: Runtime Error

Solution code:
from itertools import permutations

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

for i in range(n) :
    _a, _b = map(int, input().split())
    paths.add((_a, _b))
    paths.add((_b, _a))
    
print(sum(all(s in paths for s in zip((1,) + p, p)) for p in permutations(range(2, n + 1))))

Submission status: Runtime Error

Solution code:
from itertools import permutations

n, m = map(int, input().split())
# a, b = [], []
paths = set()

for i in range(n) :
    _a, _b = map(int, input().split())
    paths.add((_a, _b))
    paths.add((_b, _a))
    
print(sum(all((s, t) in paths for s, t in zip((1,) + p, p)) for p in permutations(range(2, n + 1))))

Submission status: Runtime Error

Solution code:
from itertools import permutations

n, m = map(int, input().split())
a, b = [], []

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

# create set
paths = set()
for i in range(m) :
    paths.add((a[i], b[i]))
    paths.add((b[i], a[i]))
    
print(sum(all((s, t) in paths for s, t in zip((1,) + p, p)) for p in permutations(range(2, n + 1))))

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10000)
N,M=list(map(int,input().split()))
graph=[[False]*N for i in range(N)]
for i in range(N):
    a,b=list(map(int, input().split()))
    graph[a-1][b-1]=True
    graph[b-1][a-1]=True
visited=[False]*N
def dfs(v,visited):
    if all(visited):
        return 1
    ret=0
    for i in range(N):
        if not graph[v][i]:
            continue
        if visited[i]:
            continue
        visited[i]=True
        ret+=dfs(i,visited)
        visited[i]=False
    return ret
visited[0]=True
print(dfs(0,visited))

Submission status: Runtime Error

Solution code:
from collections import defaultdict
import sys
sys.setrecursionlimit(10000)
N,M=list(map(int,input().split()))
links=defaultdict(list)
for i in range(N):
    a,b=list(map(int, input().split()))
    links[a].append(b)
    links[b].append(a)
ct=0
visited=[False]*N
def DFS(idx):
    global visited
    if all(visited):
        global ct
        ct+=1
        return
    for i in links[idx]:
        if visited[i-1]:
            continue
        visited[i-1]=True
        DFS(i)
        visited[i-1]=False
visited[0]=True
DFS(1)
print(ct)

Submission status: Runtime Error

Solution code:
from collections import defaultdict
import sys
sys.setrecursionlimit(10000)
N,M=list(map(int,input().split()))
links=defaultdict(list)
for i in range(N):
    a,b=list(map(int, input().split()))
    links[a].append(b)
    links[b].append(a)
ct=0
def DFS(idx,visited):
    visited.add(idx)
    for i in links[idx]:
        if i in visited:
            continue
        visi=set(visited)
        DFS(i,visi)
        if len(visi)==N:
            global ct
            ct+=1
DFS(1,set())
print(ct)

Submission status: Runtime Error

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

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

b = [[0 for i in range(n)] for j in range(n)]
for i in a:
    b[i[0]][i[1]] = 1
    b[i[1]][i[0]] = 1

c = [i+1 for i in range(m-1)]
ans = 0
for i in itertools.permutations(c,m-1):
    j = [0]
    j += i
    count = 0
    for i in range(m-1):
        if b[j[i]][j[i+1]] == 1:
            count += 1
            if count == m-1:
                ans += 1
                count = 0
        else:
            break
print(ans)

Submission status: Runtime Error

Solution code:
import sys

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

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

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

adj_array = [[] for x in range(m + 1)]
res_array = [True] + [False for x in range(n)]
for item in array:
    adj_array[item[0]].append(item[1])
    adj_array[item[1]].append(item[0])


def dfs(n, res_array, res):
    res_array[n] = True
    if False not in res_array:
        return res+1
    else:
        for next in adj_array[n]:
            if not res_array[next]:
                res = dfs(next, list(res_array), res)
    return res


res = 0
res_array[1] = True
print(dfs(1, res_array, res))

Submission status: Runtime Error

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

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

adj_array = [[] for x in range(m + 1)]
res_array = [True] + [False for x in range(n)]
for item in array:
    adj_array[item[0]].append(item[1])
    adj_array[item[1]].append(item[0])


def dfs(n, res_array, res):
    res_array[n] = True
    if False not in res_array:
        return res+1
    else:
        for next in adj_array[n]:
            if not res_array[next]:
                res = dfs(next, list(res_array), res)
    return res


res = 0
res_array[1] = True
print(dfs(1, res_array, res))

Submission status: Runtime Error

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

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

adj_array = [[] for x in range(m + 1)]
res_array = [True] + [False for x in range(m)]
for item in array:
    adj_array[item[0]].append(item[1])
    adj_array[item[1]].append(item[0])


def dfs(n, res_array, res):
    res_array[n] = True
    if False not in res_array:
        return res+1
    else:
        for next in adj_array[n]:
            if not res_array[next]:
                res = dfs(next, list(res_array), res)
    return res


res = 0
res_array[1] = True
print(dfs(1, res_array, res))

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-

# AtCoder Beginner Contest
# Problem C


# See:
# https://atcoder.jp/img/abc054/editorial.pdf
def dfs(v):
    all_visited = True

    if False in visited:
        all_visited = False

    if all_visited:
        return 1

    count = 0

    for i in range(n):
        if graph[v][i] == 0:
            continue

        if visited[i]:
            continue

        visited[i] = True
        count += dfs(i)
        visited[i] = False
    return count


if __name__ == '__main__':
    n, m = list(map(int, input().split()))
    graph = [[0 for __ in range(m)] for _ in range(m)]

    for i in range(m):
        a, b = list(map(lambda x: int(x) - 1, input().split()))
        graph[a][b] = 1
        graph[b][a] = 1

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

    print(dfs(0))

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-

# AtCoder Beginner Contest
# Problem C


def dfs(pos, mask):
    if pos == n:
        if len(set(p)) == n:
            pass_count = 1

            for i in range(n - 1):
                if graph[p[i]][p[i + 1]] == 1:
                    pass_count += 1

            if pass_count == n:
                global count
                count += 1
        return

    # See:
    # https://www.youtube.com/watch?v=UFMvexj1hY4
    for i in range(n):
        if mask and (1 << i):  # i in mask.
            p[pos] = i
            dfs(pos + 1, mask ^ (1 << i))  # remove i from mask.


if __name__ == '__main__':
    n, m = list(map(int, input().split()))
    ab = [list(map(lambda x: int(x) - 1, input().split())) for _ in range(m)]
    graph = [[0 for __ in range(m)] for _ in range(m)]
    p = [0] * n
    count = 0

    for a, b in ab:
        graph[a][b] = 1

        if a != 0:
            graph[b][a] = 1

    dfs(0, (1 << n) - 1)  # permutation [0, n - 1]

    print(count)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-

# AtCoder Beginner Contest
# Problem C


def dfs(i: int):
    if visited[i]:
        return

    visited[i] = True

    for k in range(n):
        if graph[i][k] == 1:
            dfs(k)


if __name__ == '__main__':
    n, m = list(map(int, input().split()))
    ab = [list(map(lambda x: int(x) - 1, input().split())) for _ in range(m)]
    graph = [[0 for __ in range(m)] for _ in range(m)]

    for a, b in ab:
        graph[a][b] = 1
        graph[b][a] = 1

    count = 0

    for a, b in ab:
        visited = [False for _ in range(n)]

        if a == 0:
            dfs(a)

            if False not in visited:
                count += 1

    print(count)

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())
l = []
combo = []
for i in range(max(n, m) + 1):
  l.append([])
def dfs(path, now):
  if len(set(path)) == n and not path in combo:
    combo.append(path)
    return

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

  return

if m == 0:
  print(0)
else:

  for i in range(m):
    f, t = map(int, input().split())
    if not t in l[f]:
      l[f].append(t)
    
    if not f in l[t]:
      l[t].append(f)

  dfs([1], 1)
  print(len(combo))n, m = map(int, input().split())
l = []
combo = []
for i in range(max(n, m) + 1):
  l.append([])
def dfs(path, now):
  if len(set(path)) == n and not path in combo:
    combo.append(path)
    return

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

  return

if m == 0:
  print(0)
else:

  for i in range(m):
    f, t = map(int, input().split())
    if not t in l[f]:
      l[f].append(t)
    
    if not f in l[t]:
      l[t].append(f)

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