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 itertools as itl
n, m=map(int, input().split())
#ここでリストを作成する
hen=[]
check=0

for _ in range(m):
  hen.append(list(map(int, input().split())))
#print(hen)
l=list(range(2, n+1))
for v in itl.permutations(l):
  #print(v)
  for i in range(n-2):
    if not(sorted(v[i:i+2]) in hen) or not(list([1, v[0]]) in hen):
      break
  else:
    if n==2:
      check+=1
    elif i==n-3:
      check+=1
    continue
print(check)

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)
    
bin = [2 ** i for i in range(n + 1)]

def bfs(bit, pos, s):
    global ans
    if bit == bin[-1] - 1:
        ans += 1
        return
    for next_pos in ab[pos]:
        if (bit // bin[next_pos]) % 2 == 1:
            continue
        bfs(bit + bin[next_pos], next_pos, s + str(next_pos + 1))

ans = 0
bfs(1, 0, "1")
print(ans)

Submission status: Accepted

Solution code:
#abc 054 C
n,m = map(int, input().split()) #  N頂点 ,M辺
connect = [[] for i in range(n)]
for i in range(m):
    a,b = map(int, input().split())
    connect[a-1].append(b -1)
    connect[b -1].append(a -1)
#print(connect)
import itertools 

state = list(itertools.permutations(list(range(n)) ,n ))
def abc054c(i):#
    counter = 1
    if i[0] != 0:
        return 0
    for j,k  in enumerate(i):
        if j == n -1:
            pass
        elif i[j +1] in connect[k]:
            pass
        else:
            counter = 0
            break
    return counter
total = 0
for  i in state:
    total += abc054c(i)
    
print(total)

Submission status: Accepted

Solution code:
# coding: utf-8
# hello worldと表示する
import sys
import numpy
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil,pi,factorial
from operator import itemgetter
from copy import deepcopy
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
def SI(): return input().rstrip()
def printns(x): print('\n'.join(x))
def printni(x): print('\n'.join(list(map(str,x))))
inf = 10**17
mod = 10**9 + 7

n,m=MI()
tree=[[] for i in range(n)]
for i in range(m):
    a,b=MI()
    a-=1;b-=1
    tree[a].append(b)
    tree[b].append(a)
#print(tree)
#count=0
#global count
count=0
def dfs(x,al):
    global count
    if len(al+[x])==n:
        count+=1
        #print(count)
        return
    #if x==0:
        #al=[]
    #al.append(x)
    #print(al)
    for y in tree[x]:
        if not (y in al):
            #print(y,al+[x])
            dfs(y,al+[x]) #return
dfs(0,[])
print(count)

Submission status: Accepted

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

ans = 0
def dfs(visited, current):
    global ans
    if len(visited) == n:
        ans += 1
        return
    for nex in mat[current]:
        if nex not in visited:
            _vi = visited[:]
            _vi.append(nex)
            dfs(_vi, nex)

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

Submission status: Accepted

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

res = 0
for case in itertools.permutations(range(n)):
  if case[0] != 0:
    continue
  for i in range(n-1):
    if case[i+1] not in path[case[i]]:
      break
  else:
    res+=1
print(res)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**5)
def solve():
    N,M = map(int,input().split())
    G = [[False]*N for _ in range(N)]
    for _ in range(M):
        a, b = map(int,input().split())
        a -= 1
        b -= 1
        G[a][b] = True
        G[b][a] = True
    
    visited = [False] * N
    print(dfs(0, G, visited[:], N))

def dfs(now, G, visited, N):
    visited[now] = True
    if not (False in visited):
        return 1
    
    cnt = 0
    for next in range(N):
        if not visited[next] and G[now][next]:
            cnt += dfs(next,G,visited[:],N)
    
    return cnt

if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
from itertools import permutations

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

all_routes = list(permutations([i for i in range(1, N + 1)]))

ans = 0
for route in all_routes:
    flg = True
    if route[0] != 1:
        break
    for i in range(1, N):
        if path[route[i-1] - 1][route[i] - 1] != 1:
            flg = False
            break
    if flg:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
