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):
n, m = map(int, input().split())
L = [[] for i in range(n)]

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

ans = 0

def f(t, history):
    his = history[:]
    his[t] += 1
    global ans
    if sum(his)==n:
        ans += 1
    else:
        for i in L[t]:
            if his[i]==0:
                f(i, his)

f(0, [0]*n)
print(ans)

Solution (Python):

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

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

ans = 0
def f(t, history):
    his = history[:]
    his[t] += 1
    global ans
    if sum(his) == n:
        ans += 1
    else:
        for i in L[t]:
            if his[i] == 0:
                f(i, his)
            
f(0, [0]*n)
print(ans)

Solution (Python):
import sys
import heapq
import re
from itertools import permutations
from bisect import bisect_left, bisect_right
from collections import Counter, deque
from fractions import gcd
from math import factorial, sqrt, ceil
from functools import lru_cache, reduce
INF = 1 << 60
MOD = 1000000007
sys.setrecursionlimit(10 ** 7)


class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

def is_prime(n):
    if n == 1:
        return False
    for i in range(2,int(n**0.5)+1):
        if n % i == 0:
            return False
    return True




def warshall_floyd(d, n):
    
    for k in range(n):
        for i in range(n):
            for j in range(n):
                d[i][j] = min(d[i][j],d[i][k] + d[k][j])
    return d



def dijkstra_heap(s, edge, n):
    
    d = [10**20] * n
    used = [True] * n 
    d[s] = 0
    used[s] = False
    edgelist = []
    for a,b in edge[s]:
        heapq.heappush(edgelist,a*(10**6)+b)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        
        if not used[minedge%(10**6)]:
            continue
        v = minedge%(10**6)
        d[v] = minedge//(10**6)
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,(e[0]+d[v])*(10**6)+e[1])
    return d


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


def lcm(x, y):
    return (x * y) // gcd(x, y)


def lcm_list(numbers):
    return reduce(lcm, numbers, 1)


def gcd_list(numbers):
    return reduce(gcd, numbers)






def eratosthenes(limit):
    A = [i for i in range(2, limit+1)]
    P = []

    while True:
        prime = min(A)
        
        if prime > sqrt(limit):
            break
            
        P.append(prime)
            
        i = 0
        while i < len(A):
            if A[i] % prime == 0:
                A.pop(i)
                continue
            i += 1
            
    for a in A:
        P.append(a)
            
    return P


def permutation_with_duplicates(L):

    if L == []:
        return [[]]

    else:
        ret = []

        
        S = sorted(set(L))

        for i in S:

            data = L[:]
            data.remove(i)

            for j in permutation_with_duplicates(data):
                ret.append([i] + j)

        return ret



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

queue = deque([])
queue.append([0, []])
ans = 0
while queue:
    x = queue.popleft()
    now = x[0]
    visited = x[1]
    if len(visited) == n - 1:
        ans += 1
        continue
    for i in d[now]:
        if i not in visited:
            queue.append([i, visited + [now]])
print(ans)

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

edge=[[] for i in range(n)]

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

ans=0
def search(his,nxt):
    global ans
    newhis=his.copy()
    newhis.append(nxt)
    if len(newhis)==n:
        ans+=1
        return
    for i in edge[nxt]:
        if i in newhis:continue
        search(newhis,i)




search([],0)

print(ans)

Solution (Python):
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()

from collections import defaultdict, deque, Counter
from sys import exit
import heapq
import math
import fractions
import copy
from itertools import permutations
from operator import mul
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7

N, M = getNM()
dist = [[] for i in range(N + 1)]
for i in range(M):
    a, b = getNM()
    dist[a - 1].append(b - 1)
    dist[b - 1].append(a - 1)

cnt = 0

pos = deque([[1 << 0, 0]])

while len(pos) > 0:
    s, v = pos.popleft()
    if s == (1 << N) - 1:
        cnt += 1
    for u in dist[v]:
        if s & (1 << u):
            continue
        pos.append([s | (1 << u), u])
print(cnt)

Solution (Python):
from itertools import permutations

N, M = map(int, input().split())
matrix = [[0] * N for i in range(N)]
ans = 0

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

for p in list(permutations(range(N))):
    if p[0] != 0:
        continue
    else:
        check = 1
        for i in range(N - 1):
            check *= matrix[p[i]][p[i+1]]
        ans += check

print(ans)

Solution (Python):
N,M=list(map(int,input().split()))
color=["white"]*(N+1)
relation_list=[[] for i in range(N+1)]
count=[0]
for i in range(M):
    a,b=list(map(int,input().split()))
    relation_list[a].append(b)
    relation_list[b].append(a)

