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.

Solution (Python):
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)

Solution (Python):
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)

Solution (Python):
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)

Solution (Python):
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))

Solution (Python):
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))

Solution (Python):
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)

Solution (Python):



from collections import Counter, deque, defaultdict
from copy import deepcopy





import sys

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)]

def OutH(lst, deli=' '): print(deli.join(map(str, lst)))
def OutV(lst): print('\n'.join(map(str, lst)))

sys.setrecursionlimit(10 ** 6)

int1 = lambda x: int(x) - 1

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], []]]) 

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)

Solution (Python):
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)

Solution (Python):
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()

Solution (Python):
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)

Solution (Python):
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)

Solution (Python):
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)

Solution (Python):
import bisect
import copy
import heapq
import sys
import itertools
import math
import queue
from functools import lru_cache
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
mod = 10 ** 9 + 7 

def read_values(): return map(int, input().split())
def read_index(): return map(lambda x: int(x) - 1, input().split())
def read_list(): return list(read_values())
def read_lists(N): return [read_list() for n in range(N)]


def main():
    N, M = read_values()
    L = [set() for _ in range(N)]
    for _ in range(M):
        a, b = read_index()
        L[a].add(b)
        L[b].add(a)

    res = 0
    for T in itertools.permutations(range(1, N)):
        pre = 0
        for t in T:
            if t not in L[pre]:
                break
            pre = t
        else:
            res += 1

    print(res)


if __name__ == "__main__":
    main()

Solution (Python):
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)

def dfs(n):
    global P
    seen[n] = 1
    for g in G[n]:
        if seen[g] == 0:
            dfs(g)
            seen[g] = 0
    if not 0 in seen:
        P += 1
P = 0
seen = [0] * N
dfs(0)
print(P)

Solution (Python):
from collections import defaultdict
from itertools import permutations

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

graph = defaultdict(list)

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

pattern = [x for x in permutations(range(1, n + 1)) if x[0] == 1]

ans = []
for p in pattern:
    tmp = []
    for i in range(n - 1):
        if p[i + 1] in graph[p[i]]:
            tmp.append(True)
        else:
            tmp.append(False)
    ans.append(all(tmp))

print(sum(ans))

Solution (Python):
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)

ans = 0


def main():
    def dfs(u, visited):
        visited[u] = True
        cnt = 0

        for v in edge[u]:
            if not visited[v]:
                cnt += dfs(v, visited)
                visited[v] = False

        if visited.count(True) == n:
            return 1

        return cnt

    from collections import defaultdict
    n, m = map(int, readline().split())
    edge = defaultdict(list)

    for i in range(m):
        a, b = map(int, readline().split())
        edge[a].append(b)
        edge[b].append(a)

    ans = dfs(1, [False] * (n + 1))
    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
import itertools
from collections import deque

n, m = map(int,input().split())
edge = [[] for _ in range(n)]
for _ in range(m):
    a,b = map(int,input().split())
    edge[a-1].append(b-1)
    edge[b-1].append(a-1)
    
ans = 0
for p in itertools.permutations([i+1 for i in range(n-1)]):
    pp = [0]+list(p)
    
    now = pp[0]
    for i in range(1,n):
        if pp[i] in edge[now]:
            now = pp[i]
        else:
            break
    else:
        ans += 1
    
print(ans)

Solution (Python):


from itertools import permutations

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

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



res = 0
for a in permutations(range(2,N+1),N-1):
    j = 1
    k = 0
    for i in a:
        if (j,i) in edges:
            k += 1
        if k == N-1:
            res += 1
        j = i

print(res)

Solution (Python):
import sys
import copy

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline

in_n = lambda: int(readline())
in_nn = lambda: map(int, readline().split())
in_nl = lambda: list(map(int, readline().split()))
in_na = lambda: map(int, read().split())
in_s = lambda: readline().rstrip().decode('utf-8')

sys.setrecursionlimit(1000000)


ans = 0


def bfs(N, edge, v, search):

    search |= {v}

    global ans
    if len(search) == N:
        ans += 1
        return

    for e in edge[v]:
        if e not in search:
            bfs(N, edge, e, copy.copy(search))


