AtCoder Beginner Contest 054 - One-stroke Path

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-----
3 3
1 2
1 3
2 3

-----Sample Output-----
2

The given graph is shown in the following figure:
The following two paths satisfy the condition:

Source: atcoder | Difficulty: EASY


Solutions:
from itertools import permutations
(N, M) = map(int, input().split())
G = [[] for _ in range(N)]
for _ in range(M):
	(a, b) = map(int, input().split())
	(a, b) = (a - 1, b - 1)
	G[a].append(b)
	G[b].append(a)
res = 0
for P in permutations(range(N), N):
	if P[0] != 0:
		continue
	for i in range(N - 1):
		if P[i + 1] not in G[P[i]]:
			break
	else:
		res += 1
print(res)


(n, m) = map(int, input().split())
e = [[] for _ in [0] * -~n]
for _ in [0] * m:
	(a, b) = map(int, input().split())
	e[a] += [b]
	e[b] += [a]
candy = [[1]]
for _ in [0] * ~-n:
	tmp = []
	for c in candy:
		for next in e[c[-1]]:
			tmp += [c + [next]]
	candy = tmp
print(sum((c == set(range(1, n + 1)) for c in map(set, candy))))


import itertools
(n, m) = list(map(int, input().split()))
path = [[False] * n for _ in range(n)]
for i in range(m):
	(a, b) = list(map(int, input().split()))
	a -= 1
	b -= 1
	path[a][b] = True
	path[b][a] = True
