Problem:
 Score : 300 points    Problem Statement You are given an undirected unweighted graph with N vertices and M edges that contains neither self-loops nor double edges. Here, a self-loop is an edge where a_i = b_i (1≤i≤M) , and double edges are two edges where (a_i,b_i)=(a_j,b_j) or (a_i,b_i)=(b_j,a_j) (1≤i<j≤M) . How many different paths start from vertex 1 and visit all the vertices exactly once? Here, the endpoints of a path are considered visited.  For example, let us assume that the following undirected graph shown in Figure 1 is given.    Figure 1: an example of an undirected graph   The following path shown in Figure 2 satisfies the condition.    Figure 2: an example of a path that satisfies the condition   However, the following path shown in Figure 3 does not satisfy the condition, because it does not visit all the vertices.    Figure 3: an example of a path that does not satisfy the condition   Neither the following path shown in Figure 4, because it does not start from vertex 1 .    Figure 4: another example of a path that does not satisfy the condition       Constraints  2≦N≦8   0≦M≦N(N-1)/2   1≦a_i<b_i≦N   The given graph contains neither self-loops nor double edges.         Input The input is given from Standard Input in the following format:  N  M  a_1  b_1  a_2  b_2  :  a_M  b_M       Output Print the number of the different paths that start from vertex 1 and visit all the vertices exactly once.        Sample Input 1 3 3
1 2
1 3
2 3      Sample Output 1 2  The given graph is shown in the following figure:     The following two paths satisfy the condition:          Sample Input 2 7 7
1 3
2 7
3 4
4 5
4 6
5 6
6 7      Sample Output 2 1  This test case is the same as the one described in the problem statement.

Solution (Python):
def do_dp(N, Adj):
    univ = 2 ** N - 1
    dp = [[0] * N for i in range(univ + 1)]
    dp[1][0] = 1

    for S in range(2, univ + 1):
        for v in range(N):
            S2 = S & (univ ^ (1 << v))
            for u in range(N):
                if ((1 << u) & S2) and Adj[u][v]:
                    dp[S][v] += dp[S2][u]
    
    ans = sum(dp[univ][u] for u in range(1, N))

    return ans

def solve():
    N, M = map(int, input().split())
    Adj = [[0] * N for i in range(N)]

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

    ans = do_dp(N, Adj)
    print(ans)

if __name__ == '__main__':
    solve()

Solution (Python):
import numpy as np
n, m = map(int, input().split())
if m == 0:
    print(0)
    exit()
r = [[] for i in range(n)]
for i in range(m):
    f, s = map(int, input().split())
    r[f-1].append(s - 1)
    r[s-1].append(f - 1)
ans = []
def dfs(now, visited = []):
    global ans
    if len(visited) == n:
        ans.append([visited])
        return
    for j in r[now]:
        if j not in visited:
            dfs(j, visited + [j])
dfs(0, [0])
print(len(ans))

Solution (Python):
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
    count=0
    for i in edges[v]:
        if vis[i]==0:
            vis[i]=1
            count+=dfs(i)
            vis[i]=0
    else:
        return count
print(dfs(0))

Solution (Python):
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
    count=0
    for i in edges[v]:
        if vis[i]==0:
            vis[i]=1
            count+=dfs(i)
            vis[i]=0
    else: return count
print(dfs(0))

Solution (Python):
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)
count=0
for i in itertools.permutations(range(2,n+1)):
    if i[0] not in e[1]:
        continue
    f=True
    for j in range(n-2):
        if i[j+1] not in e[i[j]]:
            f=False
            break
    if f:
        count+=1
print(count)

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


route = [i for i in range(2, N+1)]
routes = list(permutations(route))
ans = 0

for route in routes:
    now = 1
    for r in route:
        if ([now, r] not in AB) and ([r, now] not in AB):
            now = r
            break
        now = r
    else:
        ans += 1

print(ans)

Solution (Python):
def c_One_stroke_Path(N, M, E):
    import itertools
    edge = [[] for j in range(N + 1)]
    for a, b in E:
        edge[a].append(b)
        edge[b].append(a)

    ans = 0
    route = itertools.permutations(range(2, N + 1), N - 1)
    for r in route:
        if not r[0] in edge[1]:
            
            continue
        count = 0
        for i in range(len(r)):
            if count == len(r) - 1:
                
                ans += 1
                break
            if not r[i + 1] in edge[r[i]]:
                
                break
            count += 1

    return ans

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

Solution (Python):
N,M=[int(i) for i in input().split()]
edge=[[] for i in range(N)]

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