from itertools import permutations
N,M = list(map(int,input().split()))
e = [list(map(int,input().split())) for i in range(M)]
a = 0

for p in permutations(range(1,N+1)):
  f = True
  if p[0]==1:
    for i in range(N-1):
      if sorted([p[i],p[i+1]]) not in e:
        f = False
    if f:
      a+=1

print(a)

Submission status: Accepted

Solution code:
from collections import deque
import copy
n,m = map(int,input().split())
Map = [[] for i in range(n)]

for i in range(m):
    a,b = map(int,input().split())
    Map[a-1].append(b-1)
    Map[b-1].append(a-1)
visit = [False for i in range(n)]
ans = 0
q = deque()
q.append((0,visit))
while q:
    index,visit = q.popleft()
    Visit = copy.deepcopy(visit)
    if not Visit[index]:
        Visit[index] = True
    else:
        continue
    if all(Visit):
        ans += 1
        continue
    for i in Map[index]:
        q.append((i,Visit))
print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 9)
N, M = map(int, input().split())
G = [[] for _ in range(N)]
for _ in range(M):
    a, b = map(int, input().split())
    G[a - 1].append(b - 1)
    G[b - 1].append(a - 1)
D = [0] * N
D[0] = 1

C = 0
def dfs(n):
    global C
    if not 0 in D:
        C += 1
        return
    for i in G[n]:
        if D[i] == 1:
            continue
        D[i] = 1
        dfs(i)
        D[i] = 0

dfs(0)
print(C)

Submission status: Accepted

Solution code:
from collections import deque
from copy import deepcopy

N, M = map(int, input().split())
paths = [[] for n in range(N)]
def add_paths(a, b):
    paths[a - 1].append(b - 1)
    paths[b - 1].append(a - 1)

for i in range(M):
    a, b = map(int, input().split())
    add_paths(a, b)
route = deque([(0, paths[0], [False for n in range(N)])])
ans = 0
while len(route) > 0:
    vertex, path, visited = route.pop()
    visited[vertex] = True
    for i in path:
        if visited[i] != True:
            route.append((i, paths[i], deepcopy(visited)))
    if visited.count(False) == 0:
        ans += 1
print(ans)

Submission status: Accepted

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

    # create graph G
    G = {}
    for m in range(M):
        a, z = map(int, input().split())
        G[a] = G.get(a, [])
        G[a].append(z)
        G[z] = G.get(z, [])
        G[z].append(a)

    # print(G)

    # find all paths
    if G.get(1, 0) == 0:
        print(0)
        return

    def dfs(a, path):
        path.append(a)
        if len(path) == N:
            return 1

        paths = 0
        for z in G.get(a):
            if z in path:
                continue
            paths += dfs(z, path[:])

        return paths

    print(dfs(1, []))


##########
if __name__ == "__main__":
    abc054_c_one_stroke_paths()

Submission status: Accepted

Solution code:
def abc054_c_one_stroke_paths():
    import copy
    N, M = map(int, input().split())

    # create graph G
    G = {}
    for m in range(M):
        a, z = map(int, input().split())
        G[a] = G.get(a, [])
        G[a].append(z)
        G[z] = G.get(z, [])
        G[z].append(a)

    # print(G)

    # find all paths
    if G.get(1, 0) == 0:
        print(0)
        return

    paths = []

    def solve(a, path):
        path.append(a)
        if len(path) == N:
            paths.append(path)
            return
        for z in G.get(a):
            p = copy.copy(path)
            if z in p:
                continue
            solve(z, p)

    solve(1, [])
    # print(paths)
    print(len(paths))


##########
if __name__ == "__main__":
    abc054_c_one_stroke_paths()

Submission status: Accepted

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

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    # divisors.sort()
    return divisors

def ValueToBits(x,digit):
    res = [0 for i in range(digit)]
    now = x
    for i in range(digit):
        res[i]=now%2
        now = now >> 1
    return res

def BitsToValue(arr):
    n = len(arr)
    ans = 0
    for i in range(n):
        ans+= arr[i] * 2**i
    return ans

