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: Accepted

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

graphs = list([list(map(int, input().split())) for x in range(m)])

def search_indecies(num, remainGraph, path):
    indecies = []
    for i, currentNode in enumerate(remainGraph):
        if currentNode[0] == num or currentNode[1] == num:
            others = get_other_num(currentNode, num)
            if all([x[0] != others and x[1] != others for x in path]):
                indecies.append(i)
    return indecies



def search_iterative(currentGraph, currentNodeNum, currentIndex, path):
    prev = currentNodeNum

    currentNode = currentGraph.pop(currentIndex)
    path.append(currentNode)
    if len(path) == n - 1:
        return [path]
    nextNum = get_other_num(currentNode, prev)

    nextCandidateIndecies = search_indecies(nextNum, currentGraph, path)

    pathList = []
    for nextIndex in nextCandidateIndecies:
        c = search_iterative(currentGraph[:], nextNum, nextIndex, path[:])
        pathList += c

    return pathList

def get_other_num(currentNode, prev):
    return currentNode[0] if currentNode[1] == prev else currentNode[1]


startIndecies = search_indecies(1, graphs, [])

resuts = []
for startIndex in startIndecies:
    path = []
    resuts += search_iterative(graphs[:], 1, startIndex, path)

allPaths = [r for r in resuts if len(r) > 0]
print(len(allPaths))

Submission status: Accepted

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

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

def dfs(v, seen):
    seen[v] = True
    if all(seen):
        return 1

    ans = 0
    for nextCandidate in graphs[v]:
        if seen[nextCandidate]:
            continue
        ret = dfs(nextCandidate, seen[:])
        ans += ret

    return ans


firstSeen = [False]*n

total = dfs(0, firstSeen)

print(total)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
ab=[set(map(int,input().split())) for _ in range(m)]
def dfs(v,visited):
  if v in visited:
    return 0
  if len(visited|{v})==n:
    return 1
  return sum(dfs(i,visited|{v}) for i in range(1,n+1) if {i,v} in ab)
print(dfs(1,set()))

Submission status: Accepted

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

# N!通りの順列
# lはタプルなのでlist()でリスト化して使うべし
import itertools
t = [i for i in range(N)]
l = list(itertools.permutations(t))
# 以下でリスト化
for i in range(len(l)):
    l[i] = list(l[i])

ans = 0
for i in range(len(l)):
    for j in range(N-1):
        if not l[i][j+1] in line[l[i][j]]:
            break
    else:
        if l[i][0] == 0:
            ans += 1

print(ans)

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
vertex = [[0 for j in range(N+1)] for i in range(N+1)]

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

from itertools import permutations

ans = 0
for v in permutations([i+2 for i in range(N-1)], N-1):
    v = [1] + list(v)
    canmake = 1
    for j in range(N-1):
        if not vertex[v[j]][v[j+1]]:
            canmake = 0
            break
    if canmake:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
vertex = [[0 for j in range(N+1)] for i in range(N+1)]
AB = [list(map(int,input().split())) for _ in range(M)]

for i in range(M):
    a,b = AB[i]
    vertex[a][b] = 1
    vertex[b][a] = 1

from itertools import permutations

ans = 0
for v in permutations([i+2 for i in range(N-1)], N-1):
    v = [1] + list(v)
    canmake = 1
    for j in range(N-1):
        if not vertex[v[j]][v[j+1]]:
            canmake = 0
            break
    if canmake:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
## coding: UTF-8
from itertools import permutations

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

graph = []
for i in range(M):
    graph.append(list(map(int, input().split())))
#print(graph)

point = [i+1 for i in range(1,N)]
root = list(permutations(point, N-1))
#print(root)

counter = 0
for i in range(len(root)):
    pairs = []
    pairs.append([1, root[i][0]])
    #print(root[i])
    for j in range(N-2):
        pairs.append([root[i][j], root[i][j+1]])
    #print('i:{},root[i]:{},pairs:{}'.format(i, root[i], pairs))
    status = True
    for k in range(len(pairs)):
        tester = sorted(pairs[k])
        #print('pairs[k]:{}, tester:{}, in graph?:{}'.format(pairs[k], tester, (tester in graph)))
        if(not(tester in graph)):
            status = False
    #print('status:{}'.format(status))
    if(status):
        counter += 1