went=[False for i in range(N)]

def dfs(now):
	if went.count(False)==0:
		return 1
	ans=0
	for _next in edge[now]:
		if not went[_next]:
			went[_next]=True
			ans+=dfs(_next)
			went[_next]=False
	return ans
went[0]=True

print(dfs(0))

Solution (Python):
def main():
    """
    N<=8, M<=N(N-1)/2
    →全探索?
    """
    N, M = map(int, input().split())

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

    
    visited = [False for _ in range(N)]
    visited[0] = True

    def dfs(v, N, visited):
        if all(visited):
            return 1

        ret = 0
        for i in range(N):
            
            if not g[v][i] or visited[i]:
                continue

            
            visited[i] = True
            ret += dfs(i, N, visited)
            visited[i] = False

        return ret

    ans = dfs(0, N, visited)

    print(ans)

if __name__ == '__main__':
    main()

Solution (Python):
import itertools
import collections
N,M=map(int,raw_input().split())

a=[map(int,raw_input().split()) for i in range(M)]

b=list(itertools.permutations(range(1,N+1)))


ans=0
for i in b:
	if i[0]!=1:
		continue
	c=[]
	for j in i:
		
		if len(c)<2:
			c.append(j)

		if len(c)==2:
			if c in a or c[::-1] in a:
				cnt=1
			else:
				cnt=0
				break
			c.pop(0)
	ans+=cnt
print ans

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

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

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

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

ret = 0
for path in itertools.permutations(range(2, N + 1)):
    if path[0] not in E[1]:
        continue
    f = True

    for i in range(N - 2):
        if path[i + 1] not in E[path[i]]:
            f = False
            break
    if f:
        ret += 1

print(ret)

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

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

def dfs(v, used):
    if not False in used:
        return 1
    
    ans = 0
    for i in range(N):
        if not adj_matrix[v][i]:
            continue
        if used[i]:
            continue
        
        used[i] = True
        ans += dfs(i, used)
        used[i] = False
    
    return ans

used = [False] * N
used[0] = True

print(dfs(0, used))

Solution (Python):

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

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

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

memo = {}
All_used = (1 << N) -1

def dfs(v, used):
    if used == All_used:
        return 1
    
    key = (v, used)
    if key in memo:
        return memo[key]
    
    ans = 0
    for u in g[v]:
        if (used >> u) & 1 == 1:
            continue
        
        used ^= (1 << u)
        ans += dfs(u, used)
        used ^= (1 << u)
        
    memo[key] = ans
    return ans

print(dfs(0, 1))

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

Solution (Python):
N, M = [int(i) for i in input().split()]
road = [list() for i in range(N + 1)]
for i in range(M):
    a, b = [int(i) for i in input().split()]
    road[a].append(b)
    road[b].append(a)


def solve(before, visited, now):
    visited.append(now)
    if len(visited) is N:
        return 1
    pattern = 0
    for way in road[now]:
        if way is now:
            continue
        if way in visited:
            continue
        pattern += solve(now, visited[:], way)
    return pattern


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

Solution (Python):
from copy import deepcopy


def solve(road, num, ans, n):
    pattern = 0
    test = deepcopy(road)
    for s in test:
        if num in s:
            s.remove(num)
    if len(ans) is n:
        return 1
    if len(test[num - 1]) == int(0):
        return 0
    else:
        for i in range(len(test[num - 1])):
            tmp = test[num - 1][i]
            if tmp is not 0:
                word = ans + str(tmp)
            pattern += solve(test, tmp, word, n)
    return pattern


N, M = [int(i) for i in input().split()]
town = []
for i in range(N):
    town.append(deepcopy([]))

for i in range(M):
    a, b = [int(i) for i in input().split()]
    if a is not 1 or b is not 1:
        town[a - 1].append(b)
        town[b - 1].append(a)
print(solve(town, 1, '1', N))

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

graph = [list() for i in range(N+1)]

for i in range(M):
    a, b = list(map(int, input().split(" ")))
    graph[a].append(b)
    graph[b].append(a)
    
def DFS(node, prev, visited):
    visited.append(node)
    if len(visited) == N:
        return 1
    
    res = 0
    for edge in graph[node]:
        if edge == prev:
            continue
        elif edge in visited:
            continue
        res += DFS(edge, node, visited[:])
        
    return res

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

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

graph = [list() for i in range(N+1)]

for i in range(M):
    a, b = list(map(int, input().split(" ")))
    graph[a].append(b)
    graph[b].append(a)
    