def main():

    N, M = in_nn()

    edge = [[] for _ in range(N)]

    for i in range(M):
        a, b = in_nn()
        a, b = a - 1, b - 1
        edge[a].append(b)
        edge[b].append(a)

    bfs(N, edge, 0, set())

    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
import sys
import copy

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline

in_n = lambda: int(readline())
in_nn = lambda: map(int, readline().split())
in_nl = lambda: list(map(int, readline().split()))
in_na = lambda: map(int, read().split())
in_s = lambda: readline().rstrip().decode('utf-8')

sys.setrecursionlimit(1000000)


ans = 0


def bfs(N, edge, v, search):

    search |= {v}

    global ans
    if len(search) == N:
        ans += 1
        return

    for e in edge[v]:
        if e not in search:
            
            bfs(N, edge, e, copy.copy(search))


def main():

    N, M = in_nn()

    edge = [[] for _ in range(N)]

    for i in range(M):
        a, b = in_nn()
        a, b = a - 1, b - 1
        edge[a].append(b)
        edge[b].append(a)

    bfs(N, edge, 0, set())

    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
from networkx import*
(n,_),*t=map(str.split,open(0))
n=int(n)
print(sum(n==len(p)for i in range(n)for p in all_simple_paths(Graph(t),'1',str(i+1))))

Solution (Python):
from networkx import*
(n,_),*t=[[*map(int,t.split())]for t in open(0)]
print(sum(n==len(p)for i in range(n)for p in all_simple_paths(Graph(t),1,i+1)))

Solution (Python):
from itertools import permutations as perm
n,m = map(int, input().split())
edges = [[] for i in range(n)]
for i in range(m):
    a,b = map(int, input().split())
    a -= 1
    b -= 1
    edges[a].append(b)
    edges[b].append(a)

def check(l, edge):
    for i in range(1,len(l)):
        u = l[i-1]
        v = l[i]
        if v not in edges[u]:
            return False
    return True

ans = 0
for l in perm([i for i in range(n)]):
    if l[0] != 0: continue
    if check(l,edges):
        ans += 1

print(ans)

Solution (Python):
import itertools
from sys import stdin
input = stdin.readline


def main():
  N, M = list(map(int, input().split()))
  map_ = [[0]*(N+1) for _ in range(N+1)]
  for i in range(M):
    a, b = list(map(int, input().split()))
    map_[a][b] = 1
    map_[b][a] = 1

  def is_one_stroke(path):
    now = 1
    for i in range(len(path)):
      next_ = path[i]
      if not map_[now][next_]:
        return False
      now = next_
    return True

  perms = itertools.permutations(list(range(2, N+1)))
  num_path = 0
  for path in perms:
    if (is_one_stroke(path)):
      num_path += 1
  print(num_path)


if(__name__ == '__main__'):
  main()

Solution (Python):
from itertools import permutations

n, m = map(int, input().split())
L = [set() for _ in range(n)]
for _ in range(m):
    a, b = map(int, input().split())
    L[a-1].add(b-1)
    L[b-1].add(a-1)
lst = [i for i in range(1, n)]
ans = 0
for v in permutations(lst, n-1):
    case = [0] + list(v)
    for i in range(n-1):
        next = case[i+1]
        if next not in L[case[i]]:
            break
    else:
        ans += 1
print(ans)

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

path = [[] for i in range(N)]

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

def dfs(now,depth):
	global cnt
	if depth == N: cnt+=1
	for new in path[now]:
		if vis[new] == 0:
			vis[new] = 1
			dfs(new,depth+1)
			vis[new] = 0

vis[0] = 1
dfs(0,1)
print(cnt)

Solution (Python):
import itertools as it

n,m=map(int,input().split())
path=[]
for i in range(m): path.append(list(map(int,input().split())))
ls=list(it.permutations(range(1,n+1)))
cnt=0
for l in ls:
    if l[0]!=1: break
    flag=1
    for i in range(n-1):
        if ([l[i],l[i+1]] not in path) and ([l[i+1],l[i]] not in path):
            flag=0
            break
    if flag: cnt+=1
