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):
import itertools

n, m = map(int, input().split())
graph = {i + 1 : set() for i in range(n)}
for i in range(m):
    a, b = map(int, input().split())
    graph[a] |= set([b])
    graph[b] |= set([a])
count = 0
node = [i + 2 for i in range(n - 1)]
for i in itertools.permutations(node):
    route = [1] + list(i)
    flag = True
    for j in range(n - 1):
        if route[j + 1] not in graph[route[j]]:
            flag = False
            break
    if flag == True:
        count += 1
print(count)

Solution (Python):
import sys
import copy

sys.setrecursionlimit(1000)
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def LIST(): return [int(x) for x in input().split()]
MOD = 10**9 + 7

N, M = LIST()

A = [[0]*(N+1) for _ in range(N+1)]

for _ in range(M):
    a, b = LIST()
    A[a][b] = A[b][a] = 1



def check(current, tovisit):
    if tovisit == []:
        return 1
    
    count = 0

    for i in tovisit:
        if A[current][i] == 1:
            tmp = copy.deepcopy(tovisit)
            tmp.remove(i)
            count += check(i, tmp)

    return count

print(check(1, list(range(2, N+1))))

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

C=[[] for i in range(nn)]
C.insert(0,"niku")

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

ans=0    

def tansa(n,path,app):
    new_path=path[:]
    new_path.append(app)
    
    if len(new_path)==nn:
        global ans
        ans+=1
        return 1

    for num in C[n]:
        if not num in new_path:
            tansa(num,new_path,num)

            
tansa(1,[],1)

print(ans)

Solution (Python):