ans = 0
for i in itertools.permutations(list(range(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)


(N, M) = [int(a) for a in input().split()]
edges = {i: [] for i in range(1, N + 1)}
for i in range(M):
	(a, b) = [int(a) for a in input().split()]
	edges[a].append(b)
	edges[b].append(a)

def dfs(list):
	if len(list) == N:
		return 1
	else:
		a = list[-1]
		next = [n for n in edges[a] if n not in list]
		if len(next) == 0:
			return 0
		total = 0
		for n in next:
			total += dfs(list + [n])
		return total
ans = dfs([1])
print(ans)


(N, M) = map(int, input().split())
leng = [set() for i in range(N + 1)]
res = 0
for _ in range(M):
	(a, b) = map(int, input().split())
	leng[a].add(b)
	leng[b].add(a)

def check(arr):
	for i in range(N - 1):
		if arr[i + 1] not in leng[arr[i]]:
			return False
	return True
import itertools
for i in itertools.permutations([x for x in range(2, N + 1)]):
	if check([1] + list(i)):
		res += 1
print(res)


(N, M) = list(map(int, input().split()))
A = [[] for i in range(N)]
for i in range(M):
	(x, y) = list(map(int, input().split()))
	A[x - 1].append(y)
	A[y - 1].append(x)
color = ['W' for i in range(N)]
clear = ['B' for i in range(N)]

def path(x, d):
	if color[x - 1] == 'B':
		return False
	color[x - 1] = 'B'
	if color == clear:
		color[x - 1] = 'W'
		return True
	ans = 0
	for i in range(len(A[x - 1])):
		ans += int(path(A[x - 1][i], d + 1))
	color[x - 1] = 'W'
	return ans
print(path(1, 0))


from itertools import permutations
(N, M) = map(int, input().split())
AB = [0 for i in range(M)]
for i in range(M):
	ab = list(map(int, input().split()))
	AB[i] = ab
count = 0
nums = [i for i in range(1, N + 1)]
pers = permutations(nums, N)
for i in pers:
	if i[0] == 1:
		flag1 = 0
		for j in range(N - 1):
			flag2 = False
			for k in range(M):
				if i[j] == AB[k][0] and i[j + 1] == AB[k][1] or (i[j] == AB[k][1] and i[j + 1] == AB[k][0]):
					flag2 = True
			if flag2:
				flag1 += 1
		if flag1 == N - 1:
			count += 1
print(count)


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

def dfs(V, s):
	V[s] = 1
	if sum(V) == N:
		cnt[0] += 1
	else:
		for adj in G[s]:
			if V[adj] == 0:
				dfs(V[:adj] + [1] + V[adj + 1:], adj)
dfs([0] * N, 0)
print(cnt[0])


import itertools
(N, M) = map(int, input().split())
ab = []
for _ in range(M):
	(a, b) = map(int, input().split())
	ab.append({a - 1, b - 1})
ans = 0
for v in itertools.permutations(range(1, N)):
	ok = True
	a = 0
	for b in v:
		if {a, b} not in ab:
			ok = False
			break
		a = b
	if ok:
		ans += 1
print(ans)


import itertools
import collections
(n, m) = map(int, input().split())
a = [list(sorted(map(int, input().split()))) for i in range(m)]
a.sort()
cnt = 0
for i in itertools.permutations(range(2, n + 1), n - 1):
	li = [1] + list(i)
	if sum((list(sorted(edge)) in a for edge in zip(li, li[1:]))) == n - 1:
		cnt += 1
print(cnt)


(n, m) = map(int, input().split())
root = [[] for _ in range(n + 1)]
for i in range(m):
	(a, b) = map(int, input().split())
	root[a].append(b)
	root[b].append(a)
s = [0] * (n + 1)
s[0] = 1
s[1] = 1
ans = 0

def f(a, x):
	global ans
	for i in root[a]:
		if x[i] == 0:
			x[i] = 1
			f(i, x)
			x[i] = 0
	if x.count(1) == n + 1:
		ans += 1
f(1, s)
print(ans)


from itertools import permutations
(n, m) = map(int, input().split())
data = [[False] * n for i in range(n)]
for i in range(m):
	(a, b) = map(int, input().split())
	a -= 1
	b -= 1
	data[a][b] = True
	data[b][a] = True
ans = 0
for i in permutations(range(n), n):
	if i[0] == 0:
		for j in range(n):
			if j == n - 1:
				ans += 1
				break
			if not data[i[j]][i[j + 1]]:
				break
print(ans)


import collections
import copy

def dfs(i, basho, memo):
	nonlocal ans
	if memo[basho] == 1:
		return
	memo[basho] = 1
	if i == n:
		if sum(memo) == n:
			ans += 1
		return
	tmp = collections.Counter(graph[basho])
	for next_basho in tmp.keys():
		copy_memo = copy.copy(memo)
		dfs(i + 1, next_basho, copy_memo)
(n, m) = map(int, input().split())
graph = [[] for i in range(n + 1)]
for i in range(m):
	(a, b) = map(int, input().split())
	graph[a].append(b)
	graph[b].append(a)
memo = [0 for i in range(n + 1)]
ans = 0
dfs(1, 1, memo)
print(ans)


import itertools
(N, M) = map(int, input().split())
ab = list((list(map(int, input().split())) for _ in range(M)))
l = list((l for l in range(1, N + 1)))
numlist = list(itertools.permutations(l))
ans = 0
for I in numlist:
	if I[0] == 1 and all((sorted([I[j], I[j + 1]]) in ab for j in range(N - 1))):
		ans += 1
print(ans)


(N, M) = map(int, input().split())
AB = [tuple(map(int, input().split())) for i in range(M)]
es = [[0] * N for _ in range(N)]
for (a, b) in AB:
	(a, b) = (a - 1, b - 1)
	es[a][b] = es[b][a] = 1
ans = 0
import itertools
for ptn in itertools.permutations(range(1, N)):
	ptn = list(ptn)
	for (a, b) in zip([0] + ptn, ptn):
		if not es[a][b]:
			break
	else:
		ans += 1
print(ans)


import itertools
(N, M) = map(int, input().split())
edges = {tuple(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 += all((tuple(sorted(edge)) in edges for edge in zip(l, l[1:])))
print(ans)


import itertools
(N, M) = map(int, input().split())
edges = []
for i in range(M):
	edges.append(list(map(int, input().split())))
res = 0
for i in itertools.permutations(range(2, N + 1), N - 1):
	path = [1] + list(i)
	check = [sorted(path[i:i + 2]) in edges for i in range(len(path) - 1)]
	if not False in check:
		res += 1
print(res)


from itertools import permutations
(n, m) = map(int, input().split())
path = set()
for _ in range(m):
	(u, v) = map(int, input().split())
	path |= {(u - 1, v - 1), (v - 1, u - 1)}
s = 0
for i in permutations(range(n)):
	if i[0] == 0:
		s += all(((h, j) in path for (h, j) in zip(i[1:], i)))
print(s)


from itertools import permutations
(N, M, *ab) = map(int, open(0).read().split())
g = [[] for _ in range(N)]
for (a, b) in zip(*[iter(ab)] * 2):
	a -= 1
	b -= 1
	g[a].append(b)
	g[b].append(a)
ans = 0
for path in permutations(range(1, N)):
	v = 0
	for nv in path:
		if nv not in g[v]:
			break
		v = nv
	else:
		ans += 1
print(ans)


from itertools import permutations
(n, m) = map(int, input().split())
e = [tuple(sorted(map(int, input().split()))) for _ in range(m)]
ans = 0
for i in permutations(range(2, n + 1), n - 1):
	l = [1] + list(i)
	ans += sum((1 for j in zip(l, l[1:]) if tuple(sorted(j)) in e)) == n - 1
print(ans)


import itertools
(n, m) = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(m)]
path = [[] for _ in range(n)]
for (a, b) in AB:
	(a, b) = (a - 1, b - 1)
	path[a].append(b)
	path[b].append(a)
ans = 0
for ptn in itertools.permutations(range(1, n)):
	s = 0
	for nex in ptn:
		if s not in path[nex]:
			break
		s = nex
	else:
		ans += 1
print(ans)


import itertools
(n, m) = map(int, input().split())
tbl = [[0] * n for _ in range(n)]
for _ in range(m):
	(a, b) = map(int, input().split())
	tbl[a - 1][b - 1] = 1
	tbl[b - 1][a - 1] = 1
ans = 0
l = [i + 1 for i in range(n - 1)]
for p in itertools.permutations(l, n - 1):
	flag = True
	p = [0] + list(p)
	for i in range(n - 1):
		if tbl[p[i]][p[i + 1]] == 0:
			flag = False
			break
	if flag:
		ans += 1
print(ans)


(n, m) = map(int, input().split())
edge = [n * [0] for _ in range(n)]
for i in range(m):
	(a, b) = map(int, input().split())
	a -= 1
	b -= 1
	edge[a][b] = edge[b][a] = 1
from itertools import permutations
ans = 0
for i in permutations([j for j in range(1, n)], n - 1):
	f = True
	t = [0] + list(i)
	for j in range(1, n):
		if edge[t[j - 1]][t[j]] == 0:
			f = False
	if f:
		ans += 1
print(ans)


import itertools
(n, m) = map(int, input().split())
e = set([tuple(sorted(map(int, input().split()))) for x in range(m)])
cnt = 0
for i in itertools.permutations(range(2, n + 1), n - 1):
	l = [1] + list(i)
	if sum((1 for x in range(n - 1) if tuple(sorted(l[x:x + 2])) in e)) == n - 1:
		cnt += 1
print(cnt)


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

def dfs(v, visited):
	if v in visited:
		return 0
	if len(visited | {v}) == n:
		return 1
	return sum((dfs(i, visited | {v}) for i in range(1, n + 1) if {i, v} in ab))
print(dfs(1, set()))


from itertools import permutations
(N, M) = map(int, input().split())
S = []
for i in range(M):
	(a, b) = map(int, input().split())
	S.append([a, b])
vertex = (i + 1 for i in range(N))
all_path = list(permutations(vertex))
ans = 0
for p in all_path:
	flag = True
	if p[0] == 1:
		for i in range(N - 1):
			if [p[i], p[i + 1]] not in S and [p[i + 1], p[i]] not in S:
				flag = False
				break
		if flag:
			ans += 1
print(ans)


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

def dfs(v):
	if len(v) == n:
		return 1
	ans = 0
	for u in set(g[v[-1]]) - set(v):
		ans += dfs(v + [u])
	return ans
print(dfs([0]))


from itertools import permutations
(n, m) = map(int, input().split())
G = [[0] * n for i in range(n)]
for i in range(m):
	(a, b) = map(int, input().split())
	G[a - 1][b - 1] = G[b - 1][a - 1] = 1
l = [i + 1 for i in range(n - 1)]
c = 0
for v in permutations(l, n - 1):
	L = [0] + [i for i in v]
	if all([G[L[i]][L[i + 1]] == 1 for i in range(n - 1)]):
		c += 1
print(c)


from itertools import permutations
(N, M) = map(int, input().split())
edges = set((tuple(map(int, input().split())) for _ in range(M)))
ans = 0
for t in permutations(range(2, N + 1)):
	p = [1] + list(t)
	ok = True
	for i in range(N - 1):
		e = tuple(sorted((p[i], p[i + 1])))
		if not e in edges:
			ok = False
			break
	if ok:
		ans += 1
print(ans)


import itertools
(N, M) = map(int, input().split())
route = [list(map(int, input().split())) for _ in range(M)]
candidate = list(itertools.permutations(range(1, N + 1)))
ans = 0
for c in candidate:
	if c[0] == 1:
		for i in range(N - 1):
			l = sorted([c[i], c[i + 1]])
			if l not in route:
				break
		else:
			ans += 1
print(ans)


import itertools
(n, m) = list(map(int, input().split()))
num = [[] for _ in range(n)]
for i in range(m):
	(a, b) = list(map(int, input().split()))
	num[a - 1].append(b)
	num[b - 1].append(a)
cnt = list(itertools.permutations(list(range(2, n + 1))))
ans = 0
for i in range(len(cnt)):
	num1 = 1
	num2 = cnt[i]
	yn = 0
	for j in range(n - 1):
		if num2[j] not in num[num1 - 1]:
			yn = 1
			break
		num1 = num2[j]
	if yn == 0:
		ans += 1
print(ans)


(N, M) = map(int, input().split())
AB = [list(map(int, input().split())) for i in range(M)]
c = [[0] * N for i in range(N)]
for (a, b) in AB:
	c[a - 1][b - 1] = c[b - 1][a - 1] = 1
from itertools import permutations
r = 0
for n in permutations(range(1, N)):
	n = [0] + list(n)
	x = 1
	for i in range(N - 1):
		if not c[n[i]][n[i + 1]]:
			x = 0
	r += x
print(r)


(n, m) = map(int, input().split())
ab = [list(map(int, input().split())) for i in range(m)]
import itertools
ans = 0
l = [i for i in range(1, n + 1)]
p = itertools.permutations(l, n)
for v in p:
	v = list(v)
	if v[0] != 1:
		continue
	x = 0
	for i in range(n - 1):
		w = v[i:i + 2]
		w.sort()
		if w not in ab:
			x = 1
			break
	if x == 0:
		ans += 1
print(ans)


from collections import defaultdict
(N, M) = list(map(int, input().split()))
d = defaultdict(list)
for _ in range(M):
	(a, b) = list(map(int, input().split()))
	d[a].append(b)
	d[b].append(a)

def dfs(n, path):
	count = 0
	path.append(n)
	if len(path) == N:
		count += 1
		return count
	for i in d[n]:
		if i not in path:
			count += dfs(i, path)
			path.pop()
	return count
print(dfs(1, []))


import itertools
(N, M) = map(int, input().split())
G = {k: set() for k in range(N + 1)}
for _ in range(M):
	(a, b) = map(int, input().split())
	G[a].add(b)
	G[b].add(a)
ans = 0
for p in itertools.permutations(range(2, N + 1)):
	c = 1
	for n in p:
		if n not in G[c]:
			break
		c = n
	else:
		ans += 1
print(ans)


(n, m) = list(map(int, input().split()))
es = [[0 for i in range(n)] for i in range(n)]
for i in range(m):
	(a, b) = list(map(int, input().split()))
	es[a - 1][b - 1] = 1
	es[b - 1][a - 1] = 1
import sys
sys.setrecursionlimit(10 ** 7)
visited = [0 for i in range(n)]
check = [1 for i in range(n)]

def dfs(v, visited):
	ans = 0
	visited[v - 1] = 1
	if visited == check:
		visited[v - 1] = 0
		return 1
	for i in range(n):
		if es[v - 1][i] == 1 and visited[i] == 0:
			ans += dfs(i + 1, visited)
	visited[v - 1] = 0
	return ans
print(dfs(1, visited))


import itertools
(N, M) = list(map(int, input().split()))
graph = [[False] * N for _ in range(N)]
for _ in range(M):
	(a, b) = [int(x) - 1 for x in input().split()]
	graph[a][b] = True
	graph[b][a] = True
ans = 0
for path in itertools.permutations(list(range(N)), N):
	if path[0] == 0:
		for i in range(N):
			if i == N - 1:
				ans += 1
				break
			if not graph[path[i]][path[i + 1]]:
				break
print(ans)


from itertools import permutations
(N, M) = map(int, input().split())
paths = [list(map(int, input().split())) for _ in range(M)]
points = [i for i in range(1, N + 1)]
answer = 0
for point in permutations(points):
	if not point[0] == 1:
		continue
	for i in range(N - 1):
		if sorted([point[i], point[i + 1]]) not in paths:
			break
	else:
		answer += 1
print(answer)


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


import itertools
(N, M) = map(int, input().split())
A = [set(map(int, input().split())) for _ in range(M)]
ans = 0
for p in itertools.permutations(range(2, N + 1)):
	q = list(p) + [1]
	for i in range(N - 1):
		if not {q[i], q[i + 1]} in A:
			break
	else:
		ans += 1
print(ans)


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


(N, M) = map(int, input().split())
E = [[] for i in range(N)]
for i in range(M):
	(a, b) = map(int, input().split())
	(a, b) = (a - 1, b - 1)
	E[a].append(b)
	E[b].append(a)
r = 0
c = 0
s = 1
l = 1
q = [(c, s, l)]
while q:
	(c, s, l) = q.pop()
	if l == N:
		r += 1
		continue
	for n in E[c]:
		if s & 1 << n == 0:
			q.append((n, s | 1 << n, l + 1))
print(r)


from itertools import permutations
(N, M, *ab) = map(int, open(0).read().split())
g = [[0] * N for _ in range(N)]
for (a, b) in zip(*[iter(ab)] * 2):
	g[a - 1][b - 1] = 1
	g[b - 1][a - 1] = 1
ans = 0
for path in permutations(range(1, N)):
	path = [0] + list(path)
	if all((g[v][nv] for (v, nv) in zip(path, path[1:]))):
		ans += 1
print(ans)


def dfs(g, v, i):
	if len(v) == len(g) - 1:
		return 1
	v.add(i)
	c = 0
	for u in g[i]:
		if u not in v:
			c += dfs(g, v, u)
	v.remove(i)
	return c
(n, m) = map(int, input().split())
g = [list() 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)
print(dfs(g, set(), 0))


(N, M) = map(int, input().split())
G = [[] for i in range(N)]
for i in range(M):
	(a, b) = map(lambda x: int(x) - 1, input().split())
	G[a].append(b)
	G[b].append(a)
ans = 0
H = [[0]]
while H:
	h = H.pop()
	if len(h) == N:
		ans += 1
		continue
	p = h[-1]
	for v in G[p]:
		if not v in h:
			H.append(h + [v])
print(ans)


(n, m) = map(int, input().split())
G = [[0] * n for i in range(n)]
for i in range(m):
	(a, b) = map(int, input().split())
	G[a - 1][b - 1] = G[b - 1][a - 1] = 1
V = [0] * n
c = 0

def dfs(v):
	global c
	if sum(V) == n:
		c += 1
		return
	for v2 in range(n):
		if G[v][v2] == 1 and V[v2] == 0:
			V[v2] = 1
			dfs(v2)
			V[v2] = 0
	return
V[0] = 1
dfs(0)
print(c)


(N, M) = map(int, input().split())
L = [tuple(map(int, input().split())) for _ in range(M)]
import itertools
l = [i for i in range(2, N + 1)]
Ps = itertools.permutations(l, N - 1)
c = 0
for P in Ps:
	T = 1
	for p in P:
		if (T, p) in L or (p, T) in L:
			T = p
		else:
			break
	else:
		c += 1
print(c)


(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)
	AB[b - 1].append(a)

def dfs(n, seen):
	global ans
	seen.append(n)
	if len(seen) == N:
		ans += 1
	else:
		for i in AB[n - 1]:
			if i not in seen:
				dfs(i, seen)
	seen.remove(n)
ans = 0
dfs(1, [])
print(ans)


def dfs(v, used):
	if not False in used:
		return 1
	ans = 0
	for i in range(n):
		if not matrix[v][i]:
			continue
		if used[i]:
			continue
		used[i] = True
		ans += dfs(i, used)
		used[i] = False
	return ans
(n, m) = map(int, input().split())
matrix = [[0] * n for _ in range(n)]
for i in range(m):
	(a, b) = map(int, input().split())
	matrix[a - 1][b - 1] = 1
	matrix[b - 1][a - 1] = 1
used = [False] * n
used[0] = True
print(dfs(0, used))


import itertools
(n, m) = list(map(int, input().split()))
v = []
for i in range(m):
	tpl = tuple(map(int, input().split()))
	v.append(tpl)
	v.append((tpl[1], tpl[0]))
perms = list(itertools.permutations(range(1, n + 1)))
c = 0
for i in perms:
	if i[0] != 1:
		continue
	for j in range(len(i) - 1):
		if (i[j], i[j + 1]) not in v:
			break
	else:
		c += 1
print(c)


from itertools import permutations
(N, M) = map(int, input().split())
G = [[False] * (N + 1) for _ in range(N + 1)]
for _ in range(M):
	(a, b) = map(int, input().split())
	G[a][b] = True
	G[b][a] = True
ans = 0
for p in permutations(range(2, N + 1)):
	bl = G[1][p[0]]
	for (x, y) in zip(p[:-1], p[1:]):
		bl &= G[x][y]
	ans += int(bl)
print(ans)


f = lambda : map(int, input().split())
(n, m) = f()
g = [set() for _ in range(n)]
for _ in range(m):
	(a, b) = f()
	g[a - 1].add(b - 1)
	g[b - 1].add(a - 1)
from itertools import *
p = [*permutations(range(1, n))]
c = 0
for t in p:
	v = 0
	for i in t:
		if i in g[v]:
			v = i
		else:
			break
	else:
		c += 1
print(c)


import itertools
(N, M) = map(int, input().split())
E = [[] for i in range(N)]
for i in range(M):
	(a, b) = map(int, input().split())
	a -= 1
	b -= 1
	E[a].append(b)
	E[b].append(a)
count = 0
for V in itertools.permutations(range(1, N)):
	if V[0] in E[0] and all((V[i] in E[V[i - 1]] for i in range(1, N - 1))):
		count += 1
print(count)


import itertools
(N, M) = map(int, input().split())
Lines = [set(map(int, input().split())) for _ in range(M)]
count = 0
for p in itertools.permutations(range(1, N + 1)):
	if p[0] != 1:
		continue
	flag = True
	for i in range(N - 1):
		if not {p[i], p[i + 1]} in Lines:
			flag = False
			break
	if flag:
		count += 1
print(count)


from itertools import permutations
(N, M) = map(int, input().split())
E = []
for _ in range(M):
	(a, b) = map(int, input().split())
	E.append((a, b))
	E.append((b, a))
ans = 0
for p in permutations(range(2, N + 1)):
	perm = [1] + list(p)
	for i in range(N - 1):
		if (perm[i], perm[i + 1]) not in E:
			break
	else:
		ans += 1
print(ans)


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

def dfs(v, seen):
	nonlocal Graph
	seen.add(v)
	if len(seen) == N:
		seen.remove(v)
		return 1
	Res = [dfs(nv, seen) for nv in Graph[v] if not nv in seen]
	seen.remove(v)
	return sum(Res)
print(dfs(0, set()))


import itertools
(n, m) = map(int, input().split())
path = [[] for i in range(n)]
for i in range(m):
	(a, b) = map(int, input().split())
	path[a - 1].append(b - 1)
	path[b - 1].append(a - 1)
res = 0
for case in itertools.permutations(range(n)):
	if case[0] != 0:
		continue
	for i in range(n - 1):
		if case[i + 1] not in path[case[i]]:
			break
	else:
		res += 1
print(res)


from itertools import permutations
(n, m) = map(int, input().split())
g = [[] for i in range(n)]
for _ in range(m):
	(u, v) = map(int, input().split())
	g[u - 1].append(v - 1)
	g[v - 1].append(u - 1)
ans = 0
for v in permutations([int(i) for i in range(n)], n):
	if v[0] != 0:
		continue
	for i in range(n - 1):
		if not v[i + 1] in g[v[i]]:
			break
	else:
		ans += 1
print(ans)


from itertools import permutations
(N, M) = list(map(int, input().split()))
L = []
for _ in range(M):
	L.append(list(map(int, input().split())))
P = list(permutations(range(1, N + 1)))
ct = 0
for i in P:
	if i[0] == 1 and all((sorted([i[j], i[j + 1]]) in L for j in range(N - 1))):
		ct += 1
print(ct)


import itertools as it
(n, m) = map(int, input().split())
e = [[0 for i in range(n)] for j in range(n)]
for i in range(m):
	(a, b) = map(lambda x: int(x) - 1, input().split())
	e[a][b] = 1
	e[b][a] = 1
c = 0
for t in it.permutations([j + 1 for j in range(n - 1)]):
	i = (0,) + t
	c += 1
	for j in range(n - 1):
		if e[i[j]][i[j + 1]] == 0:
			c -= 1
			break
print(c)


(n, m) = map(int, input().split())
G = [set() for _ in range(n + 1)]
for _ in range(m):
	(a, b) = map(int, input().split())
	G[a].add(b)
	G[b].add(a)
seen = [False] * (n + 1)

def dfs(v, c):
	if c == n:
		return 1
	seen[v] = True
	temp = 0
	for nv in G[v]:
		if not seen[nv]:
			temp += dfs(nv, c + 1)
	seen[v] = False
	return temp
print(dfs(1, 1))


(N, M) = map(int, input().split())
to = [[] for i in range(N)]
for i in range(M):
	(a, b) = map(int, input().split())
	to[a - 1].append(b - 1)
	to[b - 1].append(a - 1)
ans = 0
v = [0] * N

def DFS(n):
	nonlocal ans
	v[n] = 1
	if sum(v) == N:
		ans += 1
	for i in to[n]:
		if v[i] == 0:
			DFS(i)
	v[n] = 0
DFS(0)
print(ans)


from itertools import permutations
(n, m) = map(int, input().split())
edges = {tuple(map(int, input().split())) for _ in range(m)}
ans = 0
for i in permutations(range(2, n + 1), n - 1):
	load = [1] + list(i)
	ans += sum((1 for edge in zip(load, load[1:]) if tuple(sorted(edge)) in edges)) == n - 1
print(ans)


import itertools
(n, m) = list(map(int, input().split()))
lis = []
for i in range(m):
	(a, b) = list(map(int, input().split()))
	lis.append((a, b))
LIS = [i for i in range(2, n + 1)]
big_lis = list(itertools.permutations(LIS))
L = len(big_lis)
ans2 = 0
for j in range(L):
	i = 1
	ans1 = 1
	for k in big_lis[j]:
		if ((i, k) not in lis) & ((k, i) not in lis):
			ans1 = 0
		i = k
	ans2 += ans1
print(ans2)


(N, M) = map(int, input().split())
adj = [set() for i in range(N + 1)]
for i in range(M):
	(u, v) = map(int, input().split())
	adj[u].add(v)
	adj[v].add(u)

def good(p):
	for i in range(N - 1):
		if p[i + 1] not in adj[p[i]]:
			return False
	return True
ans = 0
from itertools import permutations
for p in permutations(range(2, N + 1)):
	if good([1] + list(p)):
		ans += 1
print(ans)


import itertools
(n, m) = map(int, input().split())
li = []
for _ in range(m):
	(a, b) = map(int, input().split())
	li.append([a, b])
count = 0
for comb in itertools.permutations(range(n), n):
	if comb[0] != 0:
		continue
	judge = True
	for i in range(n - 1):
		if judge == False:
			break
		a = comb[i] + 1
		b = comb[i + 1] + 1
		if [a, b] in li or [b, a] in li:
			continue
		else:
			judge = False
			break
	if judge == True:
		count += 1
print(count)


import itertools
(n, m) = map(int, input().split())
edge_set = {tuple(map(int, input().split())) for _ in range(m)}
counter = 0
for i in itertools.permutations(range(2, n + 1), n - 1):
	path = [1] + list(i)
	path_set = {tuple(sorted(edge)) for edge in zip(path, path[1:])}
	if path_set <= edge_set:
		counter += 1
print(counter)


import itertools
(n, m) = map(int, input().split())
rin = [[] for _ in range(n)]
for _ in range(m):
	(a, b) = map(int, input().split())
	rin[a - 1].append(b - 1)
	rin[b - 1].append(a - 1)
li = [i for i in range(2, n + 1)]
ans = 0
for v in itertools.permutations(li):
	pas = 0
	ch = 0
	st = 1
	for x in range(n - 1):
		if v[x] - 1 not in rin[st - 1]:
			ch += 1
			break
		else:
			st = v[x]
	if ch == 0:
		ans += 1
print(ans)


import itertools
(n, m) = map(int, input().split())
edge = [[] for i in range(n + 1)]
for i in range(m):
	(a, b) = map(int, input().split())
	edge[a].append(b)
	edge[b].append(a)
ans = 0
for junretu in list(itertools.permutations(list(range(2, n + 1)))):
	now = 1
	flag = True
	for i in list(junretu):
		if not i in edge[now]:
			flag = False
			break
		now = i
	if flag:
		ans += 1
print(ans)


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


from itertools import permutations
(n, m) = map(int, input().split())
side = [[] for _ in range(n + 1)]
for i in range(m):
	(a, b) = map(int, input().split())
	side[a].append(b)
	side[b].append(a)
route = [i for i in range(2, n + 1)]
ans = 0
for x in permutations(route):
	x = list(x)
	x.insert(0, 1)
	for i in range(n - 1):
		if x[i + 1] not in side[x[i]]:
			break
	else:
		ans += 1
print(ans)


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

def s(n, v):
	if n in v:
		return 0
	if len(v) == N - 1:
		return 1
	return sum((s(i, v | {n}) for i in L[n]))
print(s(1, set()))


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

def walk(cur, visited):
	global ans
	tmp = visited + [cur]
	if len(tmp) == N:
		ans += 1
	for nex in g[cur]:
		if nex not in tmp:
			walk(nex, tmp)
walk(1, [])
print(ans)


(N, M) = map(int, input().split())
E = {i: [] for i in range(N)}
for _ in range(M):
	(u, v) = map(int, input().split())
	E[u - 1].append(v - 1)
	E[v - 1].append(u - 1)
q = [(0, [0])]
c = 0
while q:
	(x, p) = q.pop()
	if len(p) == N:
		c += 1
	for v in E[x]:
		if v in p:
			continue
		q.append((v, p + [v]))
print(c)


from itertools import permutations, islice

def window(seq, n):
	it = iter(seq)
	result = tuple(islice(it, n))
	if len(result) == n:
		yield result
	for elem in it:
		result = result[1:] + (elem,)
		yield result
(N, M, *ab) = list(map(int, open(0).read().split()))
g = [[0] * N for _ in range(N)]
for (a, b) in zip(*[iter(ab)] * 2):
	g[a - 1][b - 1] = 1
	g[b - 1][a - 1] = 1
ans = 0
for path in permutations(list(range(1, N))):
	path = [0] + list(path)
	if all((g[v][nv] for (v, nv) in window(path, 2))):
		ans += 1
print(ans)


from itertools import *
f = lambda : map(int, input().split())
(N, M) = f()
a = [[*f()] for i in range(M)]
a = [*a, *[[y, x] for (x, y) in a]]
p = [(1, *i) for i in [*permutations(range(2, N + 1))]]
print([sum((1 for y in range(N - 1) if [x[y], x[y + 1]] in a)) for x in p].count(N - 1))


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)


(N, M) = map(int, input().split())
r = [set() for _ in range(N + 1)]
for _ in range(M):
	(n1, n2) = map(int, input().split())
	r[n1].add(n2)
	r[n2].add(n1)
from itertools import permutations as p
c = 0
kumis = p(range(2, N + 1))
for kumi in kumis:
	prev = 1
	for k in kumi:
		if k not in r[prev]:
			break
		prev = k
	else:
		c += 1
print(c)


import itertools
(N, M) = map(int, input().split())
adj_matrix = [[0] * N for _ in range(N)]
for i in range(M):
	(a, b) = map(int, input().split())
	adj_matrix[a - 1][b - 1] = 1
	adj_matrix[b - 1][a - 1] = 1
cnt = 0
for each in itertools.permutations(range(N)):
	if each[0] != 0:
		break
	factor = 1
	for i in range(N - 1):
		factor *= adj_matrix[each[i]][each[i + 1]]
	cnt += factor
print(cnt)


(N, M) = map(int, input().split())
li = []
for i in range(N):
	li.append([-1 for i in range(N)])
for i in range(M):
	(a, b) = map(int, input().split())
	li[a - 1][b - 1] = 1
	li[b - 1][a - 1] = 1
import itertools
an = 0
for i in itertools.permutations(range(1, N)):
	jun = [0]
	jun += list(i)
	st = jun[0]
	for t in range(1, N):
		if li[jun[t]][st] == -1:
			break
		st = jun[t]
		if t == N - 1:
			an += 1
print(an)


import itertools
(n, m) = map(int, input().split())
ab = []
count = 0
for i in range(m):
	ab.append(set(map(int, input().split())))
ns = [i for i in range(1, n + 1)]
ptn = [i for i in list(itertools.permutations(ns)) if i[0] == 1]
for i in ptn:
	first = i[0]
	for s in range(1, n):
		if {first, i[s]} not in ab:
			break
		first = i[s]
	else:
		count += 1
print(count)


import itertools
(N, M) = map(int, input().split())
s = [list(map(int, input().split())) for _ in range(M)]
lst = [x for x in range(2, N + 1)]
l = itertools.permutations(lst)
ans = 0
for num in l:
	t = [1] + list(num)
	ok = True
	for j in range(N - 1):
		p = sorted([t[j], t[j + 1]])
		if not p in s:
			ok = False
			break
	if ok:
		ans += 1
print(ans)


(n, m) = map(int, input().split())
arr = [[0] * n for _ in range(n)]
for _ in range(m):
	(a, b) = map(int, input().split())
	arr[a - 1][b - 1] = 1
	arr[b - 1][a - 1] = 1
d = [0] * n
d[0] = 1
cnt = 0

def dfs(x):
	global cnt
	if all(d):
		cnt += 1
	for i in range(1, n + 1):
		if arr[x - 1][i - 1] and d[i - 1] == 0:
			d[i - 1] = 1
			dfs(i)
			d[i - 1] = 0
dfs(1)
print(cnt)


from itertools import permutations
(n, m) = map(int, input().split())
v = [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 v:
			crnt = nxt
		else:
			break
	else:
		ans += 1
print(ans)


import copy

def dfs(i, path, reached, n):
	if reached[i]:
		return n
	reached[i] = True
	if all(reached):
		n += 1
		return n
	for p in path[i]:
		org_reached = copy.deepcopy(reached)
		n = dfs(p, path, org_reached, n)
	return n

def main():
	(N, M) = list(map(int, input().split()))
	AB = [list(map(int, input().split())) for _ in range(M)]
	path = [[] for _ in range(N)]
	for (a, b) in AB:
		a -= 1
		b -= 1
		path[a].append(b)
		path[b].append(a)
	reached = [False for _ in range(N)]
	n = 0
	n = dfs(0, path, reached, n)
	print(n)
main()


(N, M) = map(int, input().split())
graph = [set() for _ in range(N)]
for _ in range(M):
	(a, b) = map(int, input().split())
	graph[a - 1].add(b - 1)
	graph[b - 1].add(a - 1)
ans = 0

def dfs(p, visited):
	global ans
	if len(visited) == N:
		ans += 1
	else:
		for q in graph[p]:
			if q not in visited:
				dfs(q, visited + [q])
dfs(0, [0])
print(ans)


import itertools as itt
(n, m) = map(int, input().split())
l = set()
for i in range(m):
	(a, b) = map(int, input().split())
	l.add((a, b))
	l.add((b, a))
lis = [i for i in range(1, n + 1)]
p_lis = list(itt.permutations(lis))
cnt = 0
for i in range(len(p_lis)):
	if p_lis[i][0] != 1:
		continue
	flg = [0] * (n - 1)
	for j in range(n - 1):
		x = (p_lis[i][j], p_lis[i][j + 1])
		if x in l:
			flg[j] = 1
	if all(flg):
		cnt += 1
print(cnt)


def dp(d, i):
	if sum(d) == n - 1:
		return 1
	x = 0
	for j in l[i]:
		if d[j - 2] == 1:
			continue
		di = d[:]
		di[j - 2] = 1
		x += dp(di, j)
	return x
(n, m) = map(int, input().split())
l = [[] for _ in range(n + 1)]
for i in range(m):
	(a, b) = map(int, input().split())
	if b != 1:
		l[a].append(b)
	if a != 1:
		l[b].append(a)
print(dp([0] * (n - 1), 1))


from itertools import permutations
from math import factorial
(n, m) = list(map(int, input().split(' ')))
edge = []
for i in range(m):
	(ai, bi) = list(map(int, input().split(' ')))
	edge.append([ai, bi])
x = [i for i in range(1, n + 1)]
ls = list(permutations(x))
ans = 0
for l in range(factorial(n - 1)):
	cnt = 0
	for i in range(n - 1):
		for j in range(m):
			if ls[l][i] in edge[j] and ls[l][i + 1] in edge[j]:
				cnt += 1
	if cnt == n - 1:
		ans += 1
print(ans)


import itertools
(n, m) = map(int, input().split())
E = [list(map(int, input().split())) for i in range(m)]
G = [[] for i in range(n)]
for i in range(m):
	G[E[i][0] - 1] += [E[i][1] - 1]
	G[E[i][1] - 1] += [E[i][0] - 1]
ans = 0
for p in itertools.permutations(range(1, n)):
	if p[0] in G[0] and all([p[i] in G[p[i - 1]] for i in range(1, n - 1)]):
		ans += 1
print(ans)


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


from itertools import permutations
(n, m) = map(int, input().split())
edge = [[0] * n for i in range(n)]
for i in range(m):
	(a, b) = map(int, input().split())
	a -= 1
	b -= 1
	edge[a][b] = edge[b][a] = 1
ret = 0
for i in permutations(range(n)):
	if i[0] != 0:
		break
	for j in range(n - 1):
		if edge[i[j]][i[j + 1]] == 0:
			break
	else:
		ret += 1
print(ret)


import itertools
(n, m) = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(m)]
c = [i for i in range(2, n + 1)]
b = []
for x in itertools.permutations(c):
	b.append([1] + list(x))
cnt = 0
for x in b:
	exist = True
	for i in range(n - 1):
		if not sorted(x[i:i + 2]) in a:
			exist = False
			break
	if exist:
		cnt += 1
print(cnt)


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


(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 go(curr, used, count):
	if count == 1:
		return 1
	tmp = used + [curr]
	return sum((go(node, tmp, count - 1) for node in g[curr] if node not in used))
print(go(0, [], n))


import itertools
(N, M) = map(int, input().split())
edges = [list(map(int, input().split())) for i in range(M)]
graph = [[] for i in range(N + 1)]
for edge in edges:
	graph[edge[0]].append(edge[1])
	graph[edge[1]].append(edge[0])
node = [i for i in range(1, N + 1)]
per_list = list(itertools.permutations(node))
count = 0
for l in per_list:
	if l[0] != 1:
		continue
	flg = 0
	for i in range(len(l) - 1):
		if not l[i + 1] in graph[l[i]]:
			flg = 1
			break
	if not flg:
		count += 1
print(count)


def dfs(now_node, depth):
	if seen[now_node]:
		return 0
	if depth == N:
		return 1
	seen[now_node] = True
	connect_nodes = graph[now_node]
	ans = 0
	for node in connect_nodes:
		ans += dfs(node, depth + 1)
	seen[now_node] = False
	return ans
(N, M) = map(int, input().split())
edges = [list(map(int, input().split())) for i in range(M)]
graph = [[] for i in range(N + 1)]
for edge in edges:
	graph[edge[0]].append(edge[1])
	graph[edge[1]].append(edge[0])
seen = [False for i in range(N + 1)]
seen[0] = True
print(dfs(1, 1))


import copy
from collections import deque
(n, m) = map(int, input().split())
e = [[] for i in range(n)]
for i in range(m):
	(a, b) = map(int, input().split())
	a -= 1
	b -= 1
	e[a].append(b)
	e[b].append(a)
visited = [False] * n
visited[0] = True
d = deque([[0, visited]])
cnt = 0
while d:
	(f, visited) = d.pop()
	for t in e[f]:
		v = copy.deepcopy(visited)
		if not v[t]:
			v[t] = True
			if False in v:
				d.append([t, v])
			else:
				cnt += 1
print(cnt)


def read_int_list():
	return list(map(int, input().split()))
(N, M) = read_int_list()
g = [[] for i in range(N)]
for i in range(M):
	(a, b) = read_int_list()
	a -= 1
	b -= 1
	g[a].append(b)
	g[b].append(a)

def dfs(v):
	if len(v) == N:
		return 1
	ans = 0
	for u in set(g[v[-1]]) - set(v):
		ans += dfs(v + [u])
	return ans
print(dfs([0]))


from itertools import *
(n, *t) = map(int, open(0).read().split())
e = {0}
for a in zip(t[1::2], t[2::2]):
	e |= {a, a[::-1]}
print(sum((all((u in e for u in zip(t, t[1:]))) for t in permutations(range(1, n + 1)) if t[0] < 2)))


def dfs(v):
	if sum(visited) == N:
		return 1
	res = 0
	for nv in g[v]:
		if visited[nv]:
			continue
		visited[nv] = 1
		res += dfs(nv)
		visited[nv] = 0
	return res
(N, M, *ab) = list(map(int, open(0).read().split()))
g = [[] for _ in range(N)]
for (a, b) in zip(*[iter(ab)] * 2):
	a -= 1
	b -= 1
	g[a].append(b)
	g[b].append(a)
visited = [0] * N
visited[0] = 1
print(dfs(0))


import itertools
(N, M, *AB) = [int(_) for _ in open(0).read().split()]
G = [set() for _ in range(N)]
for (a, b) in zip(AB[::2], AB[1::2]):
	a -= 1
	b -= 1
	G[a].add(b)
	G[b].add(a)
ans = 0
for root in itertools.permutations(range(1, N), N - 1):
	root = [0] + list(root)
	if all((a in G[b] for (a, b) in zip(root, root[1:]))):
		ans += 1
print(ans)


import itertools
(n, m) = map(int, input().split())
p = [[False] * n for i in range(n)]
for i in range(m):
	(a, b) = map(int, input().split())
	a -= 1
	b -= 1
	p[a][b] = True
	p[b][a] = True
ans = 0
for i in itertools.permutations(range(1, n), n - 1):
	list = [0] + [k for k in i]
	if all((p[list[j]][list[j + 1]] == True for j in range(n - 1))):
		ans += 1
print(ans)


(N, M) = map(int, input().split())
path_matrix = []
for n in range(N):
	path_matrix.append([False] * N)
for m in range(M):
	line = map(int, input().split())
	paths = [x - 1 for x in line]
	path_matrix[paths[0]][paths[1]] = True
	path_matrix[paths[1]][paths[0]] = True
visited = [False] * N

def dfs(now, depth):
	if visited[now]:
		return 0
	if depth == N - 1:
		return 1
	visited[now] = True
	total_paths = 0
	for i in range(0, N):
		if path_matrix[now][i]:
			total_paths += dfs(i, depth + 1)
	visited[now] = False
	return total_paths
print(dfs(0, 0))


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


import itertools
(N, M) = map(int, input().split())
E = [[] for _ in range(N)]
for _ in range(M):
	(ta, tb) = map(int, input().split())
	E[ta - 1].append(tb - 1)
	E[tb - 1].append(ta - 1)
ans = 0
for p in itertools.permutations(range(1, N)):
	p = [0] + list(p)
	cond = 1
	for i in range(N - 1):
		if p[i + 1] not in E[p[i]]:
			cond = 0
	if cond:
		ans += 1
print(ans)


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))
print(sum((all((move in edges for move in zip((1,) + p, p))) for p in permutations(range(2, n + 1)))))


import itertools
(N, M) = map(int, input().split())
E = set([tuple(sorted(map(int, input().split()))) for x in range(M)])
cnt = 0
for i in itertools.permutations(range(2, N + 1), N - 1):
	l = [1] + list(i)
	if sum((1 for x in range(N - 1) if tuple(sorted(l[x:x + 2])) in E)) == N - 1:
		cnt += 1
print(cnt)


f = lambda : map(int, input().split())
(n, m) = f()
g = [[0] * n for _ in range(n)]
for i in range(m):
	(a, b) = f()
	g[a - 1][b - 1] = g[b - 1][a - 1] = 1
import itertools as it
c = 0
for t in it.permutations(range(1, n)):
	(p, d) = (0, 1)
	for q in t:
		d *= g[p][q]
		p = q
	c += d
print(c)


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

def walk(node, visited):
	global ret
	tmp = visited + [node]
	if len(tmp) == n:
		ret += 1
	for nd in g[node]:
		if nd not in tmp:
			walk(nd, tmp)
walk(1, [])
print(ret)


(N, M) = map(int, input().split())
edges = [[] for _ in range(N + 1)]
for _ in range(M):
	(a, b) = map(int, input().split())
	edges[a] += [b]
	edges[b] += [a]
candy = [[1]]
for _ in range(N - 1):
	tmp = []
	for c in candy:
		for next in edges[c[-1]]:
			tmp += [c + [next]]
	candy = tmp
print(sum((len(set(c)) == N for c in candy)))


import itertools
(N, M) = map(int, input().split())
X = [[int(a) - 1 for a in input().split()] for _ in range(M)]
Y = [[0] * N for _ in range(N)]
for (a, b) in X:
	Y[a][b] = 1
	Y[b][a] = 1
ans = 0
for A in itertools.permutations(range(1, N)):
	A = [0] + [a for a in A]
	if all([Y[A[i]][A[i + 1]] for i in range(N - 1)]):
		ans += 1
print(ans)


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

def DFS(v):
	if vis == [1] * N:
		return 1
	ret = 0
	for u in edges[v]:
		if vis[u] == 0:
			vis[u] = 1
			ret += DFS(u)
			vis[u] = 0
	else:
		return ret
print(DFS(0))


import itertools
(N, M) = map(int, input().split())
e = set([])
for i in range(M):
	(a, b) = map(int, input().split())
	e.add((a, b))
ans = 0
for i in list(itertools.permutations(range(2, N + 1))):
	a = 1
	for b in i:
		if (a, b) in e or (b, a) in e:
			a = b
			continue
		break
	else:
		ans += 1
print(ans)


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


import sys
from io import StringIO
import unittest
import itertools

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\n1 2\n1 3\n2 3'
		output = '2'
		self.assertIO(input, output)

	def test_入力例_2(self):
		input = '7 7\n1 3\n2 7\n3 4\n4 5\n4 6\n5 6\n6 7'
		output = '1'
		self.assertIO(input, output)

def resolve():
	(N, M) = list(map(int, input().split()))
	P = [list(map(int, input().split())) for _ in range(M)]
	R = itertools.permutations(list(range(1, N + 1)))
	ans = 0
	for r in R:
		flag = True
		r = list(r)
		if r[0] != 1:
			break
		for i in range(1, N):
			for p in P:
				if r[i - 1] == p[0] and r[i] == p[1] or (r[i - 1] == p[1] and r[i] == p[0]):
					break
			else:
				flag = False
		if flag == True:
			ans += 1
	print(ans)

def __starting_point():
	resolve()
__starting_point()


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

def dfs(x, G, seen):
	seen[x] = True
	flag = True
	for i in seen:
		if i == False:
			flag = False
	if flag:
		return 1
	res = 0
	for i in G[x]:
		if seen[i]:
			continue
		res += dfs(i, G, seen)
		seen[i] = False
	return res
print(dfs(0, G, seen))


def OneStrokePath():
	from collections import deque
	import copy
	(n, m) = list(map(int, input().split()))
	graph = [[] for _ in range(n)]
	ans = 0
	for _ in range(m):
		(a, b) = list(map(int, input().split()))
		graph[a - 1].append(b - 1)
		graph[b - 1].append(a - 1)
	q = deque()
	q.append([0, []])
	while q:
		(x0, route0) = q.pop()
		if x0 in route0:
			continue
		route1 = copy.deepcopy(route0)
		route1.append(x0)
		if len(route1) == n:
			ans += 1
		for i in graph[x0]:
			if i in route1:
				continue
			q.append([i, route1])
	print(ans)

def __starting_point():
	OneStrokePath()
__starting_point()


import itertools
(N, M) = map(int, input().split())
(AB, ans) = ([tuple(map(int, input().split())) for _ in range(M)], 0)
for p in itertools.permutations(range(1, N + 1)):
	if p[0] == 1:
		ans += 1
		for i in range(N - 1):
			if not (min(p[i], p[i + 1]), max(p[i], p[i + 1])) in AB:
				ans -= 1
				break
print(ans)


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

def dfs(place):
	checked[place] = 1
	if sum(checked) == N:
		return 1
	ret = 0
	for i in path[place]:
		if checked[i] == 1:
			continue
		ret += dfs(i)
		checked[i] = 0
	return ret
print(dfs(0))


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

def dfs(p, s):
	for i in G[p]:
		if s[i] == '0':
			a = s[:i] + '1' + s[i + 1:]
			dfs(i, a)
	if s == '0' + N * '1':
		l[0] += 1
s = '01' + (N - 1) * '0'
dfs(1, s)
print(l[0])


import itertools
(n, m) = map(int, input().split())
a_list = []
for j in range(m):
	a = list(map(int, input().split()))
	a_list.append(a)
a_list.sort()
b_list = [k for k in itertools.permutations([l for l in range(1, n + 1)]) if k[0] == 1]
cnt = 0
for x in b_list:
	tf_list = []
	for y in range(n - 1):
		tf_list.append([x[y], x[y + 1]] in a_list or [x[y + 1], x[y]] in a_list)
	if all(tf_list) == True:
		cnt += 1
print(cnt)


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

def func(path, p, count):
	if len(path) == n:
		return count + 1
	for i in graph[p]:
		if i in path:
			continue
		count = func(path + [i], i, count)
	return count
print(func([1], 1, 0))


(N, M) = map(int, input().split())
AB = [tuple(map(int, input().split())) for _ in range(M)]
c = 0
rel = {}
for n in range(1, N + 1):
	rel[n] = []
for (a, b) in AB:
	rel[a] += [b]
	rel[b] += [a]

def trase(r):
	global c
	if N == len(r):
		c += 1
		return
	for n in rel[r[-1]]:
		if n in r:
			continue
		trase(r + [n])
for n in rel[1]:
	trase([1] + [n])
print(c)


(n, m) = map(int, input().split())
g = [[] for _ in range(n)]
for _ in range(m):
	(a, b) = map(int, input().split())
	(a, b) = (a - 1, b - 1)
	g[a].append(b)
	g[b].append(a)
ed = [0] * n
ed[0] = 1
ans = [0] * n

def f(x):
	if 0 not in ed:
		ans[x] += 1
		return
	for a in g[x]:
		if ed[a] == 0:
			ed[a] = 1
			f(a)
			ed[a] = 0
f(0)
print(sum(ans))


(N, M) = map(int, input().split(' '))
nm = [[0 for i in range(N)] for j in range(N)]
for i in range(M):
	(x, y) = map(int, input().split(' '))
	nm[x - 1][y - 1] = 1
	nm[y - 1][x - 1] = 1
cnt = [0]

def dfs(V, s):
	V[s] = 1
	if sum(V) == N:
		cnt[0] += 1
	for i in range(N):
		if nm[i][s] == 1 and V[i] == 0:
			dfs(V, i)
	V[s] = 0
dfs([0] * N, 0)
print(cnt[0])


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


import itertools
(n, m) = map(int, input().split())
D = {tuple(sorted(map(int, input().split()))) for i in range(m)}
cnt = 0
for i in itertools.permutations(range(2, n + 1), n - 1):
	li = [1] + list(i)
	cnt += sum((1 for j in zip(li, li[1:]) if tuple(sorted(j)) in D)) == n - 1
print(cnt)


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)