print(cnt)

Solution (Python):
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)

count = 0

def dfs(i, now, done):
    global count
    if i == N-1:
        count += 1
        return

    for j in ab[now]:
        if j not in done:
            dfs(i+1, j, done + [j])
    return

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

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

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



c = list(itertools.permutations(range(1, n)))
len_c = len(c)


ans = 0
for i in range(len_c):
    now = 0
    check = True
    for j in range(n - 1):
        if not c[i][j] in a[now]:
            check = False
        now = c[i][j]
    if check:
        ans += 1

print(ans)

Solution (Python):
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)

Solution (Python):
import itertools
(n,_),*a= [[*map(int,i.split())] for i in open(0)]
p=[[1] + list(i) for i in itertools.permutations(range(2,n+1),n-1)]
c = 0
for i in p:
    for j in range(n-1):
        if sorted([i[j],i[j+1]]) not in a:
            break
    else:
        c+=1
print(c)

Solution (Python):
from itertools import accumulate, permutations, combinations, combinations_with_replacement, groupby, product









import sys
sys.setrecursionlimit(10 ** 5 + 10)


def input(): return sys.stdin.readline().strip()


def resolve():
    """
    https://qiita.com/drken/items/4a7869c5e304883f539b
    cf. https://atcoder.jp/contests/abc138/submissions/13273052
    """

    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)
    ans = 0

    for i in permutations(range(N)):
        flag = True
        if i[0] != 0:
            continue
        nn=0
        for j in range(N-1):
            if i[j+1] not in G[nn]:
                flag = False
            nn=i[j+1]
        if flag:
            ans += 1
    print(ans)


resolve()

Solution (Python):
import itertools

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)

lst = [i + 1 for i in range(n - 1)]
ans = 0
for step in itertools.permutations(lst):
    flag = True
    now = 0
    for i in range(n - 1):
        if step[i] in edge[now]:
            now = step[i]
        else:
            flag = False
            break
    if flag:
        ans += 1

print(ans)

Solution (Python):
n,m = map(int,input().split())
edge = []
for i in range(n+1):
    edge.append([])
for i in range(m):
    a,b = map(int,input().split())
    edge[a].append(b)
    edge[b].append(a)
ans = 0

import itertools
def permutation_all(seq, choice):
    return list(itertools.permutations(seq, choice))

cond = [i for i in range(2,n+1)]
cond = permutation_all(cond, n-1)
for i in range(len(cond)):
    here = 1
    tar = cond[i]
    flag = True
    for j in range(n-1):
        if tar[j] not in edge[here]:
            flag= False
            break
        else:
            here = tar[j]
    if flag:
        ans += 1
print(ans)

Solution (Python):
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)

Solution (Python):
n,m=map(int,input().split())
ab = []
for _ in range(m):
  a,b=map(int,input().split())
  a,b=a-1,b-1
  ab.append({a,b})
import itertools

cnt = 0
for v in itertools.permutations(range(1,n)):
  l = 0
  ok = True
  for v2 in v:
    if {l,v2} not in ab:
      ok = False
      break
    l = v2
  if ok:
    
    cnt += 1
  
print(cnt)

Solution (Python):
import sys
import collections
INF = 10**18
ans = 0

def dfs2(now,edge,l,cnt):
    global ans
    if len(l) == n:
        ans+=1
        return
    visited[now] = True
    for v in edge[now]:
        if visited[v] == False:
            l.append(v)
            dfs2(v,edge,l,cnt)
            l.pop()
            visited[v] = False

if __name__ == "__main__":
    n,m = map(int,input().split())
    edge =[[] for i in range(n)]
    for i in range(m):
        a,b = map(int,input().split())
        a-=1
        b-=1
        edge[a].append(b)
        edge[b].append(a)
    l = [0]
    visited = [False]*(n)
    dfs2(0,edge,l,0)
    print(ans)

Solution (Python):
from itertools import permutations

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