from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
import itertools
sys.setrecursionlimit(10**5)
stdin = sys.stdin
bisect_left = bisect.bisect_left
bisect_right = bisect.bisect_right
def LI(): return list(map(int, stdin.readline().split()))
def LF(): return list(map(float, stdin.readline().split()))
def LI_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def II(): return int(stdin.readline())
def IF(): return float(stdin.readline())
def LS(): return list(map(list, stdin.readline().split()))
def S(): return list(stdin.readline().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')


def A():
    a, b = LI()
    a -= 2
    b -= 2
    a %= 13
    b %= 13
    if a > b:
        print("Alice")
    elif a < b:
        print("Bob")
    else:
        print("Draw")
    return


def B():
    n, m = LI()
    a = SR(n)
    b = SR(m)
    if a == b:
        print("Yes")
        return
    for y in range(n - m):
        for x in range(n - m):
            if a[y][x] == b[0][0]:
                flg = 0
                for yi in range(m):
                    for xi in range(m):
                        if b[yi][xi] == a[y + yi][x + xi]:
                            continue
                        flg = 1
                        break
                    if flg:
                        break
                if flg:
                    continue
                print("Yes")
                return
    print("No")
    return


def C():
    n, m = LI()
    edg = [[] for i in range(n)]
    for _ in range(m):
        a, b = LI_()
        edg[a].append(b)
        edg[b].append(a)
    def dfs(i, c):
        res = 0
        c[i] = False
        if not (True in c):
            c[i] = True
            return 1
        for e in edg[i]:
            if c[e]:
                res += dfs(e, c)
        c[i] = True
        return res
    print(dfs(0, [True] * n))
    return


def D():
    return


if __name__ == '__main__':
    C()

Solution (Python):

from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
import itertools
sys.setrecursionlimit(10**5)
stdin = sys.stdin
bisect_left = bisect.bisect_left
bisect_right = bisect.bisect_right
def LI(): return list(map(int, stdin.readline().split()))
def LF(): return list(map(float, stdin.readline().split()))
def LI_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def II(): return int(stdin.readline())
def IF(): return float(stdin.readline())
def LS(): return list(map(list, stdin.readline().split()))
def S(): return list(stdin.readline().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')


def A():
    a, b = LI()
    a -= 2
    b -= 2
    a %= 13
    b %= 13
    if a > b:
        print("Alice")
    elif a < b:
        print("Bob")
    else:
        print("Draw")
    return


def B():
    n, m = LI()
    a = SR(n)
    b = SR(m)
    if a == b:
        print("Yes")
        return
    for y in range(n - m):
        for x in range(n - m):
            if a[y][x] == b[0][0]:
                flg = 0
                for yi in range(m):
                    for xi in range(m):
                        if b[yi][xi] == a[y + yi][x + xi]:
                            continue
                        flg = 1
                        break
                    if flg:
                        break
                if flg:
                    continue
                print("Yes")
                return
    print("No")
    return


def C():
    n, m = LI()
    edg = [[] for i in range(n)]
    for _ in range(m):
        a, b = LI_()
        edg[a].append(b)
        edg[b].append(a)
    def dfs(i, c):
        res = 0
        c[i] = False
        if not (True in c):
            return 1
        for e in edg[i]:
            if c[e]:
                c[e] = False
                res += dfs(e, c)
                c[e] = True
        return res
    print(dfs(0, [True] * n))
    return


def D():
    return


if __name__ == '__main__':
    C()

Solution (Python):
N, M = map(int, input().split())
grp = []
for i in range(0, N):
	grp.append([])
for i in range(0, M):
	A, B = map(lambda v: int(v)-1, input().split())
	grp[A].append(B)
	grp[B].append(A)
memo = []
for i in range(0, N):
	memo.append(True)
memo[0] = False
cnt = 0
stack = [[0, memo]]
while stack != []:
	now = stack.pop(-1)
	if True not in now[1]:
		cnt += 1
	else:
		for i in range(0, len(grp[now[0]])):
			next = grp[now[0]][i]
			if now[1][next]:
				nextmemo = now[1][:next] + [False]
				if next != N-1:
					nextmemo = nextmemo + now[1][next+1:]
				stack.append([next, nextmemo])
print(cnt)

Solution (Python):
n, m = map(int,input().split())
lis = [0 for i in range(m)]
for i in range(m):
    lis[i] = list(map(int,input().split()))
    
seen = []
count = 0
visited = [0 for i in range(n)]
def route(x=1):
    visited[x-1] = 1
    if [1]*n == visited:
        global count
        count +=1
        return
    for i in range(m):
        if lis[i][0] == x and visited[lis[i][1]-1] == 0:
            route(lis[i][1])
            visited[lis[i][1]-1] = 0
        elif lis[i][1] == x and visited[lis[i][0]-1] == 0:
            route(lis[i][0])
            visited[lis[i][0]-1] = 0
    return
            
        
route(1)
print(count)

Solution (Python):

import sys
sys.setrecursionlimit(10**7)
import math
from collections import defaultdict


mod = 10**9 + 7


def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N):
  read_all = [tuple(map(int, input().split())) for _ in range(N)]
  return map(list,zip(*read_all))



N,M = II()
a,b = Line(M)

can_visit = defaultdict(list)
for i in range(M):
  can_visit[a[i]-1].append(b[i]-1)
  can_visit[b[i]-1].append(a[i]-1)
from itertools import permutations
road = list(permutations([i for i in range(N)]))
counter = 0
for r in road:
  if r[0]!=0:
    continue
  temp = 0
  check_visited = [False]*N
  check_visited[0] = True
  for i in r[1:]:
    if (i in can_visit[temp]) and (check_visited[i]==False):
      temp = i
      check_visited[i] = True
      if check_visited == [True]*N:
        counter += 1
        break
    else:
      break
print(counter)

Solution (Python):

import sys
sys.setrecursionlimit(10**7)
import math
from collections import defaultdict


mod = 10**9 + 7


def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N):
  read_all = [tuple(map(int, input().split())) for _ in range(N)]
  return map(list,zip(*read_all))



N,M = II()
a,b = Line(M)

can_visit = defaultdict(list)
for i in range(M):
  can_visit[a[i]-1].append(b[i]-1)
  can_visit[b[i]-1].append(a[i]-1)
from itertools import permutations
road = list(permutations([i for i in range(N)]))
counter = 0
for r in road:
  if r[0]!=0:
    continue
  temp = 0
  check_visited = [False]*N
  check_visited[0] = True
  for i in r[1:]:
    if (i in can_visit[temp]) and (check_visited[i]==False):
      temp = i
      check_visited[i] = True
      if check_visited == [True]*N:
        counter += 1
        break
    else:
      break
print(counter)