import itertools
(n, m) = map(int, input().split())
g = [[0] * n for _ in range(n)]
for _ in range(m):
	(a, b) = map(int, input().split())
	(a, b) = (a - 1, b - 1)
	g[a][b] = 1
	g[b][a] = 1
a = list(itertools.permutations(range(n)))
ans = 0
for i in a:
	if i[0] != 0:
		break
	for j in range(n - 1):
		if g[i[j]][i[j + 1]] == 0:
			break
	else:
		ans += 1
print(ans)


import itertools as it
(n, m) = list(map(int, input().split()))
a = list((list(map(int, input().split())) for _ in range(m)))
for i in range(len(a)):
	a.append([a[i][1], a[i][0]])
lis = list(it.permutations(list(range(2, n + 1))))
for i in range(len(lis)):
	lis[i] = (1,) + lis[i]
lis2 = []
for i in range(len(lis)):
	lis[i] = list(lis[i])
	lis2.append(lis[i])
ans = 0
for i in range(len(lis2)):
	check = True
	for j in range(len(lis2[i]) - 1):
		if lis2[i][j:j + 2] not in a:
			check = False
	if check:
		ans += 1
print(ans)


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


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

def dfs(i):
	nonlocal ans
	if all(reach[1:]):
		ans += 1
	for j in ma[i]:
		if reach[j] == 1:
			continue
		reach[j] = 1
		dfs(j)
		reach[j] = 0