ans = 0
for p in permutations(range(1, N)):
    v = 0
    flag = True
    for nv in p:
        if nv not in G[v]:
            flag = False
            break
        v = nv
    if flag:
        ans += 1

print(ans)

Solution (Python):
from itertools import permutations
def main():
    N, M = map(int, input().split())
    l = [[0] * N for _ in range(N)]
    for _ in range(M):
        a, b = map(int, input().split())
        a -= 1
        b -= 1
        l[a][b] = 1
        l[b][a] = 1
    r = 0
    for x in permutations(range(1, N)):
        if l[0][x[0]] == 0:
            continue
        for i in range(N-2):
            if l[x[i]][x[i+1]] == 0:
                break
        else:
            r += 1
    return r
print(main())

Solution (Python):
import sys
sys.setrecursionlimit(10**9)

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

visited = [False] * (n+1)
visited[0] = True
visited[1] = True
cnt = 0

def dfs(list):
    global cnt
    if not False in visited:
        cnt += 1
        return
    for i in list:
        if visited[i] == False:
            visited[i] = True
            dfs(g[i])
            visited[i] = False

dfs(g[1])
print(cnt)

Solution (Python):
from itertools import permutations

def main():
    N, M = map(int, input().split())
    G = [set() for _ in range(N)]
    for _ in range(M):
        a, b = map(int, input().split())
        G[a - 1].add(b - 1)
        G[b - 1].add(a - 1)
    r = 0
    for p in permutations(range(1, N)):
        f = 0
        for i in p:
            if i not in G[f]:
                break
            f = i
        else:
            r += 1
    return r

print(main())

Solution (Python):
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)

Solution (Python):
def ser(visited,now):
  visited.append(now)
  if len(visited)==n:
    return 1
  cnt=0
  for i in bri[now]:
    if i not in visited:
      cnt+= ser(visited[:],i)
  return cnt

n,m=map(int,input().split())
bri=[[] for _ in range(n)]
for i in range(m):
  a,b=map(int,input().split())
  bri[a-1].append(b-1)
  bri[b-1].append(a-1)
print(ser([],0))

Solution (Python):
import copy
import sys
sys.setrecursionlimit(10**7)
N, M = map(int, input().split())
edges = [[] for _ in range(N)]
for _ in range(M):
    a, b = map(int, input().split())
    edges[a - 1].append(b - 1)
    edges[b - 1].append(a - 1)
ans = 0
def dfs(start,path):
    next_path = copy.copy(path)
    global ans
    next_path.append(start)
    if len(next_path) == N:
        ans += 1
        return
    for i in edges[start]:
        if i not in next_path:
            dfs(i,next_path)
dfs(0,[])
print(ans)

Solution (Python):
from itertools import permutations


def main():
    n, m = map(int, input().split())

    path = [[False for _ in range(n)] for _ 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

    res = 0
    perms = list(permutations(list(range(1, n)), n - 1))
    for p in perms:
        visited = 1
        prev = 0
        for now in p:
            if path[prev][now]:
                visited += 1
                prev = now
            else:
                break
        if visited == n:
            res += 1

    print(res)


if __name__ == '__main__':
    main()

Solution (Python):
from itertools import permutations
n , m = map(int,input().split())
route = [set() for i in range(n+1)]
for i in range(m):
    a , b = map(int,input().split())
    route[a].add(b)
    route[b].add(a)
ans = 0
p=[i + 2 for i in range(n-1)]
kouho = list(permutations(p))

for i in range(len(kouho)):
    now = 1
    flag = True
    for j in kouho[i]:
        if j in route[now]:
            now = j
        else:
            flag = False
            break
    if flag:
        ans += 1
print(ans)

Solution (Python):
from collections import deque

def solve():
    ret = 0
    stack = deque()
    stack.append([1, {1}])
    while stack:
        node, used = stack.popleft()
        if len(used) == N:
            ret += 1
            continue

        for n in neighbors[node]:
            if n in used:
                continue
            stack.append([n, used | {n}])

    print(ret)

if __name__ == "__main__":
    N, M = map(int, input().split())
    neighbors = [[] for _ in range(N + 1)]
    for _ in range(M):
        a, b = map(int, input().split())
        neighbors[a].append(b)
        neighbors[b].append(a)
    solve()

Solution (Python):

from itertools import permutations
n, m = map(int, input().split())
G = [[] for _ in [0] * -~n]
for _ in [0] * m:
    a, b = map(int, input().split())
    G[a] += b,
    G[b] += a,
ans = 0
for i in permutations(range(2, n + 1), n - 1):
    i = (1,) + i
    if all(i[j] in G[i[j + 1]] for j in range(n - 1)):
        ans += 1
print(ans)

Solution (Python):
from copy import deepcopy
n, m, *AB = map(int, open(0).read().split())
graph = [[] for _ in range(n)]
for a, b in zip(AB[::2], AB[1::2]):
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)