Solution (Python):
def dfs(v, n, visited):
  passed = True
  for i in range(n):
    if not visited[i]:
      passed = False
  if passed:
    return 1
  ret = 0
  for i in range(n):
    if (v, i) not in graph:
      continue
    if not graph[(v, i)]:
      continue
    if visited[i]:
      continue
    visited[i] = True
    ret += dfs(i, n, visited)
    visited[i] = False
  return ret

n, m = map(int, input().split())
graph = {}
for _ in range(m):
  a, b = map(int, input().split())
  graph[(a-1,b-1)] = True
  graph[(b-1,a-1)] = True
visited= [False] *n
visited[0] = True
print(dfs(0, n, visited))

Solution (Python):
import sys

def solve(N,M,E):
    def dfs(v, visited = set()):
        nonlocal cnt
        if len(visited) + 1 == N:
            cnt += 1
        for u in E[v]:
            if not u in visited:
                dfs(u, visited | {v})

    stack = [1]
    cnt = 0
    dfs(1)
    print(cnt)

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

if __name__ == "__main__":
    main()

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

import itertools
ans = 0 
for ls_can in list(itertools.permutations(can)):
    ls_can = [1]+list(ls_can)
    flg = 0
    for i in range(n-1):
        if [ls_can[i],ls_can[i+1]] in ls or [ls_can[i+1],ls_can[i]] in ls :
            flg +=1
        else:
            break
        if flg == n-1:
            ans +=1
print(ans)

Solution (Python):
import math
import itertools

INF = 10**9+7
PRIME_NUM = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997]

def main():
	n,m = map(int,input().split())
	ab = []
	for i in range(m):
		ab.append(list(map(int,input().split())))
	link = []
	for i in range(n+1):
		link.append([])
	for i in ab:
		link[i[0]].append(i[1])
		link[i[1]].append(i[0])
	tmp = [i for i in range(2,n+1)]
	ans=0
	for i in itertools.permutations(tmp):
		flag =  True
		array = [1] + list(i)
		for j in range(0,n-1):
			if(link[array[j]].count(array[j+1])==0): flag = False
		if flag:
			ans+=1
	print(ans)

main()

Solution (Python):
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
def calc(G, E, s):
    global ans
    E.append(s)
    for v in G[s]:
        if v in E:
            continue
        if len(E) == N - 1 and v not in E:
            ans += 1
            return
        calc(G, E, v)
        E.remove(v)

calc(G, [], 0)
print(ans)

Solution (Python):
N,M = map(int,input().split())
pat = [[int(i) for i in input().split()] for _ in range(M)]
Graph = [[0 for i in range(N)] for _ in range(N)]
for i,j in pat:
    Graph[i-1][j-1] = 1
    Graph[j-1][i-1] = 1

def dfs(v,N,visit_list):

    all_visit = True

    for i in range(N):
        if visit_list[i] == False:
            all_visit = False
    
    if all_visit:
        return 1

    ret = 0

    for k in range(N):
        if Graph[v][k] == False:
            continue
        if visit_list[k] :
            continue
        
        visit_list[k] = True
        ret += dfs(k,N,visit_list)
        visit_list[k] = False
    return ret

visit_list = [False for i in range(N)]
visit_list[0] = True
print(dfs(0,N,visit_list))

Solution (Python):
import sys
sys.setrecursionlimit(4100000)

from itertools import permutations


def resolve():
    N_vertex, M_edge = [int(x) for x in sys.stdin.readline().split()]
    edge_set = set([
        tuple(int(x) for x in sys.stdin.readline().split())
        for _ in range(M_edge)
    ])
    

    count = 0
    for p in permutations(range(1, N_vertex + 1)):
        
        if p[0] != 1:
            continue
        is_broken = False
        for i in range(N_vertex - 1):
            if (p[i], p[i + 1]) in edge_set or (p[i + 1], p[i]) in edge_set:
                pass
            else:
                is_broken = True
                break
        if not is_broken:
            count += 1

    print(count)


if __name__ == "__main__":
    resolve()





import sys
from io import StringIO
import unittest


class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)

    def test_入力例_1(self):
        input = """3 3
1 2
1 3
2 3"""
        output = """2"""
        self.assertIO(input, output)

    def test_入力例_2(self):
        input = """7 7
1 3
2 7
3 4
4 5
4 6
5 6
6 7"""
        output = """1"""
        self.assertIO(input, output)

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


