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

Solution (Python):
_N,_M=input().split()
N = int(_N)
M = int(_M)
l = []
for i in range(0,M):
    _p, _q = input().split()
    l.append((int(_p),int(_q)))
_A,_B=zip(*l)

A=_A+_B
B=_B+_A


def gen_get_to(_fr):
    global A
    global B
    global nodes
    global step
    for itr in range(0,len(A)):
        if A[itr]==_fr:
            if not B[itr] in nodes[0:step]:
                yield B[itr]

def move(): 
    global nodes
    global possible_memo
    global step
    global counter
    global N
    global end_flag
    try:
        _=next(possible_memo[step])
        nodes[step+1]=_
        step+=1
        
        
        
        if step==N-1:
            counter+=1
            
        possible_memo[step]=gen_get_to(nodes[step])
    except StopIteration:
        step-=1
        
        if not step==-1:
            pass
            
        if step==-1:
            
            end_flag=True

nodes=[0]*N
possible_memo=[0]*N
counter=0
step=0
nodes[step]=1
possible_memo[step]=gen_get_to(nodes[0])
end_flag=False

while not end_flag:
    move()


print(counter)

Solution (Python):
N, M = map(int, raw_input().split())
E = {}
for _ in range(M):
	a, b = map(int, raw_input().split())
	if not a in E: E[a] = set()
	if not b in E: E[b] = set()
	E[a].add(b)
	E[b].add(a)

def numPaths(visited_nodes, start_node):
	if len(visited_nodes) == N-1:
		return 1
	sum = 0
	for adj_node in E[start_node]:
		if not adj_node in visited_nodes:
			visited_nodes.add(start_node)
			sum += numPaths(visited_nodes, adj_node)
			visited_nodes.remove(start_node)
	return sum

print numPaths(set(), 1)

Solution (Python):
n,m = map(int, raw_input().split())
adj = [[] for i in range(n)]

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


q = [(0,0)]
all_visited = (1 << n) - 1
ans = 0

while len(q) > 0:
    u,visited = q.pop(0)
    visited = visited ^ (1 << u)
    
    if visited == all_visited:
       ans += 1 
    
    for v in adj[u]:
        if visited & (1 << v):
            continue
        q.append((v,visited))

print ans

Solution (Python):
nmax = 8
graph = [[False for i in range(nmax)] for j in range(nmax)]

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

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

    if all_visited:
        return 1

    ret = 0

    for i in range(N):
        if graph[v][i] == False:
            
            continue
        if visited[i] == True:
            
            continue

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

    return ret

if __name__ == '__main__':
    n, m = map(int, input().split())

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

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

    visited[0] = True
    print(dfs(0, n, visited))

Solution (Python):
n,m=map(int,input().split())
e=[[] for _ 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)

fp=set()
def rec(cur):
    ret = 0
    fp.add(cur)
    if len(fp) == n:
        fp.remove(cur)
        return 1
    for nex in e[cur]:
        if nex not in fp:
            ret += rec(nex)
    fp.remove(cur)
    return ret
print(rec(0))

Solution (Python):
def findpath(graph, root, rest):
    if len(rest) == 0:
        return 1
    res = 0
    for n in graph[root]:
        if n in rest:
            rest.remove(n)
            res += findpath(graph, n, rest)
            rest.add(n)
    return res

n, m = map(int, input().split())
graph = {}
for _ in range(m):
    a, b = map(int, input().split())
    if a not in graph:
        graph[a] = set()
    graph[a].add(b)
    if b not in graph:
        graph[b] = set()
    graph[b].add(a)

print(findpath(graph, 1, set(range(2, n + 1))))

Solution (Python):

def findPaths(start, used):
	
	if len(used) == n:
		return 1

	
	tot = 0
	for v in conn[start]:
		if v not in used:
			used.append(v)
			tot += findPaths(v, used)
			used.pop()

	
	return tot


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


conn = {}
for i in range(m):
	a, b = map(int, raw_input().split())
	if a in conn:
		conn[a].append(b)
	else:
		conn[a] = [b]
	if b in conn:
		conn[b].append(a)
	else:
		conn[b] = [a]


print (findPaths(1, [1]))

Solution (Python):
import itertools
N, M = map(int, input().split())
D = {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)
    cnt += sum(1 for x in zip(l,l[1:]) if tuple(sorted(x)) in D) == N-1