complete_paths = []
stack = [0]
paths = [[]]
c = 0
while stack:
    current_node = stack.pop()
    path = paths.pop()
    path.append(current_node)
    next_nodes = [n for n in graph[current_node] if n not in path]
    if next_nodes:
        for next_node in next_nodes:
            stack.append(next_node)
            paths.append(deepcopy(path))
    else:
        if len(path) == n:
            complete_paths.append(path)
print(len(complete_paths))

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

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

counter = 0
def dfs(pointer, already_visited):
    global counter
    if len(already_visited) == n - 1:
        counter += 1
    for el in graph[pointer]:
        if el in already_visited:
            continue
        dfs(el, already_visited + [pointer])

dfs(1, [])
print(counter)

Solution (Python):
import math
import sys
from collections import deque
import copy
import itertools
from itertools import permutations
def mi() : return map(int,input().split())
def i() : return int(input())
a,b=mi()
ans=0
l=[[] for _ in range(a)]
for i in range(b):
  u,v=mi()
  l[u-1].append(v-1)
  l[v-1].append(u-1)
S=[]
for i in range(1,a):
  S.append(i)
lst=list(permutations(S))
for i in lst:
  x=0
  t=True
  for w in range(len(i)):
    if not i[w] in l[x]:
      t=False
      break
    x=i[w]
  if t:
    ans+=1
print(ans)

Solution (Python):
from itertools import permutations

def readinput():
    n,m=list(map(int,input().split()))
    nList=[]
    for _ in range(n+1):
        nList.append([])
    for _ in range(m):
        a,b=list(map(int,input().split()))
        nList[a].append(b)
        nList[b].append(a)
    
    return n,m,nList

def main(n,m,nList):
    permlist = permutations(range(2,n+1))
    count=0
    for perm in permlist:
        current=1
        for i in range(n-1):
            next=perm[i]
            if not next in nList[current]:
                break
            current=next
        else:
            count+=1
    return count

if __name__=='__main__':
    n,m,nList=readinput()
    ans=main(n,m,nList)
    print(ans)

Solution (Python):
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)

Solution (Python):
import sys 
from copy import deepcopy
from collections import deque
sys.setrecursionlimit(10**6)
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))

def solve(table,ava,now):
    if not 1 in ava:
        global ans
        ans += 1
        return
    global N
    for i in range(N):
        if table[now][i] and ava[i]:
            bt,ba = deepcopy(table),deepcopy(ava)
            bt[now][i] = bt[i][now] = ba[i] = 0
            solve(bt,ba,i)
    return

if __name__=='__main__':
    tmp = deque(LI())
    N,M = tmp.popleft(),tmp.popleft()
    table = [[0]*N for _ in range(N)]
    for i in range(M):
        tmp = deque(LI())
        a,b = tmp.popleft()-1,tmp.popleft()-1
        table[a][b] = table[b][a] = 1
    ans = 0
    ava = [1]*N
    ava[0] = 0
    solve(table,ava,0)
    print(ans)

Solution (Python):
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(node, seen):
    if len(seen)==n-1:
        return 1
    tmp = 0
    for i in graph[node]:
        if i in seen:
            continue
        tmp += DFS(i, seen|{node})
    return tmp
print(DFS(0, set()))