def dfs(v,n,visited):
    all_visited = True

    for i in range(n):
        if visited[i] == False:
            all_visited = False

    if all_visited:
        return 1

    ret = 0

    for i in range(n):
        if not graph[v][i]:
            continue
        if visited[i]:
            continue
        visited[i] = 1
        ret += dfs(i,n,visited)
        visited[i] = 0

    return ret

def main():
    visited = []
    for i in range(n):
        visited.append(0)
    visited[0] =1
    print((dfs(0,n,visited)))



if __name__ == '__main__':
    main()

Solution (Python):



import sys
sys.setrecursionlimit(10000000)
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())
    G[a-1].append(b-1)
    G[b-1].append(a-1)
s = [i for i in range(n)]
t = list(permutations(s))
ans = 0
for i in t:
    if i[0] == 0:
        for j in range(n-1):
            if i[j+1] not in G[i[j]]:
                break
        else:
            ans += 1
print(ans)

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

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

def bfs(cur, l) :
    if all(visited) :
        return 1
        
    ret = 0
    for nex in vec[cur] :
        if not visited[nex] :
            visited[nex] = True
            ret += bfs(nex, l + 1)
            visited[nex] = False
            
    return ret

visited[0] = True    
print(bfs(0, 0))

Solution (Python):

import sys
sys.setrecursionlimit(300000)


def solve(N: int, M: int, a: "List[int]", b: "List[int]"):
    conn = [[] * N for _ in range(N)]
    for i in range(M):
        conn[a[i] - 1].append(b[i] - 1)
        conn[b[i] - 1].append(a[i] - 1)
    def dfs(idx, visited):
        last = True
        for v in visited:
            if not v:
                last = False
                break
        if last:
            return 1
        ret = 0
        for nex in conn[idx]:
            if not visited[nex]:
                visited[nex] = True
                ret += dfs(nex, visited)
                visited[nex] = False
        return ret
    visited = [False] * N
    visited[0] = True
    count = dfs(0, visited)
    print(count)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  
    M = int(next(tokens))  
    a = [int()] * (M)  
    b = [int()] * (M)  
    for i in range(M):
        a[i] = int(next(tokens))
        b[i] = int(next(tokens))
    solve(N, M, a, b)

if __name__ == '__main__':
    main()

Solution (Python):

N,M = map(int,input().split())
lis = []
path = ["1"]

for i in range(M):

    a,b = map(int,input().split())
    lis.append([a,b])

for i in range(N-1):

    i += 1

    npath = []

    for p in path:


        for j in lis:

            if j[0] == int(p[-1]) and str(j[1]) not in p:

                npath.append(p + str(j[1]))

            if j[1] == int(p[-1]) and str(j[0]) not in p:

                npath.append(p + str(j[0]))

    path = npath.copy()


print (len(path))

Solution (Python):
N,M=map(int,input().split())
inp=[list(map(int,input().split())) for _ in range(M)]
g=[[] for _ in range(N)]
[g[a-1].append(b-1) for a,b in inp]
[g[b-1].append(a-1) for a,b in inp]
 
from itertools import permutations
seq=[i for i in range(N)]
test=list(permutations(seq))
cnt=0
for t in test:
    if t[0]==0:
        for i in range(N-1):
            if t[i+1] not in g[t[i]]:
                break
        else:
            cnt+=1
print(cnt)

Solution (Python):
import itertools

b_lis = []
j_lis = []
N,M = map(int,input().split())
for i in range(M):
    b_lis.append(list(map(int,input().split())))
    
n_lis =list(range(2,N+1))

count = 0
for i in itertools.permutations(n_lis):
    frag = 1
    
    l = [1]
    l.extend(i)
    
    for k in range(N-1):
        if [l[k],l[k+1]] in b_lis or [l[k+1],l[k]] in b_lis:
            pass
            
        else:
            frag = 0
            break
    if frag == 1:
        count += 1
        

print(count)

Solution (Python):
import math
from collections import defaultdict
import itertools
def input_as_int():
    return tuple(map(int,input().split()))

N,M  = input_as_int()

path = defaultdict(lambda  :defaultdict(lambda :False))
for i in range(M):
    a,b = input_as_int()
    path[a][b] = path[b][a] = True