print(counter)

'''
counter = 0
for i in range(len(root)):
    print('i:{},root[i]:{}'.format(i, root[i]))
    spot = 1
    for j in range(N-1):
        #勧めるなら進む
        n = root[i][j]
        print('spot:{}, n:{}'.format(spot, n))
        if(spot < n):
            if([spot, n] in graph):
                spot = n
            else:
                continue
        elif(spot > n):
            if([n, spot] in graph):
                spot = n
            else:
                continue
        else:
            continue
'''

Submission status: Accepted

Solution code:
def bitDP():
    dp = [[0] * N for _ in range(1 << N)]
    dp[1][0] = 1
    for i in range(1 << N):
        for v in range(N):
            if  (i >> v) & 0:
                continue
            j = i ^ (1 << v)
            for u in range(N):
                if (j >> u) & 1 and v in E[u]:
                    dp[i][v] += dp[j][u]
    res = sum(dp[-1][u] for u in range(1, N))
    return res

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

print(bitDP())

Submission status: Accepted

Solution code:
from itertools import permutations

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

ans = 0
for p in permutations([i for i in range(1, N)]):
    i = 0
    for j in p:
        if j not in E[i]:
            break
        i = j
    else:
        ans += 1
print(ans)

Submission status: Accepted

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

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

memo = {}
All_used = (1 << N) - 1


def dfs(v, used):
  if used == All_used:
    return 1
  key = (v, used)
  if key in memo:
    return memo[key]
  ans = 0
  for i in g[v]:
    if used & (1 << i):
      continue
    used ^= (1 << i)
    ans += dfs(i, used)
    used ^= (1 << i)
  memo[key] = ans
  return ans

print(dfs(0, 1))

Submission status: Accepted

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

# 繋がっている点を記載する二重リストを準備する。
adj_matrix = [[0]* N for _ in range(N)]
for i in range(M):
    a, b = map(int, input().split())
    adj_matrix[a-1][b-1] = 1
    adj_matrix[b-1][a-1] = 1

# 点を通ったかを記録するリスト
used = [False] * N
used[0] = True


# 深さ探索を行うため再帰関数を定義する。
# 現在いる点をvとしての再帰
def dfs(v, used):
    # 再帰を繰り返してusedの中身が全てTrueになったときのみ1を返すようにする。
    if not False in used:
        return 1

    ans = 0
    for i in range(N):
        if adj_matrix[v][i] != 1:
            continue
        if used[i]:
            continue
        used[i] = True
        ans += dfs(i, used)
        used[i] = False
    # usedの中にFalseがあるとき用のreturn(再帰で用いられるようのreturn)
    return ans

print(dfs(0, used))

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
edge = [[] for _ in range(N)]
for i in range(M):
    a, b = map(int, input().split())
    edge[a-1].append(b-1)
    edge[b-1].append(a-1)
def dfs(start,route):
    route.append(start)
    if len(route) == N:
        route.remove(start)
        return 1
    res = 0
    for i in edge[start]:
        if i not in route:
            res += dfs(i,route)
    route.remove(start)
    return res
print(dfs(0,[]))

Submission status: Accepted

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

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

for i in itertools.permutations(range(n), n):
    if i[0] == 0:
        for j in range(n):
            if j == n - 1:
                ans += 1
                break
            if not path[i[j]][i[j + 1]]:
                break
print(ans)

Submission status: Accepted

Solution code:
import itertools
N,M=map(int,input().split())
ab=list(list(map(int,input().split())) for _ in range(M))
l=list(l for l in range(1,N+1))
numlist=list(itertools.permutations(l))
ans=0
for I in numlist:
    if I[0]==1 and all(sorted([I[j],I[j+1]]) in ab for j in range(N-1)):
        ans+=1
print(ans)

Submission status: Accepted