print(cnt)

Solution (Python):
import sys

def debug(x, table):
    for name, val in table.items():
        if x is val:
            print('DEBUG:{} -> {}'.format(name, val), file=sys.stderr)
            return None

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

    for u in range(N - 1):
        if Adj[0][u+1]:
            dp[1<<u][u] = 1

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

    
    ans = sum(dp[univ][u] for u in range(N - 1))

    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 sys
from itertools import permutations

def debug(x, table):
    for name, val in table.items():
        if x is val:
            print('DEBUG:{} -> {}'.format(name, val), file=sys.stderr)
            return None

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 sys
from itertools import permutations

def debug(x, table):
    for name, val in table.items():
        if x is val:
            print('DEBUG:{} -> {}'.format(name, val), file=sys.stderr)
            return None

cnt = 0

def dfs(N, Adj, p, pos, mask):
    global cnt

    if pos == N:
        for i in range(N - 1):
            if not Adj[p[i]][p[i + 1]]:
                break
        else:
            cnt += 1

        return None

    for i in range(N):
        if mask & (1 << i):
            p[pos] = i
            dfs(N, Adj, p, pos + 1, (mask ^ (1 << i)))

    return None

def solve():
    global cnt
    cnt = 0

    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

    p = list(range(N))
    dfs(N, Adj, p, 1, (2 << N) - 1 - 1)

    print(cnt)

if __name__ == '__main__':
    solve()

Solution (Python):
import itertools
N, M = list(map(int, input().split()))
path = [[0 for i in range(N)] for j in range(N)]
for i in range(M):
    a, b = list(map(int, input().split()))
    path[a-1][b-1] = 1
    path[b-1][a-1] = 1

count = 0

for p in itertools.permutations(range(N)):
    if p[0] != 0:
        break
    check = 1
    for search in range(N-1):
        check = check * path[p[search]][p[search+1]]
    count += check

print(count)

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


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

    ans = 0
    for route in permutations(range(2, N + 1), N - 1):
        ok = True
        now = 1
        for node in route:
            if node in graph[now]:
                now = node
            else:
                ok = False
        ans += ok

    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
from itertools import repeat, permutations


if __name__ == '__main__':
    n, m = map(int, input().split())    
    
    edges = [list(repeat(False, n)) for i in range(n)]
    for i in range(m):
        a, b = map(int, input().split())
        a -= 1      
        b -= 1
        edges[a][b] = True
        edges[b][a] = True
    
    
    
    result = 0      
    
    for order_iterable in permutations(range(1, n)):
        order = [0] + list(order_iterable)
        
        if all([edges[order[i - 1]][order[i]] for i in range(1, n)]):
            result += 1     
    print(result)

Solution (Python):
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

def LI(): return list(map(int, input().split()))
def II(): return int(input())
def LS(): return input().split()
def S(): return input()


def main():
    n,m = LI()
    r = 0
    d = collections.defaultdict(set)
    for _ in range(m):
        a,b = LI()
        d[a].add(b)
        d[b].add(a)
    for a in itertools.permutations(range(2,n+1)):
        if a[0] not in d[1]:
            continue
        f = True
        for i in range(len(a)-1):
            if a[i] not in d[a[i+1]]:
                f = False
                break
        if f:
            r += 1

    return r


print(main())

Solution (Python):
import itertools

s = input()
l = s.split()
N = int(l[0])
M = int(l[1])

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):
import numpy as np

class Node:
    def __init__(self, id):
        self.id = id
        self.nexts = []
        self.visited = False

    def add_next(self, node):
        self.nexts.append(node)

def saiki(node, count, judge):
    node.visited = True
    judge[node.id] = True
    if(all(judge)):
        count[0]+=1

    for next in node.nexts:
        if(not next.visited):
            saiki(next, count, judge)
    node.visited = False
    judge[node.id] = False

if __name__=="__main__":
    inputs = lambda : input().replace("\n", "").split(" ")
    N, M = [int(number) for number in inputs()]

    nodes = [Node(i) for i in range(N)]
    for i in range(M):
        x, y = [int(number)-1 for number in inputs()]
        nodes[x].add_next(nodes[y])
        nodes[y].add_next(nodes[x])

    judge = [False]*N
    count = [0]
    saiki(nodes[0], count , judge)
    print(count[0])