ans = 0
roots = itertools.permutations(list(range(2,N+1)))
for root in roots:
    fr = 1
    flag = True
    for to in root:
        if path[fr][to]:
            fr = to
        else:
            flag = False
            break
    if flag:
        ans += 1
print(ans)

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

d = [[False for i in range(N)] for i in range(N)]
visited = [False] * N

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

def dfs(now, depth):
    if visited[now]:
        return 0
    if depth == N - 1:
        return 1
    
    ret = 0
    visited[now] = True

    for i in range(N):
        if d[now][i]:
            ret += dfs(i, depth + 1)
    
    visited[now] = False

    return ret

print(dfs(0,0))

Solution (Python):
N, M = map(int,input().split())
C = [[] for i in range(N)]
for i in range(M):
  a,b = map(int, input().split())
  a -= 1
  b -= 1
  C[a].append(b)
  C[b].append(a)
visited = [0]*N
ans = 0
def dfs(x):
  global ans
  visited[x] = 1  
  if all(visited):
    ans += 1
    return
  for i in C[x]:
    if visited[i] == 0:
      dfs(i)
      visited[i] = 0
  return
dfs(0)
print(ans)

Solution (Python):
n, m = [int(i) for i in input().split()]

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

s = [0]
p = 0
cnt = 0
h = -1
while True:
    if 1 in g[p][h+1:]:
        q = g[p].index(1, h+1)
        if q not in s:
            p = q
            h = -1
            s.append(p)
        else:
            h = q
    else:
        if len(s) == n:
            cnt += 1
        elif len(s) == 1:
            break
        h = p
        s.pop()
        p = s[-1]

print(cnt)

Solution (Python):
import bisect
import heapq
import itertools
import math
import os
import re
import string
import sys
from collections import Counter, deque, defaultdict
from copy import deepcopy
from decimal import Decimal
from fractions import gcd
from functools import lru_cache, reduce
from operator import itemgetter

import numpy as np

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7

N, M = list(map(int, sys.stdin.readline().split()))
A, B = list(zip(*[map(int, sys.stdin.readline().split()) for _ in range(M)]))

graph = np.zeros((N, N), dtype=bool)
for a, b in zip(A, B):
    graph[a - 1][b - 1] = True
    graph[b - 1][a - 1] = True

cnt = 0
for order in itertools.permutations(range(1, N)):
    ok = graph[0][order[0]]
    for v, u in zip(order[:-1], order[1:]):
        ok &= graph[v][u]
    cnt += ok
print(cnt)

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

g = [[] for _ in range(N)]
for a, b in AB:
	a, b = a - 1, b - 1
	g[a] += [b]
	g[b] += [a]

def dfs(v, visited):
	
	if v in visited:
		return False
	if N - 1 == len(visited):
		return True
	count = 0
	for n in g[v]:
		count += dfs(n, visited | {v})
	return count

print(dfs(0, set()))

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

v = []

for i in range(M):
    line = map(int, input().split())
    v.append([x - 1 for x in line])

conn = []
for _ in range(N):
    conn.append([False] * N)

visited = [False] * N

for start, end in v:
    conn[start][end] = conn[end][start] = True

def dfs(now, depth):
    if visited[now]:
        return 0
    if depth == N - 1:
        return 1

    visited[now] = True
    ret = 0

    for i in range(N):
        if conn[now][i]:
            ret += dfs(i, depth + 1)
    
    visited[now] = False

    return ret

print(dfs(0,0))

Solution (Python):
n,m=map(int,input().split())
path=[list(map(int,input().split())) for i in range(m)]


def ok(l1, now, next):
    
    
    l=l1[:]
    count=0
    if [now,next] in path or [next, now] in path:
        l.remove(next)
        if len(l)==0:
            return 1
        for i in range(len(l)):
            count+=ok(l, next, l[i])
        return count
    else:
        return 0

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

now=1
tmp=li[:]
count=0
for i in range(len(tmp)):
    count+=ok(tmp, now, tmp[i])
print(count)

Solution (Python):

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

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


def count_path(node, path, list_edge, N):
    
    count = 0
    
    if len(path) == N:
        
        count += 1
    
    else:
        
        for next_node in list_edge[node]:
            
            if next_node not in path:
                
                count += count_path(next_node, path + [next_node], list_edge, N)
    
    return count