reach = [0] * (n + 1)
reach[1] = 1
dfs(1)
print(ans)


from itertools import permutations
(n, m) = map(int, input().split())
v = [set() for _ in range(n)]
for i in range(m):
	(ai, bi) = map(int, input().split())
	v[ai - 1].add(bi - 1)
	v[bi - 1].add(ai - 1)
ans = 0
for ci in permutations(range(n)):
	if not ci[0]:
		for i in range(n - 1):
			if not ci[i + 1] in v[ci[i]]:
				break
		else:
			ans += 1
print(ans)


import itertools
(N, M) = map(int, input().split())
edges = {tuple(map(int, input().split())) for _ in range(M)}
paths = itertools.permutations(range(2, N + 1))
ans = 0
for path in paths:
	count = 0
	path = [1] + list(path)
	for edge in zip(path[:-1], path[1:]):
		count += tuple(sorted(edge)) in edges
	ans += count == N - 1
print(ans)


import sys

def dfs(A: list):
	if len(A) == n:
		for i in range(len(A) - 1):
			if A[i + 1] not in node[A[i]]:
				break
			if i == n - 2:
				ans[0] += 1
		return
	for v in range(2, n + 1):
		if v not in A:
			A.append(v)
			dfs(A)
			A.pop()
(n, m) = list(map(int, input().split()))
node = [set() for _ in range(n + 1)]
for x in sys.stdin.readlines():
	(a, b) = list(map(int, x.split()))
	node[a].add(b)
	node[b].add(a)