def DFS(node, prev, visited):
    visited.append(node)
    if len(visited) == N:
        return 1
    
    res = 0
    for edge in graph[node]:
        if edge == prev:
            continue
        elif edge in visited:
            continue
        res += DFS(edge, prev, visited[:])
        
    return res

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

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


def main():
    N, M = map(int, input().split())
    s = set()
    for _ in range(M):
        a, b = map(int, input().split())
        s.add((a, b))
        s.add((b, a))
    ans = 0
    for x in permutations(range(2, N + 1)):
        now = 1
        for i in range(len(x)):
            if (now, x[i]) not in s:
                break
            now = x[i]
        else:
            ans += 1
    print(ans)

if __name__ == '__main__':
    main()

Solution (Python):
def makelist(n, m):
  return [[False for i in range(m)] for j in range(n)]


N, M = map(int, input().split())
graph = [0]*N
ans = [0]

for i in range(N):
  graph[i] = []
  
for i in range(M):
  a, b = map(int, input().split())
  a -= 1
  b -= 1
  graph[a].append(b)
  graph[b].append(a)
  
def dfs(now, dp):
  if dp.count(True) == N:
    ans[0] += 1
  else:
    for e in graph[now]:
      if not dp[e]:
        nextdp = dp[:]
        nextdp[e] = True
        dfs(e, nextdp)

first = [False]*N
first[0] = True
dfs(0, first)
print(ans[0])

Solution (Python):

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
    ret = 0
    for u in set(g[v[-1]]) - set(v):
        ret += dfs(v + [u])
    return ret

print(dfs([0]))

Solution (Python):
import itertools
import sys




def read_int_list():
    return list(map(int, input().split()))


def read_str_list():
    return input().split()


def read_int():
    return int(input())


def read_str():
    return input()


N, M = read_int_list()
a = list()
b = list()
edges = set()
for i in range(1, M + 1):
    s = input()
    l = s.split()
    u = int(l[0])
    v = int(l[1])
    a.append(u)
    b.append(v)
    edges.add((u, v))
    edges.add((v, u))


t = range(1, N + 1)
res = 0
for p in itertools.permutations(t):
    if p[0] != 1:
        break
    c = 0
    for j in range(0, N - 1):
        if (p[j], p[j + 1]) in edges:
            c += 1
    if c == N - 1:
        res += 1
print(res)

Solution (Python):
def dfs():
  stack = [[0]]
  count = 0
  while stack:
    route = stack.pop()
    if len(route) == N:
      
      count += 1
      continue
    now = route[-1]
    for next in filter(lambda x: EDGES[now][x] == 1, range(N)):
      
      if next in route:
        continue
      newroute = route[:]
      newroute.append(next)
      stack.append(newroute)
  return count

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

print dfs()

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

l = []

for i in range(M):
    l.append(list(map(lambda x: int(x) - 1, input().split())))

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

for i in range(M):
    lis[l[i][0]].append(l[i][1])
    lis[l[i][1]].append(l[i][0])






























que = [[0, lis[0], []]]
ends = []

while que:
    now, nextnodes, visited = que.pop()
    ends.append(visited)
    visited.append(now)
    for node in nextnodes:
        if node in visited:
            continue
        que.append([node, lis[node], visited[:]])

print(len(list(filter(lambda ii: len(ii) is N, ends))))

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

abmap = {}
for a, b in ab:
    atarget = abmap.get(a)
    if atarget == None:
        abmap[a] = []
    abmap[a].append(b)

    btarget = abmap.get(b)
    if btarget == None:
        abmap[b] = []
    abmap[b].append(a)

que = [[1, abmap[1], []]]
ends = []
while que:
    now, nextnodes, visited = que.pop()
    ends.append(visited)
    visited.append(now)
    for node in nextnodes:
        if node in visited:
            continue
        mvisited = visited[:]
        que.append([node, abmap[node], mvisited])

print(len(list(filter(lambda x: len(x) == n, ends))))

Solution (Python):
import itertools
import numpy as np
N, M = map(int, raw_input().split())
G = [map(int, raw_input().split()) for i in range(M)]
ans = 0
for x in itertools.permutations(range(1,N+1)):
    if x[0] != 1:
        continue
    ok = True
    for i in range(N-1):
        a, b = x[i:i+2]
        if (not [a, b] in G) and (not [b, a] in G):
            ok = False
            break
    if ok:
        ans += 1
print ans

Solution (Python):

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



visited = [False for i in range(N+1)]