Solution code:
n,m=[int(i) for i in input().split()]
es=set()
for _ in range(m):
    u,v=map(int,input().split())
    u,v=u-1,v-1
    es|={(u,v),(v,u)}

p=[[0]]
x=0
while p:  
  p1=p.pop()
  if len(p1)==n:
    x+=1
  else:
    for l0,l1 in es:
      if l0==p1[len(p1)-1] and l1 not in p1:
          p.append(p1+[l1])

print(x)

Submission status: Accepted

Solution code:
import itertools
N,M=map(int,input().split())
path=[list(map(int,input().split())) for _ in range(M)]
seq=list(range(2,N+1))
#print(path)
l=list(itertools.permutations(seq))
#print(l)
buf=[]
cnt=0
for i in range(len(l)):
    buf=list(l[i])
    piv1=1
    #print(buf,len(buf))
    for j in range(len(buf)):
        flag = 0
        piv2=buf[j]
        #print(i,piv1,piv2)
        for k in range(M):
            mi=min(piv1,piv2)
            ma=max(piv1,piv2)
            if (path[k][0]==mi)and(path[k][1]==ma):
                flag=1
        #input()
        if flag==0:
            break
        else:
            piv1=piv2
    if flag==1:
        cnt=cnt+1
print(cnt)

Submission status: Accepted

Solution code:
def resolve():
    N, M = list(map(int, input().split()))
    A = [list(map(int, input().split())) for i in range(M)]
    cnt = 0
    import itertools
    L = list(itertools.permutations(range(2, N+1)))
    for route in L:
        src = 1
        for point in route:
            dst = point
            if not ([src, dst] in A or [dst, src] in A):
                break
            src = dst
        else:
            cnt += 1
    print(cnt)

if '__main__' == __name__:
    resolve()

Submission status: Accepted

Solution code:

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

# 無向グラフ
d = [[False] * N
    for _ in range(N)]

for _ in range(M):
    A, B = map(int, input().split())
    d[A - 1][B - 1] = True
    d[B - 1][A - 1] = True

# 訪問したかどうか:スタート頂点の1以外訪問していないとする
visited = [False for _ in range(N)]
visited[0] = True

#Depth first serch
def dfs(v, N, visited):
    if all(visited): #すべて訪問済みなら1を返す
        return 1

    ret = 0
    for i in range(N):
        # 経路存在と訪問済み確認
        if not d[v][i] or visited[i]: #経路がない or 訪問済みなら次
            continue

        visited[i] = True
        
        #再帰
        ret += dfs(i, N, visited)
        
        # 再帰後に元に戻す
        visited[i] = False

    return ret

ans = dfs(0, N, visited)

print(ans)

Submission status: Accepted

Solution code:
import itertools

n,m = map(int,input().split())
path_list = [list(map(int,input().split())) for _ in range(m)]

path_dict = {}
count = 0

for path in path_list:
    if path[0] in path_dict:
        path_dict[path[0]].append(path[1])
    else:
        path_dict[path[0]] = [path[1]]
    if path[1] in path_dict:
        path_dict[path[1]].append(path[0])
    else:
        path_dict[path[1]] = [path[0]]

order_list = list(range(2,n+1))
order_list = list(itertools.permutations(order_list))
# print(list(itertools.permutations(order_list)))
for order in order_list:
    order = list(order)
    order.insert(0,1)
    for i,num in enumerate(order):
        if i >= 1:
            if num not in target_list:
                break
        if i == len(order)-1:
            count += 1
        target_list = path_dict[num]

print(count)

Submission status: Accepted

Solution code:
from itertools import permutations
N, M = list(map(int, input().split(' ')))
ADJ_MAT = [[0 for _ in range(N)] for _ in range(N)]
for _ in range(M):
    a, b = list(map(int, input().split(' ')))
    ADJ_MAT[a - 1][b - 1] = 1
    ADJ_MAT[b - 1][a - 1] = 1