def dfs(i,j,cnt,kako):
    keiro=kako[:]
    cnt += 1
    for k in relation_list[i]:
        if k not in keiro:
            keiro.append(k)
            dfs(k,i,cnt,keiro)
            del keiro[-1]
    if cnt==N:
        count[0]+=1
dfs(1,1,0,[1])
print(count[0])

Solution (Python):


import numpy as np
n,m = map(int,input().rstrip().split())
connection_list = [[] for _ in range(n)]
for _ in range(m):
    a,b = map(int,input().rstrip().split())
    connection_list[a-1].append(b-1)
    connection_list[b-1].append(a-1)

count = 0
def dfs(g,p,checked):
    global count
    checked[p] = 1
    if checked.all():
        count += 1
        return
    for next in g[p]:
        if checked[next] == 1:
            continue
        dfs(g,next,checked.copy())

checked = np.zeros(n,int)
dfs(connection_list,0,checked)
print(count)

Solution (Python):
from itertools import permutations
n,m=map(int,input().split())
s=[set(map(int,input().split())) for _ in range(m)]

ans=0
x=[i for i in range(2,n+1)]
cand=permutations(x)
for i in cand:
  crnt=1
  for nxt in i:
    if set([crnt,nxt]) in s:
      crnt=nxt
    else:
      break
  else:
    ans+=1
print(ans)

Solution (Python):





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

    from itertools import permutations
    L = list(permutations(range(N)))
    ret = 0
    for l in L:
        fg = 1
        if l[0]!=0:
            continue
        for k in range(N-1):
            if not l[k+1] in graph[l[k]]:
                fg = 0
                break
        if fg == 1:
            ret += fg
    print(ret)

if __name__ == '__main__':
    main()

Solution (Python):
from itertools import permutations

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