num_of_paths = 0
def dfs(v):
    global num_of_paths
    
    if visited.count(True) == N:
        num_of_paths += 1
        return
    else:
        for next_v in E[v]:
            if not visited[next_v]:
                visited[next_v] = True
                dfs(next_v)
                visited[next_v] = False
        return
    
visited[1] = True
dfs(1)

print(num_of_paths)

Solution (Python):
def move(a, A, c):

  c.remove(a)
  if(c==[]):
    return 1
  if(not a in A):
    return 0
  sum = 0
  for i in A[a]:
    if(i in c):
      sum += move(i, A, list(c))

  return sum


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

A = {}
c = []

for i in range(M):
  a, b = map(int, input().split())

  if(not a in c):
    c.append(a)
  if(not b in c):
    c.append(b)

  if(a in A):
    A[a].append(b)
  else:
    A[a] = [b]
  if(b in A):
    A[b].append(a)
  else:
    A[b] = [a]

print(move(1, A, c))

Solution (Python):


import sys
import os

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

one_stroke_num = 0
def dfs(v):
    
    global one_stroke_num

    if visited.count(True) == N:
        one_stroke_num += 1
        return
    else:
        
        for next_i in E[v]:
            if not visited[next_i]:
                
                visited[next_i] = True
                dfs(next_i)
                visited[next_i] = False
        
        return

visited[0] = True
dfs(0)

print(one_stroke_num)

Solution (Python):
from collections import defaultdict
import queue

if __name__ == "__main__":
    inp = [int(i) for i in input().split()]
    N = inp[0]
    M = inp[1]
    adjs = defaultdict(lambda: [])
    for i in range(M):
        a, b = [int(i) for i in input().split()]
        adjs[a].append(b)
        adjs[b].append(a)
    
    q = queue.Queue()
    q.put([1])
    n = 0
    while True:
        if q.empty(): break
        p = q.get()
        if len(p) == N:
            n += 1
        else:
            for i in adjs[p[-1]]:
                if i not in p:
                    pp = p.copy()
                    pp.append(i)
                    q.put(pp)
    print(n)

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

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)

Solution (Python):
N, M = map(int,input().split())
graph = [[False for i in range(N)] for j in range(N)]
for i in range(M):
    a, b = map(int,input().split())
    graph[a-1][b-1] = graph[b-1][a-1] = True

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

visited = [False]*N
visited[0] = True
print(dfs(0,N,visited))

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

bar = [[] for _ in range(n)]

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

result = 0

def search(root=[0]):
    global result
    if len(root) >= n:
        result += 1
        return
    nxt = set(bar[root[-1]])
    nxt = nxt - set(root)
    for nxt_ in nxt:
        search(root+[nxt_])

search()
print(result)

Solution (Python):
def add_adj(adj, k, v):
    if k not in adj:
        adj[k] = set()
    adj[k].add(v)


def all_visited(N):
    x = 0
    for i in range(N):
        x += 1 << i
    return x


def dfs(adj, cur, visited, N):
    if visited == all_visited(N):
        return 1
    cnt = 0
    for nex in adj[cur]:
        if (visited >> (nex - 1)) & 1 == 1:
            continue
        cnt += dfs(adj, nex, (visited | (1 << (nex - 1))), N)
    return cnt


def main():
    N, M = map(int, input().split())
    adj = {}
    for i in range(M):
        a, b = map(int, input().split())
        add_adj(adj, a, b)
        add_adj(adj, b, a)
    print(dfs(adj, 1, 1, N))

if __name__ == '__main__':
    main()

Solution (Python):
num = list(map(int,raw_input().split()))
point = num[0]
line = num[1]
total = 0
d = {}
for i in range (point):
    d[i+1] = []
for i in range(line):
    pair = list(map(int,raw_input().split()))
    d[pair[0]].append(pair[1])
    d[pair[1]].append(pair[0])
old_list = []
new_list = [[1]]
for i in range (point-1):
    old_list = new_list[:]
    new_list =[]
    for j in old_list:
        for k in d[j[-1]]:
            if k in j:
                pass
            else:
                j.append(k)
                new_list.append(j[:])
                j.pop()
print len (new_list)

Solution (Python):

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


sign = []
for i in range(n):
    sign.append("o")


graph = []
for i in range(n):
    graph.append([])


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