Solution (Python):
n,m=map(int,raw_input().split())
graph=[[] for i in xrange(n)]
while m>0:
	m-=1
	a,b=map(int,raw_input().split())
	a-=1
	b-=1
	graph[a].append(b)
	graph[b].append(a)

pathcount=0

def dfs(source,l=[]):
	global pathcount
	for i in (graph[source]):
		
		if i not in l:
			l.append(source)
			if len(l)==n:
				pathcount+=1
			
			dfs(i,l)
			l.remove(source)
			
		
			
	

			
dfs(0,[0])
print pathcount

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

Solution (Python):
from collections import defaultdict

graph = defaultdict(set)
n, m = map(int, input().split())

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









def find_all_paths(graph, start, rest, path=[]):
    path = path + [start]
    rest2 = rest.copy()
    rest2.remove(start)
    if len(rest2) == 0:
        return [path]
    if start not in graph:
        return []
    paths = []
    for node in graph[start]:
        if node not in path:
            newpaths = find_all_paths(graph, node, rest2, path)
            for newpath in newpaths:
                paths.append(newpath)
    return paths

paths = find_all_paths(graph, 1, set(graph.keys()))
print(len(paths))

Solution (Python):
class Path:
    def __init__(self):
        self.a = -1
        self.b = -1

    def getA(self):
        return self.a
    def setA(self, aa):
        self.a = aa
    def getB(self):
        return self.b
    def setB(self, bb):
        self.b = bb

def trace_path(ps, s, cnt, num):
    res = 0
    
    s2 = []
    ps2 = []
    for i in range(0, len(ps)):
        p = ps[i]
        if p.getA() == s or p.getB() == s:
            s2.append(p)
        else:
            ps2.append(p)
    if len(ps2) == 0:
        if cnt == num:
            res += 1
    else:
        for i in range(0, len(s2)):
            p = s2[i]
            if p.a == s:
                res += trace_path(ps2, p.getB(), cnt+1, num)
            else:
                res += trace_path(ps2, p.getA(), cnt+1, num)
    return res

in1 = input().split()
n = int(in1[0])
m = int(in1[1])

ps = []
for i in range(0, m):
    in2 = input().split()
    p = Path()
    p.a = int(in2[0])
    p.b = int(in2[1])
    ps.append(p)
                       
res = trace_path(ps, 1, 1, n-1)

print(str(res))

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

ans = 0
for _ in range(m):
    a, b = map(int, input().split())
    edge.add((a, b))

is_used = set([])
for per in permutations(range(2, n + 1)):
    flag = True
    if (1, per[0]) not in edge:
        continue
    for i in range(n - 2):
        if (per[i], per[i + 1]) not in edge and (per[i + 1], per[i]) not in edge:
            flag = False
            break
    if flag:
        ans += 1

print(ans)

Solution (Python):
from copy import deepcopy as dcopy
def main():
    global count,N,M,edges,stack
    N, M = map(int, input().split())
    edges = [[0]*N for n in range(N)]
    for m in range(M):
        a,b = map(lambda x:int(x)-1,input().split())
        edges[a][b] = 1
        edges[b][a] = 1

    count = 0
    stack = [[[0], [0]]]
    while len(stack) != 0:
        tansaku = stack.pop()
        next_list = [n for n,v in enumerate(edges[tansaku[0][-1]]) if v == 1]
        search(tansaku, next_list)
    print(count)

def search(tansaku, next_list):
    global count, stack
    for node in next_list:
        tmp_tansaku = dcopy(tansaku)
        tmp_node = tmp_tansaku[0]
        houmonzumi = tmp_tansaku[1]
        if node in houmonzumi:
            pass
        else:
            houmonzumi.append(node)
            if len(houmonzumi) == N:
                count += 1
            else:
                tmp_node.append(node)
                stack.append([tmp_node, houmonzumi])

if __name__ == "__main__":
    try:
        import test
        test.test()
    except:
        main()

Solution (Python):
from copy import deepcopy

def wfs(tree, root, node_num):
    lost_list = [root]

    def _wfs(tree, root, lost_list) -> int:
        if len(lost_list) == node_num:
            return 1
        counter = 0
        for i in tree[root]:
            if i not in lost_list:
                tmp = deepcopy(lost_list)
                tmp.append(i)
                counter += _wfs(tree, i, tmp)
        return counter

    return _wfs(tree, 0, lost_list)


