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:
import sys
from itertools import permutations

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    """
    順列を全部試す。計算量O(N!)
    """
    n, m = map(int, input().split())
    tree = [[] for _ in range(n)]
    for _ in range(m):
        a, b = map(int, input().split())
        tree[a - 1].append(b - 1)
        tree[b - 1].append(a - 1)

    res = 0
    for pattern in permutations(range(n)):
        if pattern[0] == 0:
            for i in range(n - 1):
                if pattern[i + 1] not in tree[pattern[i]]:
                    break
            else:
                res += 1
    print(res)


def resolve2():
    """
    bit DP。計算量O(2^N*N^2)
    """
    n, m = map(int, input().split())
    edge = [[f_inf] * n for _ in range(n)]
    for _ in range(m):
        a, b = map(int, input().split())
        edge[a - 1][b - 1] = 1
        edge[b - 1][a - 1] = 1

    dp = [[f_inf] * n for _ in range(1 << n)]
    dp[0][0] = 0
    cnt = [[0] * n for _ in range(1 << n)]
    cnt[0][0] = 1
    for S in range(1 << n):
        for v in range(n):
            for u in range(n):
                if v == u or S & (1 << v) or edge[u][v] == f_inf:
                    continue
                if dp[S | (1 << v)][v] > dp[S][u] + edge[u][v]:
                    dp[S | (1 << v)][v] = dp[S][u] + edge[u][v]
                    cnt[S | (1 << v)][v] = cnt[S][u]
                elif dp[S | (1 << v)][v] == dp[S][u] + edge[u][v]:
                    cnt[S | (1 << v)][v] += cnt[S][u]

    mi = min(dp[-2])
    idx = []
    for i in range(n):
        if dp[-2][i] == mi:
            idx.append(i)

    res = 0
    for j in idx:
        res += cnt[-2][j]
    print(res)


if __name__ == '__main__':
    resolve2()

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    n, m = map(int, input().split())
    edge = [[f_inf] * n for _ in range(n)]
    for _ in range(m):
        a, b = map(int, input().split())
        edge[a - 1][b - 1] = 1
        edge[b - 1][a - 1] = 1

    dp = [[f_inf] * n for _ in range(1 << n)]
    dp[0][0] = 0
    cnt = [[0] * n for _ in range(1 << n)]
    cnt[0][0] = 1
    for S in range(1 << n):
        for v in range(n):
            for u in range(n):
                if v == u or S & (1 << v) or edge[u][v] == f_inf:
                    continue
                if dp[S | (1 << v)][v] > dp[S][u] + edge[u][v]:
                    dp[S | (1 << v)][v] = dp[S][u] + edge[u][v]
                    cnt[S | (1 << v)][v] = cnt[S][u]
                elif dp[S | (1 << v)][v] == dp[S][u] + edge[u][v]:
                    cnt[S | (1 << v)][v] += cnt[S][u]

    mi = min(dp[-2])
    idx = []
    for i in range(n):
        if dp[-2][i] == mi:
            idx.append(i)

    res = 0
    for j in idx:
        res += cnt[-2][j]
    print(res)


if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
from itertools import permutations
N,M=map(int,input().split())
G=[[] for _ in range(N)]
 
for i in range(M):
    a,b=map(int,input().split())
    G[a-1].append(b-1)            #ペアのリストに格納、a=1,b=7ならb=7をリスト0に格納
    G[b-1].append(a-1)            #ペアのリストに格納、a=1,b=7ならa=1をリスト6に格納
  
P=permutations(range(0,N),N)      #(リスト,順列の要素の数)
ans=0

for A in P:
  if A[0]!=0:                     #先頭が1でなければ下は実行されずに次のループへ
    continue
  for i in range(N-1):
    if not (A[i+1]  in G[A[i]]):
      break
  else:
    ans += 1
print(ans)

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
G=[[] for _ 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)

from itertools import permutations

P=permutations(range(1,N),N-1)