print(count_path(1, [1], list_edge, N))

Solution (Python):

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

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

list_path = [[1]]

while list_path != [] and len(list_path[0]) < N:
    
    path = list_path.pop(0)
    
    for node in list_edge[path[-1]]:
        
        if node not in path:
            
            list_path.append(path + [node])

print(len(list_path))

Solution (Python):
import itertools

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

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

Solution (Python):
import itertools

n, m = map(int, input().split())
path = [[False] * 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

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())
if M == 0:
    print(0)
else:
    l = [[0 for _ in range(N)] for _ in range(N)]
    for _ in range(M):
        a,b = map(int,input().split())
        l[a-1][b-1] = 1
        l[b-1][a-1] = 1
    g = 0
    def dfs(a,route):
        global g
        if len(route) == N:g += 1
        else:
            for i in range(N):
                if a == i:pass
                else:
                    if l[a][i] == 1 and (not i in route):
                        dfs(i,route+[i])
    dfs(0,[0])
print(g)

Solution (Python):
def DFS(n):
    global ans
    stack.append(n)
    for i in range(M):
        if graf[i][0] ==n:
            if graf[i][1] not in stack:DFS(graf[i][1])
        if graf[i][1]==n:
            if graf[i][0] not in stack:DFS(graf[i][0])
    if len(stack)==N:ans+=1
    stack.pop()

N,M=map(int,input().split())
graf,stack,ans=[],[],0
for _ in range(M):
    graf.append(list(map(int,input().split())))
DFS(1)
print(ans)

Solution (Python):
n,m=map(int,input().split())
c=[[] for i in range(n)]
for i in range(m):
	a,b=map(int,input().split())
	c[a-1].append(b-1)
	c[b-1].append(a-1)
cnt=[0]
def dfs(z,s):
	z[s]=1
	if sum(z)==n:
		cnt[0]+=1
	else:
		for i in c[s]:
			if z[i]==0:
				dfs(z[:i]+[1]+z[i+1:],i)
dfs([0]*n,0)
print(cnt[0])

Solution (Python):
from itertools import permutations
N,M = map(int,input().split())
ab = [tuple(map(lambda x:int(x)-1,input().split())) for i in range(M)]
c = permutations(range(N)[1:])
ans = 0
for per in c:
    per = [0] + list(per)
    flag = True
    for i in range(N-1):
        p1 = min(per[i],per[i+1])
        p2 = max(per[i],per[i+1])
        if (p1,p2) in ab:
            continue
        else:
            flag=False
    if flag:
        ans+=1
print(ans)

Solution (Python):
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
def dfs(cur, rem):
    global ans
    if len(rem) == 0:
        ans += 1
        return
    for cand in G[cur]:
        if cand in rem:
            i = rem.index(cand)
            dfs(cand, rem[:i] + rem[i+1:])

dfs(0, list(range(1, N)))

print(ans)

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

check = [False] * N
check[0] = True
def dfs(v):
    if sum(check) == N:
        return 1
    ans = 0
    for u in E[v]:
        if check[u]:
            continue
        check[u] = True
        ans += dfs(u)
        check[u] = False
    return ans
print(dfs(0))

Solution (Python):
n, m = map(int, input().split())
d = {i+1 : [] for i in range(n)}
for _ in range(m):
  a, b = map(int, input().split())
  d[a].append(b)
  d[b].append(a)
ans = 0
def go(c, rem):
  global ans
  if not len(rem):
    ans += 1
    return
  for cand in d[c]:
    if cand in rem:
      i = rem.index(cand)
      go(cand, rem[:i] + rem[i+1:])
go(1, list(range(2, n+1)))
print(ans)

Solution (Python):
from itertools import permutations

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

A = [[0]*N for i in range(N)]

for i in range(M) :
    u,v = map(int,input().split())
    u -= 1
    v -= 1
    
    A[u][v] = 1
    A[v][u] = 1

ran = list(range(1,N))

P = list(permutations(ran))

ans = 0

for perm in P :
    perm = list(perm)
    
    for u,v in zip([0]+perm, perm) :
        if not A[u][v] :
            break
        
    else :
        ans += 1

print(ans)