n, m = input().rstrip().split()
n, m = int(n), int(m)
v = [list() for i in range(n)]
for _ in range(m):
    line = [int(i) - 1 for i in input().rstrip().split()]
    v[line[0]].append(line[1])
    v[line[1]].append(line[0])

print(wfs(v, 0, n))

Solution (Python):
from itertools import permutations

n,m=map(int,input().split())
es=set()
for _ in range(m):
    u,v=map(int,input().split())
    es|={(u-1,v-1),(v-1,u-1)}

print(sum(all((u,v) in es for u,v in zip(p,p[1:]))
          for p in permutations(range(n)) if p[0]==0))

Solution (Python):
import collections

if __name__ == '__main__':
    n, m = map(int, input().split())
    
    ht = collections.defaultdict(list)
    for _ in range(m):
        a, b = [int(token) - 1 for token in input().split()]
        ht[a].append(b)
        ht[b].append(a)

    stack = [(0, 0)]
    cnt = 0
    while stack:
        position, history = stack.pop()
        if history | (1 << position) == 2 ** n - 1: cnt += 1

        for next_position in ht[position]:
            if history & (1 << next_position) == 0: stack.append((next_position, history | (1 << position)))
        
    print(cnt)

Solution (Python):
import copy
N,M=map(int,raw_input().split())
v=[False for _ in range(N+1)]
v[0]=True
s=[map(int,raw_input().split()) for _ in range(M)]

def recursion(V,p):
    m=0
    for a,b in s:
        if p==a :
            if V[b]:
                continue
            else:
                tmp=copy.deepcopy(V)
                tmp[b]=True
                if all(tmp):
                    m+=1
                else:
                    m+=recursion(tmp,b)
        elif p==b :
            if V[a]:
                continue
            else:
                tmp=copy.deepcopy(V)
                tmp[a]=True
                if all(tmp):
                    m+=1
                else:
                    m+=recursion(tmp,a)
    return m

v[1]=True
print recursion(v,1)

Solution (Python):
n,m = input().split()
n = int(n)
m = int(m)
mat = []
for i in range(n):
  mat.append([])
  for j in range(n):
    mat[-1].append(False)

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

def count(ar, s):
  if len(ar) == 1:
    return 1 if mat[s][ar[0]] else 0
  num = 0
  for s_next in ar:
    if mat[s][s_next]:
      num += count([x for x in ar if x != s_next], s_next)
  return num

total = 0
for i in range(n):
  ar = [j for j in range(n) if j != i]
  total += count(ar, i)
  break
print(total)

Solution (Python):
import itertools

n,m=map(int,input().split())
path={i+1:[] for i in range(n)}
for i in range(m):
    u,v=map(int,input().split())
    path[u].append(v)
    path[v].append(u)
chk=[i for i in range(2,n+1)]
ans=0
for way in list(itertools.permutations(chk)):
    now=1
    if way[0] in path[now]:
        f=1
        for j in way:
            if j in path[now]:
                now=j
                f+=1
            else:
                break
        if f==n: ans+=1
print(ans)

Solution (Python):
import copy

data = raw_input()

n,m = map(int,data.split(" "))

db = []
ans = 0

def search(pos,vis):
  global db
  global ans
  global n,m
  if len(vis) == n:
    ans = ans + 1
    return
  for x in db:
    if x[0] == pos:
      if x[1] not in vis:
        vis2 = copy.deepcopy(vis)
        vis2.append(x[1])
        search(x[1],vis2)

    if x[1] == pos:
      if x[0] not in vis and x[0] != 1:
        vis2 = copy.deepcopy(vis)
        vis2.append(x[0])
        search(x[0],vis2)


for x in range(m):
  data = raw_input()
  a,b = map(int,data.split(" "))
  db.append([a,b])

for x in db:
  if x[0] == 1:
    search(x[1],[1,x[1]])

print ans

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

def solve(path,i,cnt):
    if cnt==n:return 1
    path=list(path)
    path[i]=True
    ans=0
    for v in V[i]:
        if path[v]:continue        
        ans+=solve(tuple(path),v,cnt+1)
    return ans

print(solve([False]*n,0,1))

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

s = []
past = [1]
for i, a in enumerate(A):
    if a == past[-1] and not B[i] in past:
        s.append(past+[B[i]])