edge = [[0 for i in range(N)] for j 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

ans = 0
for path in permutations(range(N)):
    flag = True
    if path[0] != 0:
        flag = False
    for i in range(N-1):
        if not edge[path[i+1]][path[i]]:
            flag = False
    
    ans += int(flag)

print(ans)

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

N, M = map(int, input().split())
ab = [list(map(int, input().split())) for n in range(M)]
branch = [[False]* N for n in range(N)]

for m in range(M):
  a = ab[m][0] - 1
  b = ab[m][1] -1 
  branch[a][b] = True
  branch[b][a] = True

ans = 0
pattern = itertools.permutations(range(1, N+1),N)
for l in pattern:
  if l[0] != 1:
    continue
  for n in range(N):
    if n == N - 1:
      ans += 1
      break
    p = l[n] -1
    np = l[n+1] -1
    if not(branch[p][np]):
      break

print(ans)

Solution (Python):
N, M = map(int, input().split())
R = [[] for i in range(N)]
for i in range(M):
    a, b = map(int, input().split())
    R[a - 1].append(b - 1)
    R[b - 1].append(a - 1)
Parents = [[] for i in range(N)]
C = 0

def func(x, c):
    global C
    c += 1
    last = True
    for r in R[x]:
        if r in Parents[x]:
            continue
        for i in range(len(Parents[x])):
            Parents[r].append(Parents[x][i])
        Parents[r].append(x)
        last = False
        func(r, c)
        for i in range(len(Parents[x])):
            Parents[r].remove(Parents[x][i])
        Parents[r].remove(x)
    if last:
        if c == N:
            C += 1

func(0, 0)
print(C)

Solution (Python):


import sys






















from itertools import product, permutations  







def main():
    mod = 1000000007                
    inf = float('inf')              
    
    sys.setrecursionlimit(10**6)    
    def input(): return sys.stdin.readline().rstrip()
    def ii():    return int(input())
    def mi():    return map(int, input().split())
    def mi_0():  return map(lambda x: int(x)-1, input().split())
    def lmi():   return list(map(int, input().split()))
    def lmi_0(): return list(map(lambda x: int(x)-1, input().split()))
    def li():    return list(input())
    
    def check(path, adj):
        n = len(path)
        for i in range(n-1):
            if not adj[path[i]][path[i+1]]:
                return False
        return True

    
    n, m = mi()
    adj = [[False]*n for _ in range(n)]
    for _ in range(m):
        a, b = mi_0()
        adj[a][b] = True
        adj[b][a] = True
    
    cnt = 0
    for pattern in permutations(range(1, n)):
        if check([0]+list(pattern), adj):
            cnt += 1
    print(cnt)



if __name__ == "__main__":
    main()

Solution (Python):
N, M = map(int, input().split())
A = [0]*M
B = [0]*M
for i in range(M):
    A[i], B[i] = map(int, input().split())

from itertools import permutations

def make_aja_mtx(N, M, A, B):
    D = [[0 for _ in range(N)] for _ in range(N)]
    for i in range(M):
        D[A[i]-1][B[i]-1] = 1
        D[B[i]-1][A[i]-1] = 1
    return D

def check(p, N, D):
    len_path = 1
    for i in range(1, N):
        if D[p[i-1]-1][p[i]-1] == 1:
            len_path += 1
        else:
            break
    return len_path == N
        
def perm(perm_2):
    for p in perm_2:
        yield (1,) + p

def Main(N, M, A, B):
    ns = range(2, N+1)
    perm_2 = permutations(ns, N-1)
    ans = 0
    D = make_aja_mtx(N, M, A, B)
    for p in perm(perm_2):
        if check(p, N, D):
            ans += 1
    return ans
    
print(Main(N, M, A, B))

Solution (Python):
import sys, re
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2
from collections import deque, defaultdict, Counter
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop, heapify
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, M = MAP()
ab = [LIST() for _ in range(M)]


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

for a, b in ab:
	graph[a-1].append(b-1)
	graph[b-1].append(a-1)


ans = 0

for x in permutations(range(1, N)):
	tmp = 0
	for i in range(N-1):
		if x[i] in graph[tmp]:
			tmp = x[i]
		else:
			break
	else:
		ans += 1

print(ans)

Solution (Python):
import sys, re
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2
from collections import deque, defaultdict, Counter
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop, heapify
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, M = MAP()
ab = [LIST() for _ in range(M)]


graph = [[0]*N for _ in range(N)]

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

ans = 0
for x in permutations(range(1, N)):
	x = list(x)
	x.insert(0, 0)
	
	for i in range(N-1):
		if graph[x[i]][x[i+1]] != 1:
			break
	else:
		ans += 1

print(ans)

Solution (Python):
import sys, re
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2
from collections import deque, defaultdict, Counter
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop, heapify
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, M = MAP()
ab = [LIST() for _ in range(M)]


contact = [[0]*N for _ in range(N)]

for a, b in ab:
	contact[a-1][b-1] = 1
	contact[b-1][a-1] = 1

A = list(x for x in range(1, N))
ans = 0

for X in permutations(A, N-1):
	
	tmp = 0
	for y in X:
		if contact[tmp][y] == 1:
			tmp = y
		else:
			break
	else:
		
		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 sys, re
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2
from collections import deque, defaultdict, Counter
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop, heapify
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, M = MAP()

graph = defaultdict(list)
for _ in range(M):
	a, b = MAP()
	graph[a-1].append(b-1)
	graph[b-1].append(a-1)



ans = 0
A = list(range(1, N))

for x in permutations(A, N-1):
	
	y = [0]
	tmp = graph[0]
	for i in range(N-1):
		if x[i] in tmp and not x[i] in y:
			y.append(x[i])
			tmp = graph[x[i]]
		else:
			break
	else:
		ans += 1
		

print(ans)

Solution (Python):
import itertools

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

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

t = [num for num in range(1, n+1)]
ans = 0
for per in itertools.permutations(t):
  if per[0] != 1:
    continue
  for i in range(n-1):
    start = per[i]
    end = per[i+1]
    if not end in g[start]:
      break
  else:
    ans += 1
print(ans)

Solution (Python):
n,m=map(int,input().split())
e=[[0 for _ in range(n)] for i in range(n)]
for i in range(m):
    a,s=map(int,input().split())
    e[a-1][s-1]=1;e[s-1][a-1]=1
ans=0
from itertools import permutations as pe
for i in pe(range(1,n),r=None):
    
    pre=0
    for a in i:
        if e[pre][a]!=1:break
        pre=a
    else:ans+=1
print(ans)

Solution (Python):
import sys
from collections import deque, Counter, defaultdict
from itertools import permutations
import heapq


def resolve():
    N, M = map(int, sys.stdin.readline().strip().split())
    adj_mat = [[False] * N for _ in range(N)]
    for _ in range(M):
        a, b = tuple(map(int, sys.stdin.readline().strip().split()))
        adj_mat[a-1][b-1] = True
        adj_mat[b-1][a-1] = True
    ans = 0
    for perm in permutations(range(N)):
        if perm[0] != 0:
            break
        cur = 0
        while cur < N - 1:
            if not adj_mat[perm[cur]][perm[cur+1]]:
                break
            cur += 1
        else:
            ans += 1

    print(ans)


if __name__ == "__main__":
    resolve()

Solution (Python):
import itertools

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

sides = []

for _ in range(M):
    temp_a, temp_b = map(int, input().split())
    sides.append(set([temp_a, temp_b]))




counter = 0
for i in itertools.permutations(range(1, N+1)):
    if i[0] != 1:
        continue

    for j in range(0,N-1):
        if set([i[j],i[j+1]]) in sides:
            continue
        else:
            break
    else:
        counter += 1
        continue
    


print(counter)

Solution (Python):
import sys
import math
import numpy as np
from collections import Counter, defaultdict, deque
import itertools

input = sys.stdin.readline
sys.setrecursionlimit(10 ** 6)


def S():
    return input().rstrip()


def I():
    return int(input())


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


inf = float("inf")
mod = 10 ** 9 + 7

n, m = MI()
d = defaultdict(set)
for _ in range(m):
    a, b = MI()
    d[a].add(b)
    d[b].add(a)

li = list(range(2, n + 1))

ans = 0
for l in itertools.permutations(li):
    now = 1
    for i, next in enumerate(l):
        if next in d[now]:
            now = next
            if i == n - 2:
                ans += 1
        else:
            break

print(ans)

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

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

visited = [0]*N
visited[0] = 1

def dfs(v, visited):
    if 0 not in visited:
        return 1

    ans = 0
    for i in G[v]:
        if visited[i] == 0:
            visited[i] = 1
            ans += dfs(i, visited)
            visited[i] = 0

    return ans

print(dfs(0, visited))

Solution (Python):
import copy
n,m=map(int,input().split())
g=[set([]) for _ in range(n+1)]
for i in range(m):
    a,b=map(int,input().split())
    g[a].add(b)
    g[b].add(a)

ans=0
def dfs(v,used):
    usedi=copy.deepcopy(used)
    usedi[v]=True

    nexti=g[v]
    for i in nexti:
        if(usedi[i]):
            continue
        else:
            dfs(i,usedi)

    if(usedi[1:].count(True) == n):
        global ans
        ans+=1

dfs(1,[False for _ in range(n+1)])
print(ans)

Solution (Python):
import copy
A = list()
n, m = map(int, input().split())
for i in range(m):
    a = list(map(int, input().split()))
    A.append(a)
    A.append([a[1], a[0]])

B = list()

def update(current=[1], rest=A, count = 0):
    next = list(filter(lambda x: x[0] == current[count], rest))
    if len(current) < n:
        for ne in next:
            l = copy.deepcopy(current)
            l.append(ne[1])
            nRest = list(filter(lambda x: x[0] != current[count] and x[1] != current[count] and x[1] != ne[1], rest))
            update(l, nRest, count + 1)
    else:
        B.append(current)

update()
print(len(B))

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

N, M = map(int, input().split(' '))
graph = defaultdict(set)
for _ in range(M):
    a, b = map(int, input().split(' '))
    graph[a].add(b)
    graph[b].add(a)

count = 0
for path in permutations(range(2, N + 1)):
    if path[0] not in graph[1]:
        continue

    for n1, n2 in zip(path, path[1:]):
        if n2 not in graph[n1]:
            break
    else:
        count += 1

print(count)

Solution (Python):
import sys
sys.setrecursionlimit(10 ** 9)
def dfs(i, j):
    global cnt, vis
    if len(set(vis)) == 1:
        cnt += 1
        return None
    for k in l[j]:
        if not vis[k] == 1:
            vis[k] = 1
            dfs(i + 1, k)
            vis[k] = 0
n, m = map(int, input().split())
l = [[] for i in range(n)]
vis = [0] * n
vis[0] = 1
cnt = 0
for i in range(m):
    a, b = map(int, input().split())
    l[a - 1].append(b - 1)
    l[b - 1].append(a - 1)
dfs(0, 0)
print(cnt)

Solution (Python):
import itertools
import numpy as np

N, M = map(int, input().split())
X = [[] for _ in range(M)]
for i in range(M):
    X[i] = list(map(int, input().split()))
permutations_list = list(itertools.permutations([i for i in range(N-1)]))

count = 0
for i in range(len(permutations_list)):
    x = np.argsort(permutations_list[i])
    if [1, x[0]+2] not in X and [x[0]+2, 1] not in X:
        count += 1
        continue
    for j in range(N-2):
        pair = [x[j]+2, x[j+1]+2]
        reverse = list(reversed(pair))
        if pair not in X and reverse not in X:
            count += 1
            break
print(len(permutations_list) -count)

Solution (Python):
import itertools

N, M = map(int, input().split())
array = [" -> ".join(input().split()) for _ in range(M)]

permutation_list = itertools.permutations([x + 1 for x in range(N)])

count = 0
flg = True
for data in permutation_list:
    
    if data[0] != 1:
        continue
    for i in range(1, len(data)):
        param = "{} -> {}".format(data[i - 1], data[i])
        param2 = "{} -> {}".format(data[i], data[i - 1])
        if array.count(param) > 0 or array.count(param2) > 0:
            pass
            
        else:
            
            flg = False
            break
    if flg is False:
        flg = True
        continue
    
    count += 1

print(count)

Solution (Python):
import itertools
import math

n, m = [int(i) for i in input().split()]
town = [[0 for _ in range(n+1)] for _ in range(n+1)]

for i in range(m):
    a, b = [int(i) for i in input().split()]
    town[a][b] = 1
    town[b][a] = 1

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

count = 0
for one_case in permutations_lis:
    if (one_case[0] == 1):
        flag = 1
    else:
        flag = 0

    for i in range(n-1):
        if(town[one_case[i]][one_case[i+1]] == 0):
            flag = 0
    if(flag == 1):
        count += 1

print(count)

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



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

ans = 0
visited = [0] * N

def dfs(now=0):
    global visited, ans
    visited[now] = 1
    if all(visited):
        ans += 1
        
    else:
        cand = nei_L[now]
        for c in cand:
            if not visited[c]:
                dfs(c)
    visited[now] = 0

dfs()
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())
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)