ans = [0]
dfs([1])
print(ans[0])


from itertools import permutations
(n, m) = map(int, input().split())
paths = set()
for i in range(m):
	(_a, _b) = map(int, input().split())
	paths.add((_a, _b))
	paths.add((_b, _a))
print(sum((all((s in paths for s in zip((1,) + p, p))) for p in permutations(range(2, n + 1)))))


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))
cnt = 0
for p in permutations(range(2, N + 1)):
	cnt += all((move in edges for move in zip((1,) + p, p)))
print(cnt)


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

def dfs(v, seen):
	if seen == [1] * N:
		return 1
	res = 0
	for nv in to[v]:
		if not seen[nv]:
			seen[nv] = 1
			res += dfs(nv, seen)
			seen[nv] = 0
	return res

def main():
	seen = [0] * N
	seen[0] = 1
	print(dfs(0, seen))

def __starting_point():
	main()
__starting_point()


import sys, itertools
load = []
for (i, row) in enumerate(sys.stdin.readlines()):
	if i == 0:
		(n, m) = [int(x) for x in row.split()]
	else:
		load.append({int(x) for x in row.split()})
sum = 0
for one_load in itertools.permutations([i for i in range(1, n + 1)]):
	if one_load[0] != 1:
		continue
	else:
		for (i, dot) in enumerate(one_load):
			if i == 0:
				old_dot = dot
			elif {old_dot, dot} in load:
				old_dot = dot
			else:
				break
		else:
			sum += 1
print(sum)


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

def dfs(V, v):
	_V = [v for v in V]
	_V[v] = 1
	cnt = 0
	if sum(_V) == N:
		return 1
	else:
		for adj in G[v]:
			if _V[adj] == 0:
				cnt += dfs(_V, adj)
		return cnt
print(dfs([0] * N, 0))


def dfs(g, v, depth):
	if seen[v] == True:
		return 0
	if depth == n:
		return 1
	seen[v] = True
	paths = 0
	for next_v in g[v]:
		paths += dfs(g, next_v, depth + 1)
	seen[v] = False
	return paths
(n, m) = map(int, input().split())
g = [[] * (n + 1) for _ in range(n + 1)]
for _ in range(m):
	(a, b) = map(int, input().split())
	g[a].append(b)
	g[b].append(a)
seen = [False] * (n + 1)
print(dfs(g, 1, 1))


from itertools import permutations
(N, M) = map(int, input().split())
g = [[0] * N for _ in range(N)]
for _ in range(M):
	(a, b) = map(int, input().split())
	(a, b) = (a - 1, b - 1)
	g[a][b] = g[b][a] = 1
cnt = 0
for e in permutations(range(1, N)):
	for (a, b) in zip([0] + list(e[:-1]), e):
		if not g[a][b]:
			break
	else:
		cnt += 1
print(cnt)


import itertools
from collections import deque
(N, M) = map(int, input().split())
table = [[0] * N for _ in range(N)]
ans = 0
for i in range(M):
	(a, b) = map(int, input().split())
	a -= 1
	b -= 1
	table[a][b] = 1
	table[b][a] = 1
p = [i for i in range(1, N)]
q = list(itertools.permutations(p))
s = deque()
for i in range(len(q)):
	x = 0
	flag = 0
	for y in q[i]:
		if table[x][y] == 0:
			flag = 1
			break
		x = y
	if flag == 0:
		ans += 1
print(ans)


import itertools as it
(N, M) = map(int, input().split())
ab = tuple((set(map(int, input().split())) for _ in range(M)))
P = it.permutations(range(1, N + 1), N)
res = 0
for p in P:
	if p[0] == 1:
		for i in range(N - 1):
			if not set({p[i], p[i + 1]}) in ab:
				break
		else:
			res += 1
print(res)


from itertools import groupby, accumulate, product, permutations, combinations
import numpy as np
(N, M) = map(int, input().split())
adj = np.zeros((N, N), np.int64)
for i in range(M):
	(a, b) = map(lambda x: int(x) - 1, input().split())
	adj[a, b] = 1
	adj[b, a] = 1
ans = 0
for per in permutations(range(1, N), N - 1):
	if adj[0, per[0]] == 0:
		continue
	for i in range(N - 2):
		if adj[per[i], per[i + 1]] == 0:
			break
	else:
		ans += 1
print(ans)


(N, M) = map(int, input().split())
adj = [[] for _ in range(N)]
for _ in range(M):
	(i, j) = map(int, input().split())
	adj[i - 1].append(j - 1)
	adj[j - 1].append(i - 1)
ans = 0

def dfs(path):
	if len(path) == N:
		global ans
		ans += 1
	for next in adj[path[-1]]:
		if next not in path:
			dfs(path + [next])
dfs([0])
print(ans)


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


from itertools import permutations
(n, m) = map(int, input().split())
D = [[0] * n for i in range(n)]
for i in range(m):
	(a, b) = map(int, input().split())
	D[a - 1][b - 1] = 1
	D[b - 1][a - 1] = 1
cnt = 0
for a in permutations(range(n)):
	if a[0] != 0:
		break
	tmp = 1
	for i in range(n - 1):
		tmp = tmp * D[a[i]][a[i + 1]]
	cnt += tmp
print(cnt)


from itertools import permutations
(N, M) = map(int, input().split())
E = [[False] * N for _ in range(N)]
for _ in range(M):
	(a, b) = map(lambda x: int(x) - 1, input().split())
	E[a][b] = E[b][a] = True
ans = 0
for t in permutations(range(1, N)):
	pv = 0
	for v in t:
		if not E[pv][v]:
			break
		pv = v
	else:
		ans += 1
print(ans)


import itertools
(n, m) = map(int, input().split())
emp = [[] for i in range(n)]
count = 0
for i in range(m):
	(a, b) = map(int, input().split())
	emp[a - 1].append(b - 1)
	emp[b - 1].append(a - 1)
nlis = [i for i in range(n)]
perm = list(itertools.permutations(nlis))
for one_case in perm:
	if one_case[0] == 0:
		cou = 0
		for i in range(n - 1):
			if one_case[i + 1] in emp[one_case[i]]:
				cou += 1
			if cou == n - 1:
				count += 1