cnt=0
for r in P:
    now=0
    F=True
    for x in r:
        if x in G[now]:
            now=x
        else:
            F=False
    if F:
        cnt+=1
print(cnt)

Submission status: Accepted

Solution code:
from itertools import permutations
def main():
    n, m = list(map(int, input().split()))
    G = [set() for _ in range(n)]
    for _ in range(m):
        a, b = list(map(lambda x:int(x) - 1, input().split()))
        G[a].add(b)
        G[b].add(a)
    ans = 0
    for P in permutations(range(1, n)):
        pre = 0
        for p in P:
            if p not in G[pre]:
                break
            pre = p
        else:
            ans += 1
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
G=[[] for _ 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=[0]*N
ans=[]

def DFS(x,n):
    if len(n)==N:
        return True
    for a in G[x]:
        if seen[a]==0:
            seen[a]=1
            if DFS(a,n+str(a)):ans.append(n+str(a))
            seen[a]=0
seen[0]=1
DFS(0,"0")

print(len(ans))

Submission status: Accepted

Solution code:
from itertools import permutations
N,M = map(int,input().split())
cc = [list(map(int,input().split())) for i in range(M)]
count = 0
for i in permutations([i+1 for i in range(N)],N):
  bb = 0
  if i[0] == 1:
    for j in range(N-1):
      aa = [i[j],i[j+1]]
      if aa in cc or aa[::-1] in cc:
        bb += 1
        if bb == N-1:
          count += 1
        continue
      else:
        break
print(count)

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10 ** 8)
from itertools import accumulate
from itertools import permutations
from itertools import combinations
from collections import defaultdict
from collections import Counter
import fractions
import math
from collections import deque
from bisect import bisect_left
from bisect import bisect_right
from bisect import insort_left
import itertools
from heapq import heapify
from heapq import heappop
from heapq import heappush
import heapq
from copy import deepcopy
from decimal import Decimal
alf = list("abcdefghijklmnopqrstuvwxyz")
ALF = list("ABCDEFGHIJKLMNOPQRSTUVWXYZ")
#import numpy as np
INF = float("inf")
#d = defaultdict(int)
#d = defaultdict(list)
N,M = map(int,input().split())
P = [[] for _ in range(N)]
for i in range(M):
    a,b = map(int,input().split())
    a,b = a-1,b-1
    P[a].append(b)
    P[b].append(a)
ans = 0
def dfs(cur,d,num):
    global ans
    if num == N:
        ans += 1
        return
    else:
        li = P[cur]
        for chi in li:
            if d[chi] == 1:
                continue
            c = deepcopy(d)
            c[chi] += 1
            dfs(chi,c,num+1)
        return
d = defaultdict(int)
d[0] += 1
dfs(0,d,1)
print(ans)

Submission status: Accepted

Solution code:
import itertools

n, m = map(int, input().split())
ab = [list(map(lambda x:int(x)-1, input().split())) for _ in range(m)]

nodes = [i for i in range(n)]
ls = list(itertools.permutations(nodes))

ans = 0
for root in ls:
    if root[0] != 0:
        continue
    ok = 1
    for i in range(n-1):
        if list(root[i:i+2]) not in ab and list(reversed(list(root[i:i+2]))) not in ab:
            ok = 0
    if ok:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
import sys
import math
import itertools
import statistics
n,m=map(int,input().split())
side=[]
for _ in range(m):
    side.append(tuple(map(int,input().split())))
per_lis =[i for i in list(itertools.permutations(list(range(1,n+1)))) if i[0]==1]
ans=0
for one_case in per_lis:
    tmp=0
    for i in range(n-1):
        if ((one_case[i],one_case[i+1]) in side) or ((one_case[i+1],one_case[i]) in side):
            tmp+=1
    if tmp==n-1:
        ans+=1
print(ans)

Submission status: Accepted

Solution code:
import sys

def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())

n,m = LI()

graph = [[] for _ in range(n)]
for _ in range(m):
    a, b = LI()
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)  # 有向グラフなら消す

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