from collections import deque

d = deque([[0]]) 
from copy import copy
ans = 0
while len(d):
    vs = d.popleft()
    for w in edge[vs[-1]]:
        if w not in vs:
            vs_copy = copy(vs)
            vs_copy.append(w)
            if len(vs_copy)==N:
                ans += 1
            else:
                d.append(vs_copy)
print(ans)

Solution (Python):
from itertools import permutations

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

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

cnt = 0
for each in permutations(range(N)):
    if each[0] != 0:
        break

    factor = 1
    for i in range(N-1):
        factor *= path_matrix[each[i]][each[i+1]]
    cnt += factor

print(cnt)

Solution (Python):
from collections import deque

def main():
    ans = 0
    N, M = map(int, input().split())
    graph = [[] for _ in range(N)]
    for _ in range(M):
        ai, bi = map(int, input().split())
        for j in range(1, N+1):
            if ai == j:
                graph[j-1].append(bi)
            elif bi == j:
                graph[j-1].append(ai)
        
    q = deque()
    q.append([1, {_ for _ in range(2, N+1)}])

    while q:
        prev, exist = q.popleft()

        if not exist:
            ans += 1
        for next in exist:
            if next in graph[prev-1]:
                q.append([next, exist-{next}])

    print(ans)

if __name__ == "__main__":
    main()