answer = 0
for node_pattern in permutations(range(1, N)):
    # first node is fixed
    node_pattern = [0] + list(node_pattern)
    exists_path = True
    for i in range(N - 1):
        node_from = node_pattern[i]
        node_to = node_pattern[i + 1]
        if ADJ_MAT[node_from][node_to] == 0:
            exists_path = False
            break
    if exists_path:
        answer += 1
print(answer)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())  #頂点, 辺
g = [[] for _ in range(N)]  #iはjと繋がっている
for _ in range(M):
    a, b = map(int, input().split())
    g[a-1].append(b-1)
    g[b-1].append(a-1)

#1度通った頂点をTrueにする
is_checked = [False] * N

def dfs(i):
    cnt = 0
    is_checked[i] = True
    if not(False in is_checked):
        return 1
    else:
        for j in g[i]:
            if not(is_checked[j]):
                cnt += dfs(j)
                is_checked[j] = False
        return cnt
            
ans = dfs(0)
print(ans)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())  #頂点, 辺
g = [[] for _ in range(N)]  #iはjと繋がっている
for _ in range(M):
    a, b = map(int, input().split())
    g[a-1].append(b-1)
    g[b-1].append(a-1)

#1度通った頂点をTrueにする
is_checked = [False] * N

import sys
sys.setrecursionlimit(10 ** 8)
def dfs(i):
    cnt = 0
    is_checked[i] = True
    if not(False in is_checked):
        return 1
    else:
        for j in g[i]:
            if not(is_checked[j]):
                cnt += dfs(j)
                is_checked[j] = False
        return cnt
            
ans = dfs(0)
print(ans)

Submission status: Accepted

Solution code:
import itertools
nums = [int(e) for e in input().split()]
pairs = []
count = 0
for i in range(nums[1]):
    s = [int(t) for t in input().split()]
    pairs.append(s)
lis = [i for i in range(1,nums[0]+1)]
permutatin_lis = itertools.permutations(lis)
for one in permutatin_lis:
    if(one[0] != 1):
        continue
    else:
        for i in range(nums[0]-1):
            checker = [one[i],one[i+1]]
            checker.sort()
            if checker in pairs:
                pass
            else:
                break
        else:
            count += 1
print(count)

Submission status: Accepted

Solution code:
import itertools

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

path = [[False]*N for i in range(N)]
ans = 0

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

for i in list(itertools.permutations(range(N),N)):
    if i[0] == 0:
        for j in range(N):
            if j == N-1:
                ans += 1
                break
            if not path[i[j]][i[j+1]]:
                break
print(ans)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
G = [list(map(int, input().split())) for _ in range(M)]
edges = [[] for _ in range(N)]
for a, b in G:
    edges[a - 1].append(b - 1)
    edges[b - 1].append(a - 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, edges, path)
    path.pop()
    return ans

print(dfs(0, edges, []))

Submission status: Accepted

Solution code:
import itertools

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

# 隣接行列
for i in range(M):
    a, b = map(int, input().split())
    # 無向グラフなので両方1にする
    adj_mtrx[a-1][b-1] = 1
    adj_mtrx[b-1][a-1] = 1


cnt = 0

# itertools.permutations(list) リストから順列を生成、列挙
# 頂点を結ぶ結び方を全て列挙する（順列で列挙できる）
# 列挙したした中で頂点1から始まっているかつパスとして繋がっているものをカウントする
for each in itertools.permutations(range(N)):

    # 1からスタートしない場合break
    if each[0]!=0:
        break

    factor=1
    for i in range(N-1):
        # 隣接行列で繋がっていれば1、繋がっていなければ0なので
        # 一つでも繋がっていなければ、0になる
        factor *= adj_mtrx[each[i]][each[i+1]]
    cnt += factor

print(cnt)

Submission status: Accepted

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

def solve(s,p):
  global res
  dp=format(s,'08b')[::-1]
  if s == (1<<n)-1 :
    res += 1
    return res
  for u in graph[p-1]:
    if dp[u-1] == '1':
      continue
    res = solve(s|(1<<(u-1)),u)
  return res

print(solve(1,1))

Submission status: Accepted

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

t=[i for i in range(N-1)]
premu=list(itertools.permutations(t))