print(count)


from itertools import permutations
(N, M) = map(int, input().split())
AB = set([tuple(sorted(map(int, input().split()))) for _ in range(M)])
answer = 0
for pattern in permutations(range(2, N + 1), N - 1):
	pattern = [1] + list(pattern)
	for i in zip(pattern[:-1], pattern[1:]):
		if tuple(sorted(i)) not in AB:
			break
	else:
		answer += 1
print(answer)


from itertools import permutations
(n, m) = map(int, input().split())
e = [[] for _ in range(n)]
for _ in range(m):
	(a, b) = map(int, input().split())
	e[a - 1] += [b - 1]
	e[b - 1] += [a - 1]

def dfs(now, vis):
	vis += [now]
	if len(vis) == n:
		return 1
	res = 0
	for to in e[now]:
		if to not in vis:
			res += dfs(to, vis[:])
	return res
print(dfs(0, []))


from itertools import permutations
(n, m) = map(int, input().split())
d = [[] for _ in range(n)]
ans = 0
for i in range(m):
	(a, b) = map(int, input().split())
	d[a - 1].append(b - 1)
	d[b - 1].append(a - 1)
l = permutations(range(1, n))
for i in l:
	pre = 0
	c = 0
	for j in i:
		if not j in d[pre]:
			break
		c += 1
		pre = j
	if c == n - 1:
		ans += 1
print(ans)


from itertools import *
(N, M) = map(int, input().split())
S = [list(map(int, input().split())) for m in range(M)]
a = 0
for p in permutations(range(1, N + 1)):
	f = True
	if p[0] == 1:
		for n in range(N - 1):
			if sorted([p[n], p[n + 1]]) not in S:
				f = False
		if f:
			a += 1
print(a)


from itertools import permutations
(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, b) = (a - 1, b - 1)
	path[a][b] = path[b][a] = True
	ans = 0
	for i in 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)


(N, M) = map(int, input().split())
p = [list(map(int, input().split())) for i in range(M)]
import itertools
v = list(map(list, itertools.permutations(range(2, N + 1), N - 1)))
cnt = 0
for i in range(len(v)):
	vit = True
	v_i = [1] + v[i]
	for j in range(N - 1):
		if sorted(v_i[j:j + 2]) not in p:
			vit = False
	if vit:
		cnt += 1
print(cnt)


import itertools
(N, M) = list(map(int, input().split()))
graph = [[False] * N for i in range(N)]
for i in range(M):
	(a, b) = [int(x) - 1 for x in input().split()]
	graph[a][b] = True
	graph[b][a] = True
lst = [i - 1 for i in range(N)]
cnt = 0
for v in itertools.permutations(lst, N):
	if v[0] != 0:
		continue
	for i in range(N - 1):
		if graph[v[i]][v[i + 1]] == False:
			break
		if i == N - 2:
			cnt += 1
print(cnt)


(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)
from itertools import permutations
c = 0
for p in permutations(range(1, N)):
	pi = 0
	for pj in p:
		if not pj in G[pi]:
			break
		pi = pj
	else:
		c += 1
print(c)


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

def dfs(now, depth):
	if visited[now]:
		return 0
	if depth == N:
		return 1
	visited[now] = 1
	total_paths = 0
	for i in range(1, N + 1):
		if path[now][i]:
			total_paths += dfs(i, depth + 1)
	visited[now] = 0
	return total_paths
print(dfs(1, 1))


from itertools import permutations
(n, m) = map(int, input().split())
ans = 0
s = [list(map(int, input().split())) for i in range(m)]
t = list(permutations(list(range(1, n + 1))))
for i in range(len(t)):
	flag = True
	if t[i][0] != 1:
		continue
	for j in range(n - 1):
		a = sorted([t[i][j], t[i][j + 1]])
		if a not in s:
			flag = False
	if flag:
		ans += 1
print(ans)


from itertools import permutations
(N, M, *L) = map(int, open(0).read().split())
dic = [[] for i in range(N + 1)]
for (a, b) in zip(*[iter(L)] * 2):
	dic[a].append(b)
	dic[b].append(a)
ans = 0
for l in permutations(range(2, N + 1)):
	l = [1] + list(l)
	for i in range(N - 1):
		if l[i + 1] not in dic[l[i]]:
			break
	else:
		ans += 1
print(ans)


def dfs(x, l):
	if l.count(False) == 0:
		return 1
	cnt = 0
	for i in a[x]:
		if not l[i]:
			cnt += dfs(i, [[True] if j == i else l[j] for j in range(n)])
	return cnt
(n, m) = map(int, input().split())
a = [[] for i in range(n)]
for i in range(m):
	x = list(map(int, input().split()))
	a[x[0] - 1].append(x[1] - 1)
	a[x[1] - 1].append(x[0] - 1)
print(dfs(0, [True] + [False] * (n - 1)))


(N, M) = map(int, input().split())
D = {}
for i in range(M):
	(a, b) = map(int, input().split())
	if a not in D:
		D[a] = set()
	if b not in D:
		D[b] = set()
	D[a].add(b)
	D[b].add(a)
if 1 not in D or len(D) != N:
	print(0)
else:
	S = set(D.keys())
	ans = 0
	task = [(1, set())]
	while len(task) > 0:
		pos = 0
		log = set()
		(pos, log) = task.pop(0)
		log.add(pos)
		for i in D[pos]:
			if i not in log:
				task.append((i, log.copy()))
		else:
			if log == S:
				ans += 1
	print(ans)


from itertools import permutations
(n, m) = map(int, input().split())
con = [[0] * n for _ in range(n)]
for _ in range(m):
	(a, b) = map(int, input().split())
	con[a - 1][b - 1] = con[b - 1][a - 1] = 1
ans = 0
for p in permutations(range(n)):
	if p[0] != 0:
		continue
	if all((con[x][y] for (x, y) in zip(p, p[1:]))):
		ans += 1
print(ans)


from itertools import permutations
(n, m) = map(int, input().split())
edges = {tuple(map(int, input().split())) for _ in range(m)}
ans = 0
for route in permutations(range(2, n + 1)):
	route = [1] + list(route)
	ans += len([1 for edge in zip(route, route[1:]) if tuple(sorted(edge)) in edges]) == n - 1
print(ans)


from itertools import permutations
(N, M) = list(map(int, input().split()))
l = [list(map(int, input().split())) for _ in range(M)]
graph = [[False] * (N + 1) for _ in range(N + 1)]
for (i, j) in l:
	graph[i][j] = True
	graph[j][i] = True
pattern = permutations(list(range(1, N + 1)))
cnt = 0
for i in pattern:
	flag = True
	if i[0] != 1:
		continue
	for j in range(N - 1):
		if graph[i[j]][i[j + 1]] == False:
			flag = False
			break
	if flag:
		cnt += 1
print(cnt)


import itertools
(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))
answer = 0
for p in itertools.permutations(range(1, N + 1)):
	if p[0] != 1:
		continue
	bl = True
	for i in range(N - 1):
		if (p[i], p[i + 1]) not in edges:
			bl = False
	if bl:
		answer += 1
print(answer)


import copy
(N, M) = map(int, input().split())
C = {}
for m in range(M):
	(a, b) = list(map(int, input().split()))
	C[b] = C.get(b, []) + [a]
	C[a] = C.get(a, []) + [b]

def Search(a, check):
	ans = 0
	if all(check):
		return 1
	else:
		check[a - 1] = 1
		for b in C[a]:
			tmp = copy.deepcopy(check)
			if check[b - 1] != 1:
				tmp[b - 1] = 1
				ans += Search(b, tmp)
		return ans
print(Search(1, [0] * N))


import itertools
(n, m) = map(int, input().split())
a = []
c = 0
for _ in [0] * m:
	a += [list(map(int, input().split()))]
for x in list(itertools.permutations(range(2, n + 1))):
	y = [1] + list(x)
	f = True
	for i in range(1, n):
		if not [y[i - 1], y[i]] in a and (not [y[i], y[i - 1]] in a):
			f = False
			break
	if f:
		c += 1
print(c)


from collections import deque
(n, m) = list(map(int, input().split()))
g = [[] for _ in range(n)]
prev = [0] * n
for i in range(m):
	(a, b) = list(map(int, input().split()))
	g[a - 1].append(b)
	g[b - 1].append(a)
count = 0
prev[0] = 1

def keiro(pre, q, now):
	nonlocal count
	if len(q) == 0:
		return
	now = q.popleft()
	for no in g[now - 1]:
		if pre[no - 1] == 0:
			pre_1 = pre.copy()
			pre_1[no - 1] = 1
			if sum(pre_1) == n:
				count += 1
				return
			q.append(no)
			keiro(pre_1, q, no)
		else:
			keiro(pre, q, no)
keiro(prev, deque([1]), 1)
print(count)


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

def dfs(i, used):
	if len(used) == N:
		return 1
	ans = 0
	for j in edges[i]:
		if j not in used:
			ans += dfs(j, used + [j])
	return ans
print(dfs(0, [0]))


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

def search(i, visited):
	global cnt
	if len(visited) == n:
		cnt += 1
	for v in to[i]:
		if v not in visited:
			search(v, visited + [v])
search(0, [0])
print(cnt)


(n, m) = map(int, input().split())
edges = [[] for i in range(n)]
for i in range(m):
	(s, t) = map(int, input().split())
	edges[s - 1].append(t - 1)
	edges[t - 1].append(s - 1)
cnt = 0
V = [0] * n

def dfs(V, s):
	global cnt
	V = V[:]
	V[s] = 1
	if sum(V) == n:
		cnt += 1
	else:
		for v in edges[s]:
			if V[v] == 0:
				dfs(V, v)
dfs(V, 0)
print(cnt)


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

def dfs(x, used):
	if len(used) == N:
		return 1
	ans = 0
	for i in D[x]:
		if i not in used:
			ans += dfs(i, used + [i])
	return ans
print(dfs(0, [0]))


import itertools
(n, m) = list(map(int, input().split()))
routes = list(itertools.permutations([i for i in range(2, n + 1)]))
nodes = {}
ans = 0
for i in range(1, n + 1):
	nodes[i] = []
for _ in range(m):
	(a, b) = list(map(int, input().split()))
	nodes[a].append(b)
	nodes[b].append(a)
for i in range(len(routes)):
	jud = 1
	if routes[i][0] not in nodes[1]:
		jud = 0
	for j in range(n - 2):
		if routes[i][j + 1] not in nodes[routes[i][j]]:
			jud = 0
	ans += jud
print(ans)


from itertools import permutations
(n, m) = map(int, input().split())
G = [[] for _ in range(n)]
for _ in range(m):
	(a, b) = map(int, input().split())
	a -= 1
	b -= 1
	G[a].append(b)
	G[b].append(a)
ans = 0
for P in permutations(range(n), n):
	f = 1
	if P[0] != 0:
		continue
	for i in range(n - 1):
		if P[i + 1] in G[P[i]]:
			f *= 1
		else:
			f *= 0
	if f == 1:
		ans += 1
print(ans)


(N, M) = [int(a) for a in input().split()]
edges = {i: [] for i in range(1, N + 1)}
for i in range(M):
	(a, b) = [int(a) for a in input().split()]
	edges[a].append(b)
	edges[b].append(a)

def search(lst):
	if len(lst) == N:
		return 1
	else:
		a = lst[-1]
		next = [n for n in edges[a] if n not in lst]
		if len(next) == 0:
			return 0
		tot = 0
		for n in next:
			tot += search(lst + [n])
		return tot
ans = search([1])
print(ans)


import itertools
(n, m) = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(m)]
p = itertools.permutations(range(2, n + 1), n - 1)
cnt = 0
for v in p:
	if [1, v[0]] not in ab and [v[0], 1] not in ab:
		continue
	elif all(([n0, n1] in ab or [n1, n0] in ab for (n0, n1) in zip(v, v[1:]))):
		cnt += 1
print(cnt)


(n, m) = map(int, input().split())
road = [[] for _ in range(n + 1)]
for i in range(m):
	(a, b) = map(int, input().split())
	road[a].append(b)
	road[b].append(a)
dp = [[0] * (n + 1) for _ in range(2 ** n)]
dp[1][1] = 1
for i in range(1, 2 ** n):
	for j in range(1, n + 1):
		for k in road[j]:
			if not i >> k - 1 & 1:
				dp[i + 2 ** (k - 1)][k] += dp[i][j]