def dfs(v,seed):
    if all(seed):
        return 1
    ans = 0
    for i in graph[v]:
        if seed[i]:
            continue
        seed[i] = True
        ans += dfs(i,seed)
        seed[i] = False
    return ans
print(dfs(0,seed))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
N,M = map(int, input().split())
G = [[] for j 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)
visited = [False]*N
visited[0] = True
#再帰
def DFS(v,visited):
    #もし全てTrueなら1を返す
    if all(visited):
        return 1
    ans = 0
    for i in G[v]:
        if visited[i]:
            continue
        visited[i] = True
        ans += DFS(i,visited)
        visited[i] = False
    return ans

print(DFS(0,visited))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
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)

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

def DFS(v,used):
    if all(used):
        return 1
    ans = 0
    for i in graph[v]:
        if used[i]:
            continue
        used[i] = True
        ans += DFS(i,used)
        used[i] = False
    return ans
  
print(DFS(0,used))

Submission status: Accepted

Solution code:
from collections import deque

def dfs(G, visited, s, n, ans):
  # すべての頂点を訪れた場合の処理
  if all(visited) :
    ans += 1
    return ans
  #　次の頂点の探索
  for i in G[s] :
    if visited[i] == False :
      visited[i] = True
      ans = dfs(G, visited, i, n, ans)
      visited[i] = False
  return ans

#　グラフGの入力
n,m = map(int,input().split())
G = [[] for j 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)
  

visited = [False for i in range(n)]
visited[0] = True
ans = 0
print(dfs(G, visited, 0, n, ans))

Submission status: Accepted

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

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

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

print(dfs(0,N,visited))

Submission status: Accepted

Solution code:
import math
#import numpy as np
import itertools
import queue
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)

def main():
    n,m = map(int,ipt().split())
    way = [[] for i in range(n+1)]
    ans = 0
    for i in range(m):
        a,b = map(int,ipt().split())
        way[a].append(b)
        way[b].append(a)
    for i in itertools.permutations(list(range(2,n+1))):
        p = 1
        f = True
        for j in i:
            if not j in way[p]:
                f = False
                break
            else:
                p = j
        if f:
            ans += 1
    print(ans)

    return None

if __name__ == '__main__':
    main()

Submission status: Accepted

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

def dfs(v, seen):
    if all(seen):
        return 1
    ans=0
    for vv in graph[v]:
        if seen[vv]:
            continue
        seen[vv]=True
        ans+=dfs(vv, seen)
        seen[vv]=False
    return ans

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

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
graph = [[] for _ 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)

def dfs(v, seen):
    if all(seen):
        return 1
    ans=0
    for i in graph[v]:
        if seen[i]:
            continue
        seen[i]=True
        # print(seen)
        ans+=dfs(i, seen)
        seen[i]=False
    return ans

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

Submission status: Accepted

Solution code:
from itertools import permutations
import math
n,m = map(int,input().split())
G = [[] for i in range(n)]
ans = 0
for i in range(m):
  a,b = map(int,input().split())
  G[a-1].append(b-1)
  G[b-1].append(a-1)
for per in permutations(range(n)):
  if per[0] != 0:
    continue
  for i in range(n-1):
    if not (per[i+1]  in G[per[i]]):
      break
  else:
    ans += 1
print(ans)

Submission status: Accepted

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

ans = 0
def dfs(x, visited):
    global ans
    if len(visited) == N:
        ans += 1
        return

    for b in ab[x]:
        if b not in visited:
            dfs(b, visited + [b])
    return

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

Submission status: Accepted

Solution code:
import itertools

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

ans = 0
for v in itertools.permutations(range(1, N)):
    ok = True
    a = 0
    for b in v:
        if {a, b} not in ab:
            ok = False
            break
        a = b
    if ok:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
import itertools

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

seq = list(range(2, n+1))
ptr = list(itertools.permutations(seq, n-1))