cnt=0
for elem in premu:
    eb=1
    for e in elem:
        ec=e+2
        flag=False
        for ab in AB:
            if (ec in ab) and (eb in ab):
                flag=True    
        if flag:
            eb=ec
        else:
            break
    if flag:
        cnt+=1

print(cnt)

Submission status: Accepted

Solution code:
import itertools

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

lis = [i for i in range(1, N+1)]
T = itertools.permutations(lis)

ans = 0

for t in T:
    if t[0] == 1:
        for i in range(N-1):
            A = [list(t)[i], list(t)[i+1]]
            B = [list(t)[i+1], list(t)[i]]
            if not (A in L or B in L):
                break
        else:
            ans += 1
print(ans)

Submission status: Accepted

Solution code:
import itertools

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

ans = 0
for li in itertools.permutations(range(n), n):
    if li[0] == 0:
        for i in range(n-1):
            if not li[i + 1] in relation[li[i]]:
                break
        else:
            ans += 1

print(ans)

Submission status: Accepted

Solution code:
from itertools import permutations

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


counter = 0
for perm in permutations(range(2, N+1)):
    if lines[1][perm[0]]:
        if all(lines[perm[i]][perm[i+1]] for i in range(N-2)):
            counter += 1

print(counter)

Submission status: Accepted

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

from itertools import permutations
perm=permutations(range(1,n))
ans=0
for p in perm:
    newp=[0]+list(p)
    flg=True
    for i in range(n-1):
        if newp[i+1] not in es[newp[i]]:
            flg=False
            break
    if flg: ans+=1
print(ans)

Submission status: Accepted

Solution code:
import itertools

N, M = map(int, input().split())
c = [[False] * N for i in range(N)]
for i in range(M):
	a, b = map(int, input().split())
	c[a - 1][b - 1] = True
	c[b - 1][a - 1] = True
ans, d = 0, [i for i in range(N)]
for i in itertools.permutations(d[1:]):
	e, f = True, list(i)
	f.insert(0, d[0])
	for j in range(N - 1):
		if not c[f[j]][f[j + 1]]:
			e = False
			break
	if e:
		ans += 1
print(ans)

Submission status: Accepted

Solution code:
q=[]
qq=[]
def dfs(j,q,count,n,qq):
    if len(qq)==n:
        count+=1
        return count   
    for j2 in q[j]:
        if not j2 in qq:
            qq.append(j2)
            count=dfs(j2,q,count,n,qq)
            qq.pop()
    return count

n,m=map(int,input().split())
q=[[]*2 for i in range(n)]
for i in range(m):
    ai,bi=list(map(int,input().split()))
    if not q[bi-1] in q[ai-1]:
        q[ai-1].append(bi-1)    
        q[bi-1].append(ai-1)    

count=0
j=0
qq=[j]
count=dfs(j,q,count,n,qq)
print(count)

Submission status: Accepted

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

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

memo = {}
All_used = (1 << N) - 1

def dfs(v, used):
  if used == All_used:
    return 1
  key = (v, used)
  if key in memo:
    return memo[key]
  ans = 0
  for u in g[v]:
    if (used >> u) & 1 ==1:
      continue
    used ^= (1 << u)
    ans += dfs(u, used)
    used ^= (1 << u)
  memo[key] = ans
  return ans

print(dfs(0, 1))

Submission status: Accepted

Solution code:
q=[]
qq=[]
def dfs(j,q,count,n,qq):
    if len(qq)==n:
        count+=1
        return count    
    for j2 in q[j]:
        if not j2 in qq:
            qq.append(j2)
            count=dfs(j2,q,count,n,qq)
            qq.pop()
    return count

n,m=map(int,input().split())
q=[[]*2 for i in range(n)]
for i in range(m):
    ai,bi=list(map(int,input().split()))
    if not q[bi-1] in q[ai-1]:
        q[ai-1].append(bi-1)    
    if not q[ai-1] in q[bi-1]:
        q[bi-1].append(ai-1)    