def dfs(x, i=0):
    sign[x] = "x"
    
    
    if sign == ["x" for k in range(n)]:
        return i + 1
    
    
    for j in graph[x]:
        if sign[j] == "o":
            
            
            sign[j] = "x"
            
            
            
            
            
            
            
            
            
            i = dfs(j, i)
            
            
            sign[j] = "o"
    return i

print(dfs(0))

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

sign = []
for i in range(n):
    sign.append("o")
    
graph = []
for i in range(n):
    graph.append([])
    
for i in range(m):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    for j in range(n):
        if a == j:
            graph[j].append(b)
        if b == j:
            graph[j].append(a)

def dfs(x, i=0):
    sign[x] = "x"
    if sign == ["x" for k in range(n)]:
        return i + 1
    for j in graph[x]:
        if sign[j] == "o":
            sign[j] = "x"
            i = dfs(j, i)
            sign[j] = "o"
    return i 

print(dfs(0))

Solution (Python):

import sys
import math
import numpy as np
from itertools import permutations
from functools import reduce



def main():
    
    N, M = map(int, input().split())
    edges = [set(map(int, input().split())) for i in range(M)]
    print(edges, file=sys.stderr)

    
    ps = permutations(range(2,N+1), N-1)

    C = 0
    for p in ps:
        q = [1] + list(p)
        xs = [set((q[i],q[i+1])) in edges for i in range(N-1)]
        if all(xs):
            print(q, file=sys.stderr)
            C += 1

    
    print(C)


if __name__ == '__main__':
    main()

Solution (Python):
n,m = map(int,input().split())
vector = []
for i in range(m):
    a,b = map(int,input().split())
    vector.append([a,b])
    vector.append([b,a])
global kotae
kotae = 0
route =  [1]

def idou(route,vector):
    global kotae
    if len(route) == n:
        kotae += 1
        return 0
    for vec in vector:
        if vec[0] == route[-1] and vec[1] not in route:
            route.append(vec[1])
            idou(route,vector)
            route.remove(vec[1])
    return 0
    

idou(route,vector)
 
          
print(kotae)

Solution (Python):
def main():
    N,M = map(int, raw_input().split())
    conf = [[0 for i in range(N)]for j in range(N)] 
    visit = [0]*N
    c = 0
    for i in range(M):
        s,g = map(int , raw_input().split())
        conf[s-1][g-1] = 1
        conf[g-1][s-1] = 1
    visit[0] = 1
    return dfs(conf, visit, 0, c)

def dfs(conf, visit, s, c):
    if 0 not in visit:
        visit[s] = 0
        c += 1
        return c
    for i in xrange(len(visit)):
        if conf[s][i] == 1 and visit[i] == 0:
            visit[i] = 1
            c = dfs(conf, visit , i, c)
            visit[i] = 0
    return c
print main()

Solution (Python):
N, M = map(int, input().split(" "))
a = [0 for i in range(M)]
b = [0 for i in range(M)]
for i in range(M):
    a[i], b[i] = map(int, input().split(" "))

adj_matrix = [[0 for i in range(N)] for j in range(N)]
visited_flag = [0 for i in range(N)]
visited_flag[0] = 1

for i in range(M):
    adj_matrix[a[i]-1][b[i]-1] = 1
    adj_matrix[b[i]-1][a[i]-1] = 1

def find_next(idx, matrix, flag, nb_ans):
    if sum(flag) == N:
        return nb_ans+1
    for j in range(N):
        if matrix[idx][j] == 1 and flag[j] == 0:
            flag[j] = 1
            nb_ans = find_next(j, matrix, flag, nb_ans)
            flag[j] = 0

    return nb_ans

nb_ans = find_next(0, adj_matrix, visited_flag, 0)
print(nb_ans)

Solution (Python):
t = list(str(input()).split(" "))
n = int(t[0])
m = int(t[1])

x = [list() for i in range(n)]
lst = list()

for i in range(m):
    t = list(str(input()).split(" "))
    a = int(t[0])
    b = int(t[1])
    x[a-1].append(b-1)
    x[b-1].append(a-1)

def depth(p):

    if(len(lst) == n-1):
        global c
        c = c+1

    else:
        for i in x[p]:
            if(i not in lst):
                lst.append(p)
                depth(i)
                lst.remove(p)

c = 0
depth(0)
print(c)

Solution (Python):
import itertools

def path(n):
    l = len(n)
    i = 0
    while i < l - 1:
        a = n[i]
        b = n[i + 1]

        if a < b:
            c = (a, b)
        else:
            c = (b, a)

        for m in C:
            if m == c:
                break
        else:
            return False
        i += 1
    return True