for i, b in enumerate(B):
    if b == past[-1] and not A[i] in past:
        s.append(past+[A[i]])
num_paths = 0
while s:
    past = s.pop()
    if len(past) == N:
        num_paths += 1
        continue
    for i, a in enumerate(A):
        if a == past[-1] and not B[i] in past:
            s.append(past+[B[i]])
    for i, b in enumerate(B):
        if b == past[-1] and not A[i] in past:
            s.append(past+[A[i]])

print(num_paths)

Solution (Python):
def dfs(now,vis,G):
    if sum(vis) == len(vis):
        return 1

    ret = 0
    for nx in G[now]:
        if vis[nx] == 0:
            nvis = vis[:]
            nvis[nx] = 1
            ret += dfs(nx,nvis,G)

    return ret

def main():
    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)

    vis = [0 for _ in range(n)]
    vis[0]=1
    return dfs(0,vis,G)

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

Solution (Python):
import itertools
N, M = [int(n) for n in input().split()]
path = [[False for i in range(N)]for j in range(N)]


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


res = 0
for way in itertools.permutations(range(1,N), N-1):
    exist = True
    if path[0][way[0]] == False:
        exist = False
    for n in range(N-2):
        if path[way[n]][way[n+1]] == False:
            exist = False
    if exist == True:
        res += 1

print(res)

Solution (Python):
def read():
    return int(input())

def reads(sep=None):
    return list(map(int, input().split(sep)))

def main():
    n, m = reads();
    g = [set() for _ in range(n+1)]
    for _ in range(m):
        a, b = reads()
        g[a - 1].add(b - 1)
        g[b - 1].add(a - 1)
    
    count = 0
    q = [(0, [])]
    while q:
        i, p = q.pop(0)
        if len(p) == (n-1):
            count += 1
        for e in g[i]:
            if e in p:
                continue
            pp = p[:]
            pp.append(i)
            q.append((e, pp))
    print(count)
 
main()

Solution (Python):
import itertools

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

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

ans = 0
for order in itertools.permutations(list(range(1,n))):
    ok = True
    now = 0
    for to in order:
        if to not in connect[now]:
            ok = False
            break
        now = to

    if ok:
        ans += 1

print(ans)

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

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

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

counter = 0
    
def search(pointStack):
    global counter
    if len(pointStack) == N:
        counter += 1
        pointStack.pop()
        return
    
    currentNode = pointStack[-1]
    for nextNode in road[currentNode]:
        if nextNode in pointStack:
            continue
        pointStack.append(nextNode)
        search(pointStack)

    pointStack.pop()

search([0])

print(counter)

Solution (Python):
n,m=map(int,raw_input().split())
g=[[] for _ in xrange(n)]
for i in xrange(m):
    a,b=map(int,raw_input().split())
    a-=1;b-=1
    g[a].append(b)
    g[b].append(a)
dp=[[0]*(1<<n) for _ in xrange(n)]
dp[0][1]=1
for j in xrange(1<<n):
    for i in xrange(n):
        if j>>i&1:
            for k in g[i]:
                if j>>k&1:
                    continue
                dp[k][j|(1<<k)]+=dp[i][j]
ans=0
for i in xrange(1,n):
    ans+=dp[i][(1<<n)-1]
print(ans)

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

stack = [[0,[1]+[0]*(N-1)]]
ans = 0
while stack:
	cur, passed = stack.pop()
	if passed == [1]*N:
		ans += 1
	else:
		for i, j in enumerate(g[cur]):
			if j and not passed[i]:
				t = passed.copy()
				t[i] = 1
				stack.append([i, t])
print(ans)

Solution (Python):
from collections import deque

N, M = map(int, raw_input().split())
way = {}
for _ in xrange(M):
    a, b = map(int, raw_input().split())
    if a not in way:
        way[a] = set()
    if b not in way:
        way[b] = set()
    way[a].add(b)
    way[b].add(a)

counter = 0
states = deque([({1}, 1)])
while states:
    passed, current = states.popleft()
    if len(passed) == N:
        counter += 1
        continue
    for next_index in way.get(current, []):
        if next_index not in passed:
            states.append((passed | {next_index}, next_index))
print counter

Solution (Python):
n, m = map(int, input().split())
A = [[114514893 for i in range(n)] for j in range(n)]
ans = 0

visited = [0 for i in range(n)]