count=0
j=0
qq=[j]
count=dfs(j,q,count,n,qq)
print(count)

Submission status: Accepted

Solution code:
q=[]
qq=[]
def dfs(j,q,icnt,count,n,qq):
    if len(qq)==n:
        count+=1
#        print("1",n,j,icnt,count,q[j],qq)
        return count
    icnt+=1
    
    for j2 in q[j]:
        if not j2 in qq:
            qq.append(j2)
#            print("2",n,j,icnt,count,q[j],qq)
            count=dfs(j2,q,icnt,count,n,qq)
            qq.pop()
#        print("3",n,j,icnt,count,q[j],qq)
    return count

n,m=map(int,input().split())
ab=[[0]*2 for i in range(m)]
for i in range(m):
    ab[i]=list(map(int,input().split()))

#n=3
#m=3
#ab=[[1,2],[1,3],[2,3]]

#n=7
#m=7
#ab=[[1,3],[2,7],[3,4],[4,5],[4,6],[5,6],[6,7]]

q=[[]*2 for i in range(n)]
for i in range(m):
    if not q[ab[i][1]-1] in q[ab[i][0]-1]:
        q[ab[i][0]-1].append(ab[i][1]-1)    
    if not q[ab[i][0]-1] in q[ab[i][1]-1]:
        q[ab[i][1]-1].append(ab[i][0]-1)    
#print(q)    

count=0
j=0
qq=[j]
icnt=1
count=dfs(j,q,icnt,count,n,qq)
print(count)

Submission status: Accepted

Solution code:
import sys
import heapq, math
from itertools import zip_longest, permutations, combinations, combinations_with_replacement
from itertools import accumulate, dropwhile, takewhile, groupby
from functools import lru_cache
from copy import deepcopy

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


def search(idx, S):
    if S == (1 << N) - 1:
        return 1

    cnt = 0
    for n in G[idx]:
        if ((S >> n) & 1) == 1:
            continue

        cnt += search(n, S | (1 << n))

    return cnt

print(search(0, 1))

Submission status: Accepted

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

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

def dfs(v, used):
    if not False in used:
        return 1

    ans = 0
    for i in range(N):
        if not adj_matrix[v][i]:
            continue
        if used[i]:
            continue
        used[i] = True
        ans += dfs(i, used)
        used[i] = False        
    return ans

used = [False] * N
used[0] = True
print(dfs(0, used))

Submission status: Accepted

Solution code:
def dfs(now, depth):
    if used[now]:
        return 0
    if depth == N:
        return 1

    used[now] = 1
    ans = 0

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

    used[now] = 0
    return ans


def main():

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

    print(dfs(0, 1))


if __name__ == '__main__':
    N, M = map(int, input().split())
    a = [0 for i in range(M)]
    b = [0 for i in range(M)]

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

    used = [0 for i in range(N)]
    connect = [[0 for i in range(N)] for i in range(N)]
    main()

Submission status: Accepted

Solution code:
import itertools

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

numlist=[i for i in range(1,n+1)]

plist=list(itertools.permutations(numlist))

sum=0

for challenger in plist:
	if challenger[0] != 1:
		pass
	else:
		needlist=[]
		for i in range(n-1):
			tmp=[]
			tmp.extend([challenger[i],challenger[i+1]])
			tmp.sort()
			needlist.append(tmp)
		addflag=True
		for need in needlist:
			if not need in linelist:
				addflag = False
		
		if addflag:
			sum+=1

print(sum)

Submission status: Accepted

Solution code:
import itertools

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

# 隣接行列を作る
for i in range(M):
    a, b = map(int, input().split())
    adj_matrix[a-1][b-1] = 1
    adj_matrix[b-1][a-1] = 1

cnt = 0

for each in itertools.permutations(range(N)):
    if each[0] != 0:  # 始点は1でないといけないから
        break
    factor = 1
    for i in range(N-1):
        factor *= adj_matrix[each[i]][each[i+1]]
    cnt += factor

print(cnt)

Submission status: Accepted

Solution code:
from itertools import permutations