ans = 0
for i in ptr:
    flag2 = True
    for j in range(n-1):
        flag = False
        if j == 0:
            for a,b in ab:
                if (a,b) == (1,i[j]) or (a,b) == (i[j],1):
                    flag = True
                    break
        else:
            for a,b in ab:
                if (a,b) == (i[j], i[j-1]) or (a,b) == (i[j-1], i[j]):
                    flag = True
                    break
        if not flag:
            flag2 = False
            break
    if flag2:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
(n,m), *ab = [list(map(int, s.split())) for s in open(0)]

from collections import defaultdict

d = defaultdict(list)

for a,b in ab:
    d[a] += [b]
    d[b] += [a]

def count_paths(passed, cur, d, n):
#     print(f'{passed=}, {cur=}')
    if len(passed) == n-1:
        return 1
    ans = 0
    for nx in d[cur]:
        if nx not in passed:
            ans += count_paths(passed+[cur], nx, d, n)
    return ans

print(count_paths([],1,d,n))

Submission status: Accepted

Solution code:
from itertools import permutations
N,M = map(int,input().split())
G = {i:[] for i in range(1,N+1)}
for _ in range(M):
    a,b = map(int,input().split())
    G[a].append(b)
    G[b].append(a)
cnt = 0
for x in permutations(range(2,N+1),N-1):
    flag = 0
    for i in range(N-1):
        if i==0:
            if x[0] in G[1]:continue
            else:
                flag = 1
                break
        if x[i] in G[x[i-1]]:continue
        else:
            flag = 1
            break
    if flag==0:
        cnt += 1
print(cnt)

Submission status: Accepted

Solution code:
from itertools import *
N,M=map(int,input().split())
X=list(permutations(list(range(2,N+1))))
P=0
a,b=0,0
S=set()
for i in range(M):
  a,b=map(int,input().split())
  S.add((a,b))
  S.add((b,a))
for i in range(len(X)):
  for j in range(N-1):
    if not(((1 if j==0 else X[i][j-1]),X[i][j]) in S):
      break
    if j==N-2:
      P+=1
print(P)

Submission status: Accepted

Solution code:
from itertools import permutations

n, m = map(int, input().split())
G = [set() for _ in range(n)]
for _ in range(m):
  a, b = map(int, input().split())
  a -= 1
  b -= 1
  G[a].add(b)
  G[b].add(a)
ans = 0
for l in permutations(range(n)):
  if l[0] != 0:
    continue
  for i in range(n-1):
    if l[i+1] not in G[l[i]]:
      break
  else:
    ans += 1
print(ans)

Submission status: Accepted

Solution code:
from itertools import permutations


N, M = [int(i) for i in input().split()]
D = [[False] * N for _ in range(N)]
for _ in range(M):
    a, b = [int(i) for i in input().split()]
    D[a - 1][b - 1] = True
    D[b - 1][a - 1] = True
perm = [[0] + list(p) for p in list(permutations(range(1, N)))]

cnt = 0
for p in perm:
    flg = True
    for i in range(N - 1):
        if not D[p[i]][p[i + 1]]:
            flg = False
            break
    if flg:
        cnt += 1
print(cnt)

Submission status: Accepted

Solution code:
(n, m) = tuple(map(int, input().split()))
(a, b) = zip(*list([input().split() for _ in range(m)]))

pt_c_ns = {}
for i in range(1, n + 1):
    pt_c_ns[str(i)] = []
for i in range(m):
    pt_c_ns[a[i]].append(b[i])
    pt_c_ns[b[i]].append(a[i])

paths_c = ["1"]
for _ in range(n - 1):
    paths_n = []
    for path in paths_c:
        pt_c = path[-1]
        pt_ns = pt_c_ns[pt_c]
        for pt_n in pt_ns:
            if pt_n not in path:
                paths_n.append(path + pt_n)
    paths_c = paths_n[:]

print(len(paths_c))

Submission status: Accepted

Solution code:
import itertools
N,M = list(map(int,input().split()))
lis = []
for i in range(N):
    lis.append([i+1])
for i in range(M):
    a,b = list(map(int,input().split()))
    lis[a-1].append(b)
    lis[b-1].append(a)