def ZipArray(a):
    aa = [[a[i],i]for i in range(n)]

    aa.sort(key = lambda x : x[0])
    for i in range(n):
        aa[i][0]=i+1
    aa.sort(key = lambda x : x[1])
    b=[aa[i][0] for i in range(len(a))]
    return b

def ValueToArray10(x, digit):
    ans = [0 for i in range(digit)]
    now = x
    for i in range(digit):
        ans[digit-i-1] = now%10
        now = now //10
    return ans

def Zeros(a,b):
    if(b<=-1):
        return [0 for i in range(a)]
    else:
        return [[0 for i in range(b)] for i in range(a)]

def AddV2(v,w):
    return [v[0]+w[0],v[1]+w[1]]

dir4 = [[1,0],[0,1],[-1,0],[0,-1]]


def clamp(x,y,z):
    return max(y,min(z,x))

class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
 
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
 
    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i
            
#
def Zaatsu(a):
    a.sort()
    now = a[0][0]
    od = 0
    for i in range(n):
        if(now==a[i][0]):
            a[i][0]=od
        else:
            now = a[i][0]
            od+=1
            a[i][0] = od
    
    a.sort(key = lambda x : x[1])
    return a

class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n+1)]
        self.rank = [0] * (n+1)

    # 検索
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    # 併合
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    # 同じ集合に属するか判定
    def same_check(self, x, y):
        return self.find(x) == self.find(y)


'''
def cmb(n, r, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % p

p = 2
N = 10 ** 6 + 2
fact = [1, 1]  # fact[n] = (n! mod p)
factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p)
inv = [0, 1]  # factinv 計算用

for i in range(2, N + 1):
    fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)

'''

def rl(x):
    return range(len(x))

# a = list(map(int, input().split()))

#################################################
#################################################
#################################################
#################################################



#22-

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

for i in range(m):
    p,q = list(map(int, input().split()))
    p-=1
    q-=1
    nb[p][q]=1
    nb[q][p]=1

import itertools
L = list(itertools.permutations(range(n)))
ans = 0
for i in L:
    if(i[0]!=0):
        continue
    ok = 1
    for j in range(1,n):
        if(not i[j] in nb[i[j-1]]):
            ok=0
            break
    if(ok==0):
        continue
    else:
        ans += 1
        #print(i)
        
print(ans)

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
edge = [[] for i in range(n)]
for i in range(m):
    x,y = map(int,input().split())
    edge[x-1].append(y-1)
    edge[y-1].append(x-1)
def dfs(visited,i):
    visited.append(i)
    if len(visited) == n:
        return 1
    count = 0
    for j in edge[i]:
        if j in visited:
            continue
        count += dfs(visited[:],j)
    return count
print(dfs([],0))

Submission status: Accepted

Solution code:
from collections import deque
import numpy as np
import math
import copy
import bisect  # index = bisect.bisect_left(list,num)

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

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


q = deque()
ans = 0
visited = [False for i in range(N)]
visited[0] = True
q.append((0, visited))
while(len(q) > 0):
    #print("q:", q)
    tmp, visited = q.popleft()
    if not(False in visited):
        ans += 1
    for e in E[tmp]:
        if not visited[e]:
            tmp_visited = copy.deepcopy(visited)
            tmp_visited[e] = True
            #print(e, tmp_visited)
            q.append((e, copy.deepcopy(tmp_visited)))

print(ans)

Submission status: Accepted

Solution code:
import sys
import itertools
import copy

input = sys.stdin.readline

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    N, M = MI()
    numlist = [i for i in range(1, N)]
    mylist2 = [[0 for i in range(N)] for j in range(M)]
    result = 0
    for i in range(M):
        a, b = MI()
        mylist2[min(a, b) - 1][max(a, b) - 1] = 1
    for j in itertools.permutations(numlist, len(numlist)):
        mylist = copy.deepcopy(mylist2)
        index = 0
        past = 0
        for k in j:
            try:
                
                if mylist[min(past, k)][max(past, k)] == 1:
                    mylist[min(past, k)][max(past, k)] = 0
                    past =  k
                    index += 1
                else:
                    break
            except:
                if mylist[0][k] == 1:
                    mylist[0][k] = 0
                    past = k
                    index += 1
                else:
                    break
        if index == len(numlist):
            result += 1
    print(result)
    