N, M = map(int, input().split())
Hen = [[]for i in range(N)]


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

T = []
for i in range(1, N):
    T.append(i)

ans = 0
for I in permutations(T):
    flag = True
    S = [0]
    S.extend(I)
    for j in range(N-1):
        if S[j+1] not in Hen[S[j]]:
            flag = False
            break
    if flag:
        ans += 1

print(ans)

Submission status: Accepted

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

li = set()
for i in range(m):
    a,b = map(int,input().split())
    li.add((a,b))
    li.add((b,a))

#print(li)
ans = 0

for v in permutations(range(1,n+1)):
    if v[0] != 1:
        continue
    flag = True
    for i in range(len(v)-1):
        if (v[i],v[i+1]) not in li:
            flag = False
            break
    if flag:
        ans +=1
print(ans)

Submission status: Accepted

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

def dfs(v, used):
    cnt = 0
    used[v] = 1
    if all(used):
        cnt+=1
    for nv in es[v]:
        if used[nv]:
            continue
        cnt += dfs(nv, used)
    used[v] = 0
    return cnt

used = [0] * N
cnt = dfs(0, used)
print(cnt)

Submission status: Accepted

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

def dfs(v, used, cnt):
    used[v] = 1
    if all(used):
        cnt[0]+=1
    for nv in es[v]:
        if used[nv]:
            continue
        dfs(nv, used, cnt)
    used[v] = 0

used = [0] * N
cnt = [0]
dfs(0, used, cnt)

print(cnt[0])

Submission status: Accepted

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

def dfs(v, used):
    global cnt
    used[v] = 1
    if all(used):
        cnt+=1
    for nv in es[v]:
        if used[nv]:
            continue
        dfs(nv, used)
    used[v] = 0


used = [0] * N
cnt = 0
dfs(0, used)
print(cnt)

Submission status: Accepted

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

def dfs(v, used, cnt):
    used[v] = 1
    if all(used):
        cnt.append(1)
    for nv in es[v]:
        if used[nv]:
            continue
        dfs(nv, used, cnt)
    used[v] = 0

used = [0] * N
cnt = []
dfs(0, used, cnt)

print(sum(cnt))

Submission status: Accepted

Solution code:
import itertools

n,m= map(int, input().split())
a= [list(map(int, input().split())) for i in range(m)]
# 経路全探索
ans=0
for v in itertools.combinations(a, n-1):
    b=[[] for i in range(n)]
    for x,y in v:
        b[x - 1].append(y - 1)
        b[y - 1].append(x - 1)

    import collections
    from collections import deque


    def tree(s):

        INF = -10 ** 9
        dis = [INF for i in range(n)]
        dis[s] = 0

        def bfs():
            d = deque()
            d.append(s)

            while len(d):
                x = d.popleft()

                for i in range(len(b[x])):
                    y = b[x][i]
                    if dis[y] == INF:
                        d.append(y)
                        dis[y] = dis[x] + 1

            return max(dis)

        return bfs()
    if tree(0)==n-1:
        ans+=1

print(ans)

Submission status: Accepted

Solution code:
# solution
import io
import math
import itertools as it

nim,mike = map(int, input().split())

arrat = []

for i in range(mike):
    a,b = map(int, input().split())
    arrat.append([a,b])

per = it.permutations(range(2,nim+1),nim-1)

result = 0

for pe in per:
    Flag = True
    pe = list(pe)
    pe.insert(0,1)
    for i in range(len(pe)-1):
        if [pe[i],pe[i+1]] not in arrat and [pe[i+1],pe[i]] not in arrat:
            Flag = False
            break
    if Flag == True:
        result +=1

print(result)

Submission status: Accepted

Solution code:
import copy

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

V = []


def dfs(node, seen, V):

    if seen[node] is True:
        return 0

    seen[node] = True
    if not(False in seen):
        return 1

    ret = 0
    for next_node in V[node]:
        ret += dfs(next_node, copy.deepcopy(seen), V)
    return ret


for _ in range(N):
    V.append(set())

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

print(dfs(0, copy.deepcopy([False] * N), V))