pemls = [i for i in range(2,N+1)]
lis_root = list(itertools.permutations(pemls,N-1))

counter = 0
for i in range(len(lis_root)):
    now = 1
    step = [1]
    flag = 1
    for j in range(len(lis_root[i])):
        #print("root:"+str(lis_root[i])+ " now:"+str(now) )
        if lis_root[i][j] in lis[now-1]:
            now = lis_root[i][j]
            step.append(now)
        else:
            flag = 0
            break
        if len(step) == N:
            break
    if flag ==1:
        counter += 1
        #print(counter)
print(counter)

Submission status: Accepted

Solution code:
from itertools import permutations
n, m = map(int, input().split())
g = [[] for _ in range(n)]
for _ in range(m):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    g[a].append(b)
    g[b].append(a)
ans = 0
for order in permutations(range(1, n), n-1):
    seen = [False] * n
    seen[0] = True
    pre = 0
    for v in order:
        if v not in g[pre] or seen[v]:
            break
        pre = v
        seen[v] = True
    else:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
import sys


def resolve():
    import itertools
    readline = sys.stdin.readline    # 1行だけ文字列にする

    N, M = map(int, readline().split())
    lst = [set(map(int, readline().split())) for _ in [0] * M]
    d = []
    ans = 0
    # for i in range(2, N + 1):
    #     d.append(i)
    for i in itertools.permutations(range(2, N + 1), N - 1):
        cnt = 0
        if {1, i[0]} in lst:
            cnt += 1
            for j in range(N - 2):
                if {i[j], i[j + 1]} in lst:
                    cnt += 1
                    pass
                else:
                    break
        if cnt == N - 1:
            ans += 1
    print(ans)
    

if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
def resolve():
    import sys
    import itertools
    readline = sys.stdin.readline    # 1行だけ文字列にする

    N, M = map(int, readline().split())
    lst = [set(map(int, readline().split())) for _ in [0] * M]
    d = []
    ans = 0
    for i in range(2, N + 1):
        d.append(i)
    for i in itertools.permutations(d, N - 1):
        cnt = 0
        if {1, i[0]} in lst:
            cnt += 1
            for j in range(N - 2):
                if {i[j], i[j + 1]} in lst:
                    cnt += 1
                    pass
                else:
                    break
        if cnt == N - 1:
            ans += 1
    print(ans)
    

if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
from itertools import permutations
import sys


def input(): return sys.stdin.readline().strip()
def I(): return int(input())
def LI(): return list(map(int, input().split()))
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def S(): return input()
def LS(): return input().split()


INF = float('inf')
n, m = LI()
edges = [[False] * n for _ in range(n)]  # edges[i][j] : 頂点 i から j へ向かう辺がある
for _ in range(m):
    a, b = LI()
    a -= 1
    b -= 1
    edges[a][b] = True
    edges[b][a] = True

# ハミルトン路 ： 頂点を一度だけ通る路のこと
# ハミルトン閉路 : 全頂点を一度だけ通る閉路のこと
# 関連 : オイラー路 ： 全辺を一度だけ通る路のこと

# 開始地点である頂点 1 をぞの板頂点の順列を全列挙
permu = list(permutations(range(1, n)))

ans = 0
for p in permu:
    now = 0  # 頂点 1 から順列にある頂点の順番を参考に各頂点に向かってみる
    is_ok = True  # 条件を満たすか
    for j in p:
        if edges[now][j]:
            now = j
        else:
            is_ok = False
            break
    if is_ok:
        ans += 1


print(ans)

Submission status: Accepted

Solution code:
from itertools import permutations
n, m = map(int, input().split())
path = []
for i in range(m):
    a, b = map(int, input().split())
    path.append([a,b])
    path.append([b,a])
import itertools
per = [i for i in range(2,n+1)]
data = list(itertools.permutations(per, n-1))  
flg = 0
for k in range(len(data)):
    tmp = [[1, data[k][0]]]
    for i in range(n-2):
        tmp.append([data[k][i],data[k][i+1]])
    cnt = 0
    for var in tmp:
        if var in path:
            cnt += 1
    if cnt == len(tmp):
        flg += 1