def dfs(src):
    global ans
    if sum(visited) == n: ans += 1
    for dst in range(n):
        if src == dst: continue
        if visited[dst] or A[src][dst] != 1: continue
        visited[dst] = 1
        dfs(dst)
        visited[dst] = 0


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

visited[0] = 1
dfs(0)
print(ans)

Solution (Python):


import itertools


def count_paths(n, adj_list):
    res = 0
    for vs in itertools.permutations(range(n)):
        if vs[0] != 0:
            continue
        for i in range(n - 1):
            if vs[i] not in adj_list[vs[i + 1]]:
                break
        else:
            res += 1
    return res


def main():
    n, m = (int(x) for x in input().split())
    adj_list = [set() for _ in range(n)]
    for _ in range(m):
        a, b = (int(y) - 1 for y in input().split())
        adj_list[a].add(b)
        adj_list[b].add(a)
    print(count_paths(n, adj_list))


if __name__ == '__main__':
    main()

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


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


def rec(v, use):
    if use == all_use:
        return 1

    key = (v, use)
    if key in memo:
        return memo[key]

    res = 0
    for u in g[v]:
        if (use >> u) & 1 == 1:
            continue

        use = use ^ (1 << u)
        res += rec(u, use)
        use = use ^ (1 << u)

    memo[key] = res
    return res


print(rec(0, 1))

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

Solution (Python):
from collections import defaultdict

N, M = map(int, raw_input().split())
X = [map(int, raw_input().split()) for _ in range(M)]

D = defaultdict(list)
for a, b in X:
    D[a].append(b)
    D[b].append(a)


def dfs(now, p):
    cnt = 0
    if set(now) == set(range(1, N+1)):
        return 1
    for k in D[p]:
        if k in now:
            continue
        cnt += dfs(now + [k], k)
    return cnt

print dfs([1], 1)

Solution (Python):



from fractions import gcd

def readln():
    _res = list(map(int,str(input()).split(' ')))
    return _res

def dfs(deep,now,v):
    if deep == n:
        return 1
    res = 0
    for i in range(1,n+1):
        if v[i] == 0 and e[now][i] == 1:
            v[i] = 1
            res = res + dfs(deep+1, i, v)
            v[i] = 0
    return res


a = readln()
n,m = a[0],a[1]
e = [[0 for i in range(0,n+1)] for j in range(0,n+1)]
for i in range(0,m):
    a = readln()
    e[a[0]][a[1]] = 1
    e[a[1]][a[0]] = 1
v = [0 for i in range(0,n+1)]
v[1] = 1
print(dfs(1,1,v))

Solution (Python):
from itertools import permutations

def f(n, m, uu, vv):
    a = [[0] *n for _ in range(n)]
    for u, v in zip(uu, vv):
        a[u][v] = 1
        a[v][u] = 1
    res = 0
    for p in permutations(range(n)):
        if p[0] != 0:
            break
        ok = True
        for i in range(n - 1):
            if a[p[i]][p[i+1]] == 0:
                ok = False
                break
        if ok:
            res += 1
    return res

n , m = map(int, input().split())
a = []
b = []
for k in range(m):
    _a, _b = map(int, input().split())
    _a -= 1
    _b -= 1
    a.append(_a)
    b.append(_b)
print(f(n, m, a, b))

Solution (Python):
from sys import exit, setrecursionlimit
from functools import reduce
from itertools import *
from collections import defaultdict
from bisect import bisect

def read():
  return int(input())

def reads():
  return [int(x) for x in input().split()]

setrecursionlimit(1000000)

(N, M) = reads()

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

for _ in range(M):
  (a, b) = reads()
  (a, b) = (a-1, b-1)
  conn[a][b] = conn[b][a] = True

count = 0

for p in permutations(range(1, N)):
  if conn[0][p[0]] and all(conn[p[i]][p[i+1]] for i in range(N-2)):
    count += 1

print(count)

Solution (Python):
def dfs(now,vis,G):
    visit_all = True
    for tf in vis:
        if not tf:
            visit_all = False
    if visit_all:
        return 1

    ret = 0
    for nx in G[now]:
        if vis[nx] == 0:
            nvis = vis[:]
            nvis[nx] = 1
            ret += dfs(nx,nvis,G)

    return ret

def main():
    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)

    vis = [0 for _ in range(n)]
    vis[0]=1
    return dfs(0,vis,G)

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