print(sum(dp[2 ** n - 1]))


import itertools
(n, m) = [int(x) for x in input().split()]
li = []
for _ in range(m):
	li.append({int(x) for x in input().split()})
a = itertools.permutations(range(2, n + 1))
count = 0
for i in a:
	x = [1] + list(i)
	for i in range(n - 1):
		if not {x[i], x[i + 1]} in li:
			break
	else:
		count += 1
print(count)


from itertools import permutations
(N, M) = map(int, input().split())
AB = [tuple(map(int, input().split())) for _ in range(M)]
m = [set() for _ in range(27)]
for (a, b) in AB:
	m[a].add(b)
	m[b].add(a)

def main():
	ans = []

	def traverse(n, visits):
		visits = visits | set([n])
		if len(visits) == N:
			ans.append(1)
			return
		for c in m[n] - visits:
			traverse(c, visits)
	traverse(1, set())
	return len(ans)
print(main())


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


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


(n, m) = map(int, input().split())
G = [[0] * n for i in range(n)]
for i in range(m):
	(a, b) = map(int, input().split())
	G[a - 1][b - 1] = G[b - 1][a - 1] = 1
from itertools import permutations
ans = 0
p = list(permutations([x for x in range(1, n)]))
for pp in p:
	ok = True
	t = [0] + list(pp)
	for i in range(1, n):
		if G[t[i - 1]][t[i]] == 0:
			ok = False
	if ok:
		ans += 1
print(ans)


f = lambda : map(int, input().split())
(n, m) = f()
g = [set() for _ in range(n)]
for i in range(m):
	(a, b) = f()
	g[a - 1].add(b - 1)
	g[b - 1].add(a - 1)
import itertools as it
c = 0
for t in it.permutations(range(1, n)):
	p = 0
	for q in t:
		if q not in g[p]:
			break
		p = q
	else:
		c += 1
print(c)


def abc054c_one_stroke_path():
	import itertools
	(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)
	pattern = itertools.permutations(range(2, n + 1))
	cnt = 0
	for p in pattern:
		p_m = [1] + list(p)
		for i in range(n - 1):
			if p_m[i + 1] not in e[p_m[i]]:
				break
		else:
			cnt += 1
	print(cnt)
abc054c_one_stroke_path()


from itertools import permutations
(N, M) = list(map(int, input().split()))
e = [list(map(int, input().split())) for i in range(M)]
a = 0
for p in permutations(range(1, N + 1)):
	f = True
	if p[0] == 1:
		for i in range(N - 1):
			if sorted([p[i], p[i + 1]]) not in e:
				f = False
		if f:
			a += 1
print(a)


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


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


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

def dfs(i, l1):
	if len(l1) == n:
		lans.append(l1)
		return
	for j in l[i]:
		if j in l1:
			pass
		else:
			l2 = l1 + [j]
			dfs(j, l2)
	return
dfs(1, [1])
print(len(lans))


(n, m) = map(int, input().split())
q = []
for i in range(m):
	(a, b) = map(int, input().split())
	q += [[a, b], [b, a]]
p = [[1]]
count = 0
while p:
	p1 = p.pop()
	if len(p1) == n:
		count += 1
	else:
		for (i, j) in q:
			if i == p1[-1] and j not in p1:
				p.append(p1 + [j])
print(count)


from typing import List, Tuple

def main():
	(n, m) = list(map(int, input().split()))
	g = []
	for _ in range(m):
		(a, b) = list(map(int, input().split()))
		g.append((a, b))
	print(osp(n, g))

def osp(n: int, g: List[Tuple[int, int]]) -> int:
	v = [False] * n
	g = set(g)
	return dfs(0, v, n, g)

def dfs(i, v, n, g):
	v[i] = True
	if all(v):
		v[i] = False
		return 1
	cnt = 0
	for j in range(n):
		if v[j]:
			continue
		if not ((i + 1, j + 1) in g or (j + 1, i + 1) in g):
			continue
		cnt += dfs(j, v, n, g)
	v[i] = False
	return cnt

def __starting_point():
	main()
__starting_point()


import itertools
(n, m) = map(int, input().split())
ab = [list(map(int, input().split())) for i in range(m)]
graph = [list() for i in range(n)]
ans = 0
for (a, b) in ab:
	a -= 1
	b -= 1
	graph[a].append(b)
	graph[b].append(a)
for i in itertools.permutations(range(1, n)):
	now = 0
	for j in i:
		if not j in graph[now]:
			break
		now = j
	else:
		ans += 1
print(ans)


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

def dfs(node):
	if sum([1 for v in visited if v]) == N:
		return 1
	ret = 0
	for n in graph[node]:
		if visited[n]:
			continue
		visited[n] = True
		ret += dfs(n)
		visited[n] = False
	return ret
graph = [[] for _ in range(N)]
for _ in range(M):
	(a, b) = list(map(int, input().split()))
	graph[a - 1].append(b - 1)
	graph[b - 1].append(a - 1)
visited = [False for _ in range(N)]
visited[0] = True
print(dfs(0))


(N, M) = map(int, input().split())
G = [[False] * N for i in range(N)]
for i in range(M):
	(a, b) = map(int, input().split())
	G[a - 1][b - 1] = G[b - 1][a - 1] = True
V = [False] * N
V[0] = True

def dfs(v):
	if not False in V:
		return 1
	ret = 0
	for i in range(N):
		if not G[v][i]:
			continue
		if V[i]:
			continue
		V[i] = True
		ret += dfs(i)
		V[i] = False
	return ret
print(dfs(0))


from itertools import permutations as per
(n, m) = map(int, input().split())
g = [[] for i 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)
c = 0
for i in per(range(2, n + 1)):
	cur = 1
	f = 1
	for j in range(n - 1):
		(pre, cur) = (cur, i[j])
		if cur - 1 not in g[pre - 1]:
			f = 0
			break
	c += f
print(c)


from itertools import permutations
(n, m) = map(int, input().split())
edges = [[False for _ in range(n)] for _ in range(n)]
for _ in range(m):
	(a, b) = map(int, input().split())
	(a, b) = (a - 1, b - 1)
	edges[a][b] = edges[b][a] = True
ans = 0
for l in permutations(range(1, n), n - 1):
	l = [0] + list(l)
	if all((edges[l[i]][l[i + 1]] for i in range(n - 1))):
		ans += 1
print(ans)


from collections import deque
(N, M) = map(int, input().split())
T = [[] for i in range(N + 1)]
for i in range(M):
	(a, b) = map(int, input().split())
	T[a].append(b)
	T[b].append(a)
Q = deque([(1, [1])])
ans = 0
while Q:
	(p, V) = Q.pop()
	if len(V) == N:
		ans += 1
		continue
	for c in T[p]:
		if not c in V:
			Q.append((c, V + [c]))
print(ans)


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


from itertools import permutations
(n, m) = map(int, input().split())
es = set()
for _ in range(m):
	(u, v) = map(int, input().split())
	(u, v) = (u - 1, v - 1)
	es |= {(u, v), (v, u)}
res = 0
for p in permutations(range(n)):
	if p[0] != 0:
		continue
	if all(((p[i], p[i + 1]) in es for i in range(n - 1))):
		res += 1
print(res)


import itertools
(n, m) = map(int, input().split())
s = set()
for i in range(m):
	(a, b) = map(int, input().split())
	s.add((a, b))
	s.add((b, a))
ans = 0
for i in itertools.permutations(range(2, n + 1)):
	genzai = 1
	for j in range(len(i)):
		if (genzai, i[j]) not in s:
			break
		genzai = i[j]
	else:
		ans += 1
print(ans)


from itertools import permutations as p
from collections import defaultdict as dd
(n, m) = map(int, input().split())
d = dd(list)
for _ in range(m):
	(a, b) = map(int, input().split())
	d[a].append(b)
	d[b].append(a)
d = dict(d)
ans = 0
for i in p(range(2, n + 1)):
	pos = 1
	for j in i:
		if not j in d[pos]:
			break
		pos = j
	else:
		ans += 1
print(ans)


import sys
sys.setrecursionlimit(10 ** 9)

def dfs(s, check):
	if len(check) == n:
		if len(set(check)) == n:
			return 1
		else:
			return 0
	ans = 0
	for i in edge[s]:
		ans += dfs(i, check + [i])
	return ans
(n, m) = map(int, input().split())
edge = [[] for _ in range(n + 1)]
for i in range(m):
	(s, t) = map(int, input().split())
	edge[s].append(t)
	edge[t].append(s)
print(dfs(1, [1]))


import sys
sys.setrecursionlimit(10 ** 6)
(N, M) = list(map(int, input().split()))
graph = [[] for _ in range(N)]
for i in range(M):
	(a, b) = [int(x) - 1 for x in input().split()]
	graph[a].append(b)
	graph[b].append(a)

def dfs(cur, visited):
	if visited == (1 << N) - 1:
		return 1
	res = 0
	for to in graph[cur]:
		if not visited >> to & 1:
			res += dfs(to, visited | 1 << to)
	return res
print(dfs(0, 1))


from itertools import permutations
(n, m) = map(int, input().split())
G = [[] for _ in range(n)]
for _ in range(m):
	(a, b) = map(int, input().split())
	a -= 1
	b -= 1
	G[a].append(b)
	G[b].append(a)
ans = 0
for p in permutations(range(1, n)):
	now = 0
	for nxt in p:
		if nxt not in G[now]:
			break
		now = nxt
	else:
		ans += 1
print(ans)


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

def dfs(now, visited=[]):
	if len(visited) == n:
		v.append([visited])
		return
	for j in ans[now]:
		if j not in visited:
			dfs(j, visited + [j])
dfs(0, [0])
print(len(v))


import itertools
(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)
p = list(itertools.permutations(range(0, N)))
ans = 0
for pair in p:
	if pair[0] != 0:
		continue
	ok = True
	for (node1, node2) in zip(pair[0:], pair[1:]):
		if node1 not in g[node2]:
			ok = False
			break
	if ok:
		ans += 1
print(ans)


import sys
import itertools
sys.setrecursionlimit(10 ** 6)
(N, M) = list(map(int, input().split()))
tmp = [x for x in range(1, N)]
Cases = itertools.permutations(tmp)
G = [[] for _ in range(N)]
seen = [0] * N
for _ in range(M):
	(a, b) = list(map(int, input().split()))
	a -= 1
	b -= 1
	G[a].append(b)
	G[b].append(a)

def solve(v, case, cnt, N):
	if cnt == N - 1:
		return True
	for nv in G[v]:
		if nv == case[cnt]:
			return solve(nv, case, cnt + 1, N)
	return False
ans = 0
for case in Cases:
	if solve(0, case, 0, N):
		ans += 1
print(ans)


(n, m) = map(int, input().split())
D = [list() 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)
d = [0] * n
d[0] = 1
cnt = 0

def dfs(x):
	global cnt
	if all(d):
		cnt += 1
		return
	for i in D[x]:
		if d[i] == 0:
			d[i] = 1
			dfs(i)
			d[i] = 0
dfs(0)
print(cnt)


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

def search(x):
	a = 0
	E[x] = 1
	if 0 not in E:
		a += 1
	for g in G[x]:
		if E[g] == 0:
			a += search(g)
	E[x] = 0
	return a
print(search(0))


import itertools
(n, m) = map(int, input().split())
l = [list(map(int, input().split())) for i in range(m)]
s = list(itertools.permutations(range(1, n + 1)))
count = 0
for lis in s:
	flag = False
	if lis[0] == 1:
		if all(([lis[i], lis[i + 1]] in l or [lis[i + 1], lis[i]] in l for i in range(n - 1))):
			count += 1
print(count)


from itertools import permutations as perm
(n, m) = map(int, input().split())
coor = [[False] * n for _ in range(n)]
for i in range(m):
	(a, b) = map(int, input().split())
	(a, b) = (a - 1, b - 1)
	coor[a][b] = True
	coor[b][a] = True
ll = list(range(n))
res = 0
for l in perm(ll):
	if l[0] != 0:
		continue
	for (i, j) in zip(l, l[1:]):
		if not coor[i][j]:
			break
	else:
		res += 1
print(res)


import itertools
(N, M) = map(int, input().split())
lst = [set() for _ in range(N + 1)]
for _ in range(M):
	(a, b) = map(int, input().split())
	lst[a].add(b)
	lst[b].add(a)