main()

Submission status: Accepted

Solution code:
import itertools
N,M=map(int,input().split())
ki=[[]for i in range(N)]
for i in range(M):
 a,b=map(int,input().split())
 ki[a-1].append(b-1)
 ki[b-1].append(a-1)
ans=0
for v in itertools.permutations(range(1,N), N-1):
 path=0
 if v[0] in ki[0]:
  path+=1
 if N>2:
  for i in range(N-2):
   if v[i+1] in ki[v[i]]:
    path+=1
 if path==N-1:
  ans+=1
print(ans)

Submission status: Accepted

Solution code:

from collections import deque
from copy import deepcopy

def parse():
  N, M = map(int, input().split(" "))
  # A, B = [], []
  edges = [[] for n in range(N)]
  for m in range(M):
    a, b = map(int, input().split(" "))
    edges[a - 1].append(b - 1)
    edges[b - 1].append(a - 1)
  return N, M, edges

def main():
  N, M, edges = parse()
  # print(N, M, edges)

  # visited = [False for n in range(N)]
  stack = deque([(0, edges[0], [False for n in range(N)])])
  ans = 0
  while len(stack) > 0:
    i, paths, visited = stack.pop()
    visited[i] = True
    for path in paths:
      # print("next_path:", path)
      if not visited[path]:
        stack.append((path, edges[path], deepcopy(visited)))
    
    # print(i, paths, visited)
    if not (False in visited):
      ans += 1

  print(ans)

if __name__ == "__main__":
  main()

Submission status: Accepted

Solution code:
from itertools import permutations
def main():
    N,M = map(int, input().split())
    edge = [[False]*N for _ in range(N)]
    for i in range(M):
        a,b = map(lambda x:x-1, map(int, input().split()))
        edge[a][b] = True
        edge[b][a] = True
    ans = 0
    for perm in permutations([i for i in range(1,N)]):
        arrived = [False]*N
        flag = False
        prev = 0
        for p in perm:
            # edgeが存在しない
            if not edge[prev][p]:
                flag = True
                break
            # edgeが存在
            else:
                # 過去に訪れた
                if arrived[p]:
                    flag = True
                    break
                else:
                    arrived[p] = True
            prev = p
        if not flag:
            ans += 1
    print(ans)
main()

Submission status: Accepted

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

#各部屋の通じてる部屋番のリストを作る
l=[[] for _ in range(n)]
for i in range(m):
    a,b=s[i][0],s[i][1]
    l[a-1].append(b)
    l[b-1].append(a)

def dfs(now, prev, visited):
    visited.append(now)#行った頂点を追加していって全て行ったなら+1
    if len(visited) == n:
        return 1
 
    ret = 0 #条件を満たす数の初期値
    for edge in l[now-1]:#今の場所からいける頂点がまだ行ったことのない場合そこを同様に再度探索
        if edge == prev:
            continue
        if edge in visited:
            continue
 
        ret += dfs(edge, prev, visited[:])#そこで全ての頂点を網羅したなら+1(dfs文最初の部分)
 
    return ret #総計値を返す

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

Submission status: Accepted

Solution code:
import sys
#import numpy as np
import math
import itertools
#from fractions import Fraction
#import itertools
#from collections import deque
#import heapq
#from fractions  import gcd
#input=sys.stdin.readline
n,m=map(int,input().split())
v=tuple(tuple(map(lambda x: int(x)-1,input().split())) for _ in range(m))

node=[[] for _ in range(n)]
for pair in v:
    node[pair[0]].append(pair[1])
    node[pair[1]].append(pair[0])
c=0
p=list(itertools.permutations(list(range(1,n))))
for res in p:
    for i in range(n-1):
        if i==0:
          if res[0] in node[0]:
            continue
          else:
            break
        if res[i] in node[res[i-1]]:
            continue
        else:
            break
    else:
        c+=1