print(flg)

Submission status: Accepted

Solution code:
from itertools import permutations
n, m = map(int, input().split())
path = []
for i in range(m):
    a, b = map(int, input().split())
    path.append([a,b])
    path.append([b,a])
import itertools
per = [i for i in range(2,n+1)]
data = list(itertools.permutations(per, n-1))    
flg = 0
for k in range(len(data)):
    tmp = [[1, data[k][0]]]
    for i in range(n-2):
        tmp.append([data[k][i],data[k][i+1]])
    cnt = 0
    for var in tmp:
        if var in path:
            cnt += 1
    if cnt == len(tmp):
        flg += 1
print(flg)

Submission status: Accepted

Solution code:
import itertools

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

for m in range(M):
    a, b = map(int, input().split())
    transit[a-1][b-1] = 1
    transit[b-1][a-1] = 1
permutation = list(itertools.permutations(list(range(1, N+1))))
ans = 0
for p in permutation:
    if p[0] != 1:
        continue
    for i in range(len(p) - 1):
        if transit[p[i]-1][p[i+1]-1] != 1:
            break
        if i == len(p) - 2:
            ans += 1
print(ans)

Submission status: Accepted

Solution code:
def kaijyo(n):
    ans = 1
    for i in range(n):
        ans *= i + 1
    return ans

N,M = map(int,input().rstrip().split(" "))
hen = []
ans = 0
for i in range(M):
    a,b = map(int,input().rstrip().split(" "))
    hen.append([a,b])
for i in range(kaijyo(N-1)):
    lis = [i+2 for i in range(N-1)]
    lis2 = [1]
    k = i
    for i2 in range(N-1):
        lis2.append(lis[k % (N - 1 - i2)])
        k = k // (N - 1 - i2)
        for i3 in range(len(lis)):
            if lis[i3] == lis2[-1]:
                lis.pop(i3)
                break
    for i2 in range(N-1):
        if not ([lis2[i2],lis2[i2+1]] in hen or [lis2[i2+1],lis2[i2]] in hen):
            break
        if i2 == N - 2:
            ans += 1
print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)
n, m = map(int, input().split())
ab = [[] for i in range(n)]
for i in range(m):
  a, b = map(int, input().split())
  a -= 1
  b -= 1
  ab[a].append(b)
  ab[b].append(a)

ary = []
def dfs(s,t):
  if len(t) == n:
    ary.append(t)
    return
  for i in ab[s]:
    if i not in t:
      dfs(i,t+[i])
  return
dfs(0,[0])

print (len(ary))

Submission status: Accepted

Solution code:
N,M=map(int, input().split())
l=[list(map(int, input().split())) for _ in range(M)]
ans=[i for i in range(1,N+1)]
c=[1]


def dfs(cnt):
	if len(cnt)==N and sorted(cnt)==ans:
		return 1
	elif len(cnt)>=N:
		return 0
	temp=[]
	ret=0
	for i in range(M):
		if cnt[-1]==l[i][0]:
			temp.append(l[i][1])
		elif cnt[-1]==l[i][1]:
			temp.append(l[i][0])
	for h in temp:
		cnt.append(h)
		ret+=dfs(cnt)
		cnt.pop(-1)
	return ret

print(dfs(c))

Submission status: Accepted

Solution code:
from itertools import permutations


def nearlist(N, LIST):  # 隣点リスト
    NEAR = [set() for _ in range(N)]
    for a, b in LIST:
        NEAR[a - 1].add(b - 1)
        NEAR[b - 1].add(a - 1)
    return NEAR


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

ans, near = 0, nearlist(n, ab)
for l in permutations(range(1, n), n - 1):
    s = 0
    for i in l:
        t = i
        if t not in near[s]:
            break
        s = t
    else:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