N, M = map(int, input().split())
C = []
i = 0
while i < M:
    C += [tuple(map(int, input().split()))]
    i += 1

i = 0
l = range(1, N + 1)
for n in itertools.permutations(l, N):
    if n[0] != 1:
        break
    if path(n) == True:
        i += 1
print(str(i))

Solution (Python):

from itertools import permutations

n,m=map(int,raw_input().split())
r=set()
s=set()
for i in xrange(m):
 u,v=map(int,raw_input().split())
 u-=1
 v-=1
 r.add(u)
 r.add(v)
 s.add((u,v))
 s.add((v,u))

res=0
l=list(permutations(r))
for t in l:
 if t[0]!=0:
  continue
 if all((t[i],t[i+1]) in s for i in xrange(n-1)):
  res+=1
   
print res

Solution (Python):
n, m = map(int, raw_input().split())
edges = [list(map(int, raw_input().split())) for _ in xrange(m)]

adjacent = [[] for _ in xrange(n)]
for a, b in edges:
    adjacent[a-1].append(b)
    adjacent[b-1].append(a)

check = [False]*n
check[0] = True
count = 0

def DFS(cn):
    global count
    if all(check):
        count += 1
        return 0
    for nn in adjacent[cn-1]:
        if check[nn-1] == True:
            continue
        else:
            check[nn-1] = True
            DFS(nn)
            check[nn-1] = False
    return 0

if __name__ == '__main__':
    DFS(1)
    print count

Solution (Python):
from itertools import permutations as perm

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

path = [[False] * n for _ in range(n)]
for i in range(n):
    path[i][i] = True

for _ in range(m):
    ai, bi = map(int, input().split())
    a, b = ai - 1, bi - 1
    path[a][b] = True
    path[b][a] = True

ans = 0
for ps in perm(range(1, n)):
    fst = ps[0]
    if not path[0][fst]:
        continue
    check = [path[i][j] for (i, j) in zip(ps, ps[1:])]
    if all(check):
        ans += 1

print(ans)

Solution (Python):


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

inlist = []
for i in range(m):
	inlist.append(list(map(int, input().split())))

graph = [[0 for i in range(n)] for j in range(n)]

for i in inlist:
	graph[i[0]-1][i[1]-1] = 1
	graph[i[1]-1][i[0]-1] = 1

visited = []
visited.append(0)
count = 0
def dfs(cur):
	if len(visited) == n:
		global count
		count += 1
		return
	for i in range(n):
		if graph[cur][i] == 1 and i not in visited:
			visited.append(i)
			dfs(i)
			visited.pop()
	return

dfs(0)

print(count)

Solution (Python):
def dfs(x, count):
    ret = 0
    if used[x]:
        return ret
    used[x] = 1
    for y in path[x]:
        ret += dfs(y, count + 1)
    used[x] = 0
    if count == N:
        return ret + 1
    else:
        return ret

if __name__ == '__main__':
    N, M = map(int, input().split())
    path = {i + 1: set() for i in range(N)}
    for _ in range(M):
        a, b = map(int, input().split())
        path[a].add(b)
        path[b].add(a)
    used = [0] * (N + 2)
    print(dfs(1, 1))

Solution (Python):

from queue import Queue

q = Queue()
N, M = [int(n) for n in input().split()]
graph = {n:[] for n in range(1, N+1)}

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

end = 0
for n in range(2, N+1):
    if len(graph[n]) == 1:
        end = n

ok = []
q.put([1, []])

while not q.empty():
    point, past = q.get()
    for d in graph[point]:
        if not d in past:
            if len(past + [point, d]) == N:
                ok.append(past + [point, d])
            else:
                q.put([d, past+[point]])

print(len(ok))

Solution (Python):
import itertools

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

graph = [[] for i in range(n)]
for j in range(m):
    x, y = map(int, input().split())
    road[x - 1][y - 1] += 1
    road[y - 1][x - 1] += 1
    graph[x - 1].append(y - 1)
    graph[y - 1].append(x - 1)



count = 0

for can in itertools.permutations(range(n)):
    if can[0] != 0:
        break
    
    plus = 1
    for k in range(n - 1):
        
        plus *= road[can[k]][can[k + 1]]
    count += plus


def dfs(node, prev, visited):
    visited.append(node)
    if len(visited) == n:
        return 1

    res = 0
    for edge in graph[node]:
        if edge == prev:
            continue
        if edge in visited:
            continue
        res += dfs(edge, prev, visited[:])

    return res


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

if count == dfs:
    print(dfs)