ans = 0
for t in itertools.permutations(range(2, N + 1)):
	tmp = 1
	for x in t:
		if x not in lst[tmp]:
			break
		tmp = x
	else:
		ans += 1
print(ans)


from itertools import permutations
(N, M) = map(int, input().split())
E = [set() for _ in range(N)]
for _ in range(M):
	(a, b) = map(int, input().split())
	E[a - 1].add(b - 1)
	E[b - 1].add(a - 1)
ans = 0
for p in permutations([i for i in range(1, N)]):
	i = 0
	for j in p:
		if j not in E[i]:
			break
		i = j
	else:
		ans += 1
print(ans)


import itertools
(n, m) = [int(x) for x in input().split()]
edges = set((tuple((int(x) for x in input().split())) for _ in range(m)))
print(sum((1 if all((p in edges or tuple(reversed(p)) in edges for p in [(1, path[0])] + list(zip(path, path[1:])))) else 0 for path in itertools.permutations(range(2, n + 1)))))


(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)
ans = 0
passed = [0]
n = 0
s = [[n, passed]]
while s:
	(n, passed) = s.pop()
	if len(passed) == N:
		ans += 1
	else:
		for i in g[n]:
			if i not in passed:
				s.append([i, passed + [i]])
print(ans)


(n, m) = map(int, input().split())
visit = [False] * n
r = [[] for _ in range(n)]
for i in range(m):
	(a, b) = map(lambda x: int(x) - 1, input().split())
	r[a].append(b)
	r[b].append(a)

def dfs(x, v):
	if v[x]:
		return
	v = list(v)
	v[x] = True
	if all(v):
		nonlocal ans
		ans += 1
		return
	for y in r[x]:
		dfs(y, v)
ans = 0
dfs(0, [False] * n)
print(ans)


import itertools
(N, M) = map(int, input().split())
s = [list(map(int, input().split())) for _ in range(M)]
lst = [x for x in range(1, N + 1)]
l = itertools.permutations(lst)
ans = 0
cnt = 0
for num in l:
	if num[0] == 1:
		for j in range(N - 1):
			if [num[j], num[j + 1]] in s or [num[j + 1], num[j]] in s:
				cnt += 1
	if cnt == N - 1:
		ans += 1
		cnt = 0
	else:
		cnt = 0
print(ans)


from itertools import permutations
(N, M) = map(int, input().split())
G = [[0] * N for _ in range(N)]
for i in range(M):
	(a, b) = map(int, input().split())
	G[a - 1][b - 1] = 1
	G[b - 1][a - 1] = 1
perms = permutations(range(1, N))
ans = 0
for perm in perms:
	now = 0
	for v in perm:
		if G[now][v] == 0:
			break
		now = v
	else:
		ans += 1
print(ans)


from itertools import permutations
(N, M) = map(int, input().split())
Alist = [list(map(int, input().split())) for i in range(M)]
graph = [[False] * (N + 1) for i in range(N + 1)]
for (i, j) in Alist:
	graph[i][j] = True
	graph[j][i] = True
route = permutations(range(1, N + 1))
count = 0
for i in route:
	flag = True
	if i[0] != 1:
		continue
	for j in range(N - 1):
		if graph[i[j]][i[j + 1]] == False:
			flag = False
			break
	if flag == True:
		count += 1
print(count)


from networkx import *
(N, M) = map(int, input().split())
A = [list(map(int, input().split())) for m in range(M)]
G = Graph(A)
ans = 0
for n in range(2, N + 1):
	for p in all_simple_paths(G, 1, n):
		if len(p) == N:
			ans += 1
print(ans)


from itertools import permutations
(N, M) = map(int, input().split())
E = [[0] * (N + 1) for _ in range(N + 1)]
for _ in range(M):
	(a, b) = map(int, input().split())
	E[a][b] = 1
	E[b][a] = 1
P = permutations([x for x in range(2, N + 1)])
K = 0
for p in P:
	Q = [1] + list(p)
	F = 1
	for k in range(N - 1):
		F *= E[Q[k]][Q[k + 1]]
	K += F
print(K)


import itertools
(n, m) = map(int, input().split())
l = [[0] * n for i in range(n)]
for i in range(m):
	(a, b) = map(int, input().split())
	l[a - 1][b - 1] = 1
	l[b - 1][a - 1] = 1
d = [int(i) + 1 for i in range(n)]
ans = chk = 0
for i in list(itertools.permutations(d, n)):
	chk = 1
	if i[0] != 1:
		continue
	for j in range(n - 1):
		chk *= l[i[j + 1] - 1][i[j] - 1]
	ans += chk
print(ans)


(n, m) = map(int, input().split())
l = [list(map(int, input().split())) for _ in range(m)]
p = [list() for i in range(n + 1)]
for (a, b) in l:
	p[a].append(b)
	p[b].append(a)
q = [(1, [1])]
ans = 0
while len(q) != 0:
	(x, v) = q.pop(0)
	if len(v) == n:
		ans += 1
		continue
	for i in p[x]:
		if i in v:
			continue
		q.append((i, v + [i]))
print(ans)


(n, m) = map(int, input().split())
ab = [list(map(int, input().split())) for _ in [0] * m]
g = [[] for _ in [0] * n]
[g[a - 1].append(b - 1) for (a, b) in ab]
[g[b - 1].append(a - 1) for (a, b) in ab]
from itertools import permutations
cnt = 0
for i in permutations(range(1, n)):
	i = (0,) + i
	for j in range(n - 1):
		if i[j + 1] not in g[i[j]]:
			break
	else:
		cnt += 1
print(cnt)


from itertools import permutations as per
(ty, he) = map(int, input().split())
l = [set(map(int, input().split())) for i in range(he)]
ans = 0
for g in per(range(2, ty + 1)):
	co = [1] + list(g)
	for sd in zip(co, co[1:]):
		if set(sd) not in l:
			break
	else:
		ans += 1
print(ans)


import itertools

def one_stroke_path():
	(N, M) = list(map(int, input().split()))
	a = list()
	b = list()
	for _ in range(M):
		(A, B) = list(map(int, input().split()))
		a.append(A)
		b.append(B)
	permutations_list = itertools.permutations([x for x in range(1, N + 1)])
	count = 0
	for one_case in permutations_list:
		is_ok = False
		if one_case[0] == 1:
			for i in range(len(one_case) - 1):
				for j in range(M):
					if one_case[i] == a[j] and one_case[i + 1] == b[j] or (one_case[i] == b[j] and one_case[i + 1] == a[j]):
						is_ok = True
						break
					else:
						is_ok = False
				if is_ok == False:
					break
		else:
			is_ok = False
		if is_ok:
			count += 1
	return count
result = one_stroke_path()
print(result)


import sys
readline = sys.stdin.readline
(N, M) = map(int, readline().split())
G = [[] for i in range(N)]
for i in range(M):
	(a, b) = map(int, readline().split())
	G[a - 1].append(b - 1)
	G[b - 1].append(a - 1)
stack = []
stack.append([0, set()])
ans = 0
while stack:
	(v, visited) = stack.pop()
	visited.add(v)
	if len(visited) == N:
		ans += 1
		continue
	for child in G[v]:
		if child in visited:
			continue
		visited_c = visited.copy()
		stack.append([child, visited_c])
print(ans)


(N, M) = map(int, input().split())
path_matrix = []
for i in range(N):
	path_matrix.append([False] * N)
for i in range(M):
	(a, b) = map(int, input().split())
	path_matrix[a - 1][b - 1] = True
	path_matrix[b - 1][a - 1] = True
view = [False] * N

def path(x, depth):
	if view[x - 1]:
		return False
	if depth == N - 1:
		return True
	view[x - 1] = True
	total_ans = 0
	for i in range(N):
		if path_matrix[x - 1][i]:
			total_ans += int(path(i + 1, depth + 1))
	view[x - 1] = False
	return total_ans
print(path(1, 0))


from collections import defaultdict as dd
from itertools import permutations as pe
d = dd(list)
(n, m) = map(int, input().split())
for _ in range(m):
	(a, b) = map(int, input().split())
	d[a].append(b)
	d[b].append(a)
c = 0
for i in pe(range(2, n + 1)):
	a = d[1]
	f = True
	for j in i:
		if not j in a:
			f = False
			break
		else:
			a = d[j]
	if f:
		c += 1
print(c)


import itertools
(n, m) = map(int, input().split())
l = [list(map(int, input().split())) for _ in range(m)]
p = list(itertools.permutations(list(range(2, n + 1))))
ans = 0
for i in p:
	tmp = 1
	for j in range(n - 1):
		if [tmp, i[j]] in l or [i[j], tmp] in l:
			tmp = i[j]
		else:
			break
		if j == n - 2:
			ans += 1
print(ans)


from itertools import permutations
(n, m) = map(int, input().split())
path = set()
for _ in range(m):
	(u, v) = map(int, input().split())
	path |= {(u - 1, v - 1), (v - 1, u - 1)}
print(sum((all(((u, v) in path for (u, v) in zip(p, p[1:]))) for p in permutations(range(n)) if p[0] == 0)))


def dfs(place, number, checkedList, path):
	checkedList[place] = 1
	if sum(checked) == number:
		return 1
	pathNumber = 0
	for i in path[place]:
		if checkedList[i] == 1:
			continue
		pathNumber += dfs(i, number, checkedList, path)
		checkedList[i] = 0
	return pathNumber
(n, m) = map(int, input().split())
checked = [0] * 8
path = [[] for _ in range(8)]
for i in range(m):
	(a, b) = map(int, input().split())
	path[a - 1].append(b - 1)
	path[b - 1].append(a - 1)
print(dfs(0, n, checked, path))


(n, m) = list(map(int, input().split()))
edges = [tuple(map(int, input().split())) for _ in range(m)]
G = [list() for _ in range(n + 1)]
for (a, b) in edges:
	G[a].append(b)
	G[b].append(a)
checked = [False for _ in range(n)]
ans = 0

def dfs(v):
	nonlocal ans
	if all(checked):
		ans += 1
		return
	for u in G[v]:
		if not checked[u - 1]:
			checked[u - 1] = True
			dfs(u)
			checked[u - 1] = False
	return
checked[0] = True
dfs(1)
print(ans)


import itertools
(n, m) = map(int, input().split())
l = [list(map(int, input().split())) for i in range(m)]
L = list(itertools.permutations(range(2, n + 1)))
c = 0
for j in range(len(L)):
	if [1, L[j][0]] in l:
		x = 0
		for k in range(n - 2):
			if [L[j][k], L[j][k + 1]] in l or [L[j][k + 1], L[j][k]] in l:
				x += 1
		if x == n - 2:
			c += 1
print(c)


(n, m) = [int(i) for i in input().split()]
es = set()
for _ in range(m):
	(u, v) = map(int, input().split())
	(u, v) = (u - 1, v - 1)
	es |= {(u, v), (v, u)}
p = [[0]]
x = 0
while p:
	p1 = p.pop()
	if len(p1) == n:
		x += 1
	else:
		for (l0, l1) in es:
			if l0 == p1[len(p1) - 1] and l1 not in p1:
				p.append(p1 + [l1])
print(x)


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

def dfs(i, done):
	ret = 0
	if i in done:
		return 0
	if len(done) == n - 1:
		return 1
	for j in range(len(l[i])):
		ret += dfs(l[i][j], done + [i])
	return ret
print(dfs(0, []))


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)


def dfs(start, path):
	res = 0
	path.append(start)
	if len(path) == N:
		res += 1
		return res
	for i in graph[start]:
		if i not in path:
			res += dfs(i, path)
			path.pop()
	return res
(N, M) = map(int, input().split())
graph = [[] for _ in range(N)]
for i in range(M):
	(a, b) = map(int, input().split())
	graph[a - 1].append(b - 1)
	graph[b - 1].append(a - 1)
print(dfs(0, []))


import itertools
(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)
r = 0
for path in itertools.permutations(range(1, N)):
	path = tuple([0]) + path
	for i in range(1, N):
		if path[i] not in d[path[i - 1]]:
			break
	else:
		r += 1
print(r)


from itertools import permutations
(n, m) = map(int, input().split())
graph = [set(map(lambda n: int(n) - 1, input().split())) for _ in range(m)]
print(sum((all((({0, per[i]} if not i else {per[i - 1], per[i]}) in graph for i in range(n - 1))) for per in permutations((i for i in range(1, n))))))