Solution (Python):
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    sys.setrecursionlimit(10**7)
    INF = 10**18
    MOD = 10**9 + 7
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())

    N,M = LI()
    root = [[] for _ in range(N)]
    for _ in range(M):
        a,b = LI()
        root[a-1].append(b-1)
        root[b-1].append(a-1)
    node = [0] * N

    ans = 0
    q = []
    q.append((0,1))

    while q:
        u,d = q.pop()
        if d < 0:
            node[u] = 0
        else:
            node[u] = d
            q.append((u,-1))
            for v in root[u]:
                if node[v]: continue
                if d+1 == N: ans += 1
                else:
                    q.append((v,d+1))

    print(ans)

if __name__ == '__main__':
    main()

Solution (Python):
N, M = list(map(int,input().split()))
graph = [[-1 for i in range(N)] for i in range(N)]
for i in range(M):
    a, b = list(map(int,input().split()))
    graph[a - 1][b - 1] = 1
    graph[b - 1][a - 1] = 1
    
def dfs(node, depth):
    global visited
    global ans
    if depth == N - 1:
        if sum(visited) == N:
            ans += 1
        return
    for i in range(1, N):
        if graph[node][i] == 1 and visited[i] == -1:
            visited[i] = 1
            dfs(i, depth + 1)
            visited[i] = -1
            
visited = [-1 for i in range(N)]
visited[0] = 1

ans = 0
dfs(0, 0)

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)