print(c)

Submission status: Accepted

Solution code:
import itertools
N, M = map(int, input().split())
l = []
seq = []
for i in range(1,N+1):
  seq.append(i)
  i+=1
for _ in range(M):
    A = list(map(int, input().split()))
    l.append(A)
cnt = 0
for i in list(itertools.permutations(seq)):
  if i[0]!=1:
    continue
  for j in range(N-1):
    if sorted([i[j],i[j+1]]) in l:
      if j == N-2:
        cnt += 1
    else:
      break
print(cnt)

Submission status: Accepted

Solution code:
import itertools
N, M = map(int, input().split())
l = []
seq = []
for i in range(N):
  seq.append(i)
  i+=1
for _ in range(M):
    a,b = list(map(int, input().split()))
    l.append([a-1,b-1])
cnt = 0
for i in list(itertools.permutations(seq)):
  if i[0]!=0:
    continue
  for j in range(N-1):
    if sorted([i[j],i[j+1]]) in l:
      if j == N-2:
        cnt += 1
    else:
      break
print(cnt)

Submission status: Accepted

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


def dfs(now, visited):
    visited.append(now)
    if len(visited) == N:
        return 1

    ret = 0
    for edge in graph[now]:
        if edge in visited:
            continue
        ret += dfs(edge, visited[:])

    return ret


print(dfs(0, []))

Submission status: Accepted

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


def dfs(now, prev, visited):
    visited.append(now)
    if len(visited) == N:
        return 1

    ret = 0
    for edge in graph[now]:
        if edge == prev:
            continue
        if edge in visited:
            continue

        ret += dfs(edge, prev, visited[:])

    return ret


print(dfs(0, -1, []))

Submission status: Accepted

Solution code:
from collections import deque

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

stack = deque([0])
visited = [False]*n
visited[0] = True

def dfs(visited,stack):
    tmp = 0
    while stack:
        x = stack.pop()
        if all(visited):
            return 1
        for e in edge_li[x]:
            if visited[e]:
                continue
            visited[e]=True
            stack.append(e)
            tmp+=dfs(visited,stack)

            visited[e]=False
    return tmp

print(dfs(visited,stack))

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 p in permutations(range(1,n)):
    now = 0
    for nxt in p:
        if nxt not in G[now]: break
        now = nxt
    else:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
def root(lista, S, G, M, N, memory):
  if(S == G and memory == set(range(1, N+ 1))):
    return 1
  elif(S == G and memory != set(range(1, N+ 1))):
    return 0
  elif(lista == []):
    return 0
  else:
    roots = 0
    possibilities = 0
    possibleroots = []
    for i in range(M):
      if(S in lista[i]):
        q = list(filter(lambda x: x != S, lista[i])).pop()
        if(q in memory):
          continue
        else:
          possibleroots.append(q)
    if(possibleroots == []):
      return 0
    else:
      for q in possibleroots:
        newlista = list(filter(lambda x: x != {S, q}, lista))
        newmemory = memory| {q}
        
        roots+= root(newlista, q, G, M- 1, N, newmemory)
      return roots


N, M = map(int, input().split())
lista = []
for i in range(M):
  lista.append(set(map(int, input().split())))
  
ans = 0
for i in range(2, N+ 1):
  ans+= root(lista, 1, i, M, N, {1})
  
print(ans)

Submission status: Accepted

Solution code:
import itertools

N, M = map(int, input().split())
node_relationship = [set(map(int, input().split())) for _ in range(M)]
permutations_lis = list(itertools.permutations([x for x in range(1, N + 1)]))
ans = 0

for one_case in permutations_lis:
    if one_case[0] != 1:
        continue

    flg = True
    for i in range(len(one_case) - 1):
        if not flg:
            break
        tmp = {one_case[i], one_case[i + 1]}
        if not tmp in node_relationship:
            flg = False
    if flg:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
from itertools import permutations