###==================================================
### import
#import bisect
from collections import Counter, deque, defaultdict
from copy import deepcopy
#from functools import reduce, lru_cache
#from heapq import heappush, heappop
#import itertools
#import math
#import string
import sys
### stdin
def input(): return sys.stdin.readline()
def iIn(): return int(input())
def iInM(): return map(int, input().split())
def iInM1(): return map(int1, input().split())
def iInLH(): return list(map(int, input().split()))
def iInLH1(): return list(map(int1, input().split()))
def iInLV(n): return [iIn() for _ in range(n)]
def iInLV1(n): return [iIn()-1 for _ in range(n)]
def iInLD(n): return [iInLH() for _ in range(n)]
def iInLD1(n): return [iInLH1() for _ in range(n)]
def sInLH(): return list(input().split())
def sInLV(n): return [input().rstrip('\n') for _ in range(n)]
def sInLD(n): return [sInLH() for _ in range(n)]
### stdout
def OutH(lst, deli=' '): print(deli.join(map(str, lst)))
def OutV(lst): print('\n'.join(map(str, lst)))
### setting
sys.setrecursionlimit(10 ** 6)
### utils
int1 = lambda x: int(x) - 1
### constants
INF = int(1e9)
MOD = 1000000007
dx = (-1, 0, 1, 0)
dy = (0, -1, 0, 1)
###---------------------------------------------------

N, M = iInM()
AB = iInLD(M)

ans = 0
q= deque([[[1], []]]) # [[nodes], [edges]]

while len(q) > 0:
    n, e = q.pop()
    if len(n) == N:
        ans += 1
        continue
    for i in range(M):
        if i in e:
            continue
        if AB[i][0] == n[-1]:
            if AB[i][1] not in n:
                new_n = n[:]
                new_e = e[:]
                new_n.append(AB[i][1])
                new_e.append(i)
                q.append([new_n, new_e])
                continue
        if AB[i][1] == n[-1]:
            if AB[i][0] not in n:
                new_n = n[:]
                new_e = e[:]
                new_n.append(AB[i][0])
                new_e.append(i)
                q.append([new_n, new_e])
                continue

print(ans)

Submission status: Accepted

Solution code:
import itertools

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

ans = 0
l = [i for i in range(2,n+1)]
for v in itertools.permutations(l,n-1):
    flag = True
    if v[0] not in path[1]:
        flag = False
        continue
    for k in range(1,n-1):
        if v[k] not in path[v[k-1]]:
            flag = False
            continue
    if flag:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
import sys
from itertools import permutations

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


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

    res = 0
    for pattern in permutations(range(n)):
        if pattern[0] == 0:
            for i in range(n - 1):
                if pattern[i + 1] not in tree[pattern[i]]:
                    break
            else:
                res += 1
    print(res)



if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
import itertools
N,M = map(int,input().split())
L=[]
for i in range(M):
    a,b=map(int,input().split())
    L.append([a,b])

number=[]
for i in range(1,N+1):
    number.append(i)
    
ans=0

for v in itertools.permutations(number,N):
    a=0
    v=list(v)
    for j in range(N-1):
        if ([v[j],v[j+1]] not in L ) and ([v[j+1],v[j]] not in L):
            a=1
    if a==0 and v[0]==1:
        ans+=1

print(ans)

Submission status: Accepted

Solution code:
import itertools
N,M=map(int,input().split())
edges={tuple(sorted(map(int,input().split()))) for i in range(M)}
ans=0
for i in itertools.permutations(range(2,N+1)):
    l=[1]+list(i)
    ans+=sum(1 for edge in zip(l,l[1:]) if tuple(sorted(edge)) in edges)==N-1
print(ans)

Submission status: Accepted

Solution code:
import itertools
N,M=map(int,input().split())
edges={tuple(sorted(map(int,input().split()))) for i in range(M)}
ans=0
for i in itertools.permutations(range(2,N+1),N-1):
    l=[1]+list(i)
    ans+=sum(1 for edge in zip(l,l[1:]) if tuple(sorted(edge)) in edges)==N-1
print(ans)