def main():
    n, m = map(int, input().split())
    a = {tuple(int(i) - 1 for i in input().split()) for _ in range(m)}
    c = 0
    for per in permutations(range(1, n)):
        p = [0] + list(per)
        for i in range(n - 1):
            if (p[i], p[i + 1]) not in a and (p[i + 1], p[i]) not in a:
                break
        else:
            c += 1
    print(c)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import itertools

n, m = (int(x) for x in input().split())
li = []
for i in range(m):
    li.append([int(x) for x in input().split()])
#print(li)

paths = list(itertools.permutations([int(x) for x in range(1,n+1)]))

#print(paths)

ans = 0
for path in paths:
    if path[0] != 1:
        continue
    flag = True
    for i in range(n-1):
        if path[i] < path[i+1]:
            a = path[i]
            b = path[i+1]
        else:
            b = path[i]
            a = path[i+1]
        if [a,b] not in li:
            flag = False
            break
    if flag:
        ans += 1
print(ans)

Submission status: Accepted

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

import itertools
np = [i for i in range(1,n)]
p = list(itertools.permutations(np))
ans = 0
for pi in p:
  flag = True
  sta = 0
  for j in range(n-1):
    if pi[j] not in graph[sta]:
      flag = False
      break
    else:
      sta = pi[j]
  if flag: ans += 1

print(ans)

Submission status: Accepted

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

import itertools
np = [i for i in range(1,n)]
p = list(itertools.permutations(np))
ans = 0
for pi in p:
  flag = True
  sta = 0
  for j in range(n-1):
    if pi[j] not in graph[sta]:
      flag = False
      break
    else:
      sta = pi[j]
  if flag:
    ans += 1

print(ans)

Submission status: Accepted

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

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
#from math import gcd
import bisect
from collections import defaultdict
from collections import deque
from functools import lru_cache


#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')

#############
# Functions #
#############

######INPUT######
def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]

######OUTPUT######
def P(arg): print(arg); return
def Y(): print("Yes"); return
def N(): print("No"); return
def E(): exit()
def PE(arg): print(arg); exit()
def YE(): print("Yes"); exit()
def NE(): print("No"); exit()

#####Shorten#####
def DD(arg): return defaultdict(arg)


#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n):
    return kaijo_memo[n]
  if(len(kaijo_memo) == 0):
    kaijo_memo.append(1)
  while(len(kaijo_memo) <= n):
    kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n):
    return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0):
    gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n):
    gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if(n == r):
    return 1
  if(n < r or r < 0):
    return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1:
    arr.append([temp, 1])
  if arr==[]:
    arr.append([n, 1])
  return arr

#####MakeDivisors######
def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors

#####MakePrimes######
def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum

#####GCD#####
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#####BitCount#####
def count_bit(n):
  count = 0
  while n:
    n &= n -1
    count += 1
  return count

#####ChangeBase#####
def base_10_to_n(X, n):
  if X//n:
    return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

#####IntLog#####
def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count

#############
# Main Code #
#############

N,M = IL()
graph = [[] for i in range(N)]
for _ in range(M):
  a,b = IL()
  graph[a-1].append(b-1)
  graph[b-1].append(a-1)

import itertools
nums = [i+1 for i in range(N-1)]
count = 0
for route in itertools.permutations(nums):
  co = route[:]
  route = list(route)
  prev = 0
  while route:
    now = route.pop()
    if now not in graph[prev]:
      route = "NG"
      break
    prev = now
  if not route:
    count += 1
print(count)

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

import itertools

n, m = map(int, input().rstrip().split())
adjacency_matrix = [[0 for i in range(n)] for i in range(n)]

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

result = 0
# 全組み合わせを試す
for v in itertools.permutations(node):
    index = 0
    adj_mat2 = adjacency_matrix[:]
    past = 0
    for i in v:
        # 隣接行列右上を参照する
        # そのときa>bでadj_mat[a][b]
        a = min(past, i)
        b = max(past, i)


        if adj_mat2[a][b] != 1:
            break

        past = i
        index += 1
    if index == n-1:
        result += 1

print(result)