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

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

def memoize(function):
    def _memoize(*args, _cache={}):
        if args in _cache:
            return _cache[args]
        result = function(*args)
        _cache[args] = result
        return result
    return _memoize


class Union_find():

    def __init__(self, num):
        self.num = num
        self.par = list(range(num))
        self.rank = [0]*num

    def find(self, x):
        px = self.par[x]
        if px == x:
            return x
        else:
            rx = self.find(px)
            self.par[x] = rx
            return rx

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x != y:
            if self.rank[x] > self.rank[y]:
                self.par[y] = x
            else:
                self.par[x] = y
                if self.rank[x] == self.rank[y]:
                    self.rank[y] = self.rank[y] + 1
        return self

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

    def group_num(self):
        l = set()
        for i in range(self.num):
            l.add(self.find(i))
        return len(l)


class Adjlist():

    def __init__(self, nodes, edges = None):
        self.nodes = nodes
        lis = [set() for i in range(nodes)]
        if edges is not None:
            for edge in edges:
                lis[edge[0]].add(edge[1])
        self.edges = lis

    def add_edge(self, edge):
        self.edges[edge[0]].add(edge[1])
        return self

    def discard_edge(self, edge):
        self.edges[edge[0]].discard(edge[1])
        return self

    def next_set(self, x):
        return self.edges[x]

    def include_edge(self, x, y):
        return y in self.next_set(x)

class Adjlist_weighted():

    def __init__(self, nodes, edges = None):
        self.nodes = nodes
        lis = [{} for i in range(nodes)]
        if edges is not None:
            for edge in edges:
                lis[edge[0]][edge[1]] = edge[2]
        self.edges = lis

    def add_edge(self, edge):
        self.edges[edge[0]][edge[1]] = edge[2]
        return self

    def discard_edge(self, edge):
        del self.edges[edge[0]][edge[1]]
        return self

    def next_set(self, x):
        return self.edges[x].keys()

    def include_edge(self, x, y):
        return y in self.next_set(x)

    def weight_edge(self, x, y):
        return self.edge[x][y]

class Adjmat():

    def __init__(self, nodes, edges = None):
        self.nodes = nodes
        mat = [[0]*nodes for i in range(nodes)]
        if edges is not None:
            for edge in edges:
                mat[edge[0]][edge[1]] = 1
        self.edges = mat

    def add_edge(self, edge):
        self.edges[edge[0]][edge[1]] = 1
        return self

    def discard_edge(self, edge):
        self.edges[edge[0]][edge[1]] = 0
        return self

    def include_edge(self, x, y):
        return self.edge[x][y] == 1

    def next_set(self, x):
        set = set()
        for y in range(nodes):
            if self.include_edge(x, y):
                set.add(y)
        return set


class Adjmat_weighted():

    def __init__(self, nodes, edges = None):
        self.nodes = nodes
        mat = [[None]*nodes for i in range(nodes)]
        if edges is not None:
            for edge in edges:
                mat[edge[0]][edge[1]] = edge[2]
        self.edges = mat

    def add_edge(self, edge):
        self.edges[edge[0]][edge[1]] = edge[2]
        return self

    def discard_edge(self, edge):
        self.edges[edge[0]][edge[1]] = None
        return self

    def include_edge(self, x, y):
        return self.edges[x][y] is not None

    def next_set(self, x):
        set = set()
        for y in range(nodes):
            if self.include_edge(x, y):
                set.add(y)
        return set

    def weight_edge(self, x, y):
        return self.edge[x][y]


class Graph():

    def __init__(self, nodes, adj_mat = True, weighted = False, directed = False, edges = None):
        self.nodes = nodes
        self.adj_mat = adj_mat
        self.directed = directed
        self.weighted = weighted
        if weighted:
            if not(directed):
                if edges is not None:
                    for edge in edges:
                        edges.add((edge[1], edge[0], edge[2]))
            if adj_mat:
                edges = Adjmat_weighted(nodes, edges)
            else:
                edges = Adjlist_weighted(nodes, edges)
        else:
            if not(directed):
                if edges is not None:
                    for edge in edges:
                        edges.add((edge[1], edge[0]))
            if adj_mat:
                edges = Adjmat(nodes, edges)
            else:
                edges = Adjlist(nodes, edges)
        self.edges = edges

    def add_edge(self, edge):
        self.edges.add_edge(edge)
        if not(self.directed):
            if self.weighted:
                self.edges.add_edge((edge[1], edge[0], edge[2]))
            else:
                self.edges.add_edge((edge[1], edge[0]))
        return self

    def discard_edge(self, edge):
        self.edges.discard_edge(edge)
        if not(self.directed):
            self.edges.discard_edge((edge[1], edge[0]))
        return self

    def include_edge(self, x, y):
        return self.edges.include_edge(x, y)

    def next_set(self, x):
        return self.edges.next_set(x)

    def weight_edge(self, x, y):
        if self.weighted:
            return self.edges.weight_edge(x, y)
        elif self.adj_mat:
            return self.edges[x][y]
        else:
            if self.include_edge(x, y):
                return 1
            else:
                return 0

    def union_find(self):
        uf = Union_find(self.nodes)
        if self.adj_mat:
            for i in range(self.nodes):
                for j in range(self.nodes):
                    if self.edges.include_edge(i, j):
                        uf.union(i, j)
        else:
            for i in range(self.nodes):
                for j in self.edges.next_set():
                    uf.union(i, j)
        return uf

(N, M) = tuple(map(int, input().split(" ")))
g = Graph(N, False)
for i in range(M):
    g.add_edge(tuple(map(lambda x:int(x)-1, input().split(" "))))

@memoize
def one_path(point, path=(), remin = N-1):
    if remin != 0:
        s = set(path)
        s.add(point)
        d = g.next_set(point) - s
        sum = 0
        for n in d:
            sum += one_path(n, tuple(s), remin - 1)
        return sum
    else:
        return 1

print(one_path(0))

Solution (Python):
import itertools
n,m = map(int,raw_input().split())

permutations = list(itertools.permutations(range(1,n)))


arr = [[-1 for i in range(n)] for j in range(n)]


for i in range(m):
	f,t = map(int,raw_input().split())
	f -= 1
	t -= 1
	arr[f][t] = 1
	arr[t][f] = 1


ans = 0
for p in permutations :
	count = 0
	if arr[0][p[0]] == 1 :
		count += 1
	else:
		next

	for i in range(0,len(p)-1):
		if arr[p[i]][p[i+1]] == 1 :
			count += 1

		else:
			break

	if count == n-1 :
		ans += 1
print ans

Solution (Python):
N, M = map(int, input().split())
a, b = [], []

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

zero_mask = "".join(['0' for x in range(N)])
full_mask = "".join(['1' for x in range(N)])
paths_cnt = 0
paths_set = set()

def do_mask(m, idx) :
    newmask = m[:idx] + '1' + m[idx + 1:]
    return newmask

def dfs(m, idx) :
    global paths_cnt
    
    
    
    newmask = do_mask(m, idx)
    
    if newmask == full_mask :
        paths_cnt += 1
    else :
        for i in range(N) :
            
            if idx != i and newmask[i] != '1' and (idx, i) in paths_set:
                dfs(newmask, i)

for i in range(M) :
    paths_set.add((a[i], b[i]))
    paths_set.add((b[i], a[i]))
    
dfs(zero_mask, 0)
print(paths_cnt)

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

for i in range(M) :
    _f, _t = map(int, input().split())
    paths.add((_f - 1, _t - 1))
    paths.add((_t - 1, _f - 1))

zeromask = "".join(['0' for x in range(N)])
fullmask = "".join(['1' for x in range(N)])
cnt = 0

def do_mask(m, idx) :
    return m[:idx] + '1' + m[idx + 1:]

def dfs(m, idx) :
    global cnt
    new_mask = do_mask(m, idx)
    
    if new_mask == fullmask :
        cnt += 1
    else :
        for i in range(N) :
            if i != idx and m[idx] != '1' and (idx, i) in paths:
                dfs(new_mask, i)
            
dfs(zeromask, 0)
print(cnt)

Solution (Python):
import numpy as np

N,M = list(map(int,input().split()))
arr = [[] for i in range(N)]

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

for i in range(len(arr)):
    arr[i].sort


def dfs(array,point,cnt):
    
    if(array[point]==[]):
        return cnt

    tmparr = array.copy()
    ps = tmparr[point]
    tmparr[point] = []
    
    if sum(map(len,tmparr)) == 0:
        return cnt+1
    
    for p in ps:
        
        cnt = dfs(tmparr,p,cnt)
    
    return cnt

print(dfs(arr,0,0))

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

zero_mask = "".join(["0" for x in range(n)])
full_mask = "".join(["1" for x in range(n)])

paths_cnt = 0

for i in range(m) :
    _a, _b = map(int, input().split())
    paths.add((_a - 1, _b - 1))
    paths.add((_b - 1, _a - 1))

def mask_idx(s, idx) :
    newmask = s[:idx] + "1" + s[idx + 1:] 
    return newmask 

def dfs(cur_idx, mask) :
    
    global paths_cnt
    new_mask = mask_idx(mask, cur_idx)
    
    
    if new_mask == full_mask :
        paths_cnt += 1
    for i in range(n) : 
        if i != cur_idx and new_mask[i] != '1' and (cur_idx, i) in paths:
            dfs(i, new_mask)
            
dfs(0, zero_mask)
print(paths_cnt)

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

for i in range(m) :
    _a, _b = map(int, input().split())
    paths.add((_a - 1, _b - 1))
    paths.add((_b - 1, _a - 1))

full_mask = "".join(["1" for x in range(n)])
zero_mask = "".join(["0" for x in range(n)])
p_cnt = 0

def dfs(cur_idx, mask) :
    global p_cnt
    
    
    new_mask = list(mask)
    new_mask[cur_idx] = "1"
    new_mask = "".join(new_mask)

    
    
    if new_mask == full_mask :
        p_cnt += 1
    else :
        for i in range(n) :
            
            if (cur_idx, i) in paths and mask[i] != "1" :
                dfs(i, new_mask)

dfs(0, zero_mask)
print(p_cnt)

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

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

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

ans = 0


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

def dfs(v):
    global ans, used
    if len(used) == N:
        ans += 1
        return
    else:
        for next_v in vertex_list[v]:
            if next_v not in used:
                used.add(next_v)
                dfs(next_v)
                used.remove(next_v)
        return

used = set([1])
dfs(1)

print(ans)

Solution (Python):
import copy

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

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

temp = []

def trace(p, route):
    hoge = copy.deepcopy(route)
    hoge.append(p)
    ret = 0
    for i in range(n):
        if i not in hoge and x[p][i] == 1:
            if len(hoge) == n - 1:
                return 1
            else:
                ret += trace(i, hoge)
    return ret

print(trace(0, temp))

Solution (Python):
from collections import defaultdict
from itertools import permutations
import sys
sys.setrecursionlimit(10000)
N,M=list(map(int,input().split()))
links=defaultdict(set)
for i in range(M):
    a,b=list(map(int, input().split()))
    links[a].add(b)
    links[b].add(a)
ct=0
for pts in permutations(range(2,N+1),N-1):
    current=1
    for p in pts:
        if  p not in links[current]:
            break
        else:
            current=p
    else:
        ct+=1
print(ct)

Solution (Python):
from collections import defaultdict
import sys
sys.setrecursionlimit(10000)
N,M=list(map(int,input().split()))
links=defaultdict(list)
for i in range(M):
    a,b=list(map(int, input().split()))
    links[a].append(b)
    links[b].append(a)
ct=0
visited=[False]*N
def DFS(idx):
    global visited
    if all(visited):
        global ct
        ct+=1
        return
    for i in links[idx]:
        if visited[i-1]:
            continue
        visited[i-1]=True
        DFS(i)
        visited[i-1]=False
visited[0]=True
DFS(1)
print(ct)

Solution (Python):
from itertools import permutations

def main():
	n, m = list(map(int, input().split()))
	adj_list = [[] for _ in range(n)]
	for i in range(m):
		u, v = list(map(int, input().split()))
		adj_list[u-1].append(v-1)
		adj_list[v-1].append(u-1)
	pts = list(permutations(list(range(1, n))))
	
	
	ans = 0
	for pt in pts:
		cur = 0
		for nxt in pt:
			if nxt in adj_list[cur]:
				cur = nxt
			else:
				break
		else:
			ans += 1
	print(ans)

if __name__ == '__main__':
	main()

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

ans = 0
global visit
visit = [1 for i in range(0,n)]

def dfs(s):
    if sum(visit) == 0:
        global ans
        ans += 1
        return
    for i in g[s]:
        
        if visit[i] == 1:
            visit[i] = 0
            dfs(i)
            visit[i] = 1
    return

visit[0] = 0
dfs(0)
print(ans)

Solution (Python):
import numpy as np
N, M = list(map(int, input().split()))
mtr = np.zeros((N, N), dtype=np.bool)
for _ in range(M):
    a, b = list(map(int, input().split()))
    mtr[a-1][b-1] = 1
    mtr[b-1][a-1] = 1
def v(i=0):
    return [_i for _i, _j in enumerate(mtr[i]) if _j]
def search_path(node, done):
    _d = done.copy()
    _d[node] = True
    if False not in _d:
        return [True]
    flag = [False]
    _v = [_i for _i in v(node) if not _d[_i]]
    if _v == []:
        return [False]
    return(np.concatenate([search_path(_i, _d) for _i in _v]))
print(list(search_path(0, np.zeros(N, dtype=np.bool))).count(True))

Solution (Python):
from collections import deque
N, M = map(int, input().split(' '))
neib = {}
for i in range(M):
    a, b = map(int, input().split(' '))
    if not a in neib.keys():
        neib[a] = [b]
    else:
        neib[a].append(b)
    if not b in neib.keys():
        neib[b] = [a]
    else:
        neib[b].append(a)

q = deque([])
q.append([1])
res = 0
while len(q) > 0:
    p = q.pop()
    if set(p) == set([i for i in range(1, N+1)]):
        res += 1
    cand = neib[p[-1]]
    for n in cand:
        if not n in p:
            q.append(p + [n])

print(res)

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

Solution (Python):

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

Solution (Python):
n, m = map(int, input().split())
e = [[False]*n for _ in range(n)]
for m in range(m):
  a, b = map(int, input().split())
  e[a-1][b-1] = True
  e[b-1][a-1] = True
visited = [False for _ in range(n)]

ans = 0

def dfs(v):
  global ans

  if all(visited):
    ans += 1
    return
  
  for i in range(n):
    if e[v][i] == False:
      continue
    if visited[i] == True:
      continue

    visited[i] = True
    dfs(i)
    visited[i] = False

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

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

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

b = [[0 for i in range(n)] for j in range(n)]
for i in a:
    b[i[0]][i[1]] = 1
    b[i[1]][i[0]] = 1


c = [i+1 for i in range(n-1)]
ans = 0
for i in itertools.permutations(c,n-1):
    j = [0]
    j += i
    count = 0
    for i in range(n-1):
        if b[j[i]][j[i+1]] == 1:
            count += 1
            if count == n-1:
                ans += 1
                count = 0
        else:
            break
print(ans)

Solution (Python):
import itertools

N, M = map(int, input().split())
nodes = [set(map(lambda x: int(x)-1, input().split())) for i in range(M)]
ans = 0
for path in itertools.permutations(range(N)):
    flag = True
    for i in range(N-1):
        if not ({path[i], path[i+1]} in nodes and path[0] == 0):
            flag = False
    if flag:
        ans += 1
print(ans)

Solution (Python):
import numpy
import re
import math
from collections import deque, defaultdict
import itertools

def main():
	"""
	テストコード実行
	:return:
	"""
	"""
	連結を隣接行列で管理 + DFS
	"""
	n, m = map(int, input().split())
	table = [[0] * n for _ in range(n)] 
	for _ in range(m):
		a, b = map(int, input().split())
		table[a - 1][b - 1] = 1
		table[b - 1][a - 1] = 1
	cnt = 0
	for pattern in itertools.permutations(range(n)): 
		if pattern[0] != 0: 
			break
		factor = 1
		for i in range(n - 1):
			factor *= table[pattern[i]][pattern[i + 1]] 
		cnt += factor 

	print(cnt)

if __name__ == '__main__':
	main()

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

Solution (Python):
from collections import defaultdict

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

D = defaultdict(list)

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

S = [[[1],1]] 
ans = 0
def dfs(ans,S):
    while(len(S)>0):
        SS = S.pop()
        walked,now = SS[0],SS[1]
        
        for d in D[now]:
            if d not in walked:
                ans = dfs(ans,[[walked+[d],d]])
        if len(walked)==N: return ans+1
    return ans

print(dfs(ans,S))

Solution (Python):
N, M = map(int, input().split())
from collections import defaultdict

counter = 0

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

visited = []
def h(a):
    global counter
    visited.append(a)
    if len(visited) == N:
        counter += 1
        return
    for i in g[a]:
        if not i in visited:
            h(i)
            visited.remove(i)
h(1)
print(counter)

Solution (Python):
from itertools import permutations

N, M = map(int, input().split())
pe = permutations([i for i in range(N)])

matrix = [[0] * N for _ in range(N)]
for _ in range(M):
    u, v = map(int, input().split())
    matrix[u - 1][v - 1] = 1
    matrix[v - 1][u - 1] = 1

cnt = 0
for p in pe:
    for i in range(N - 1):
        if i == 0 and p[i] != 0:
            break
        if matrix[p[i]][p[i + 1]] == 1:
            continue
        else:
            break
    else:
        cnt += 1
print(cnt)

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

def f(L,k):
    for a in L:
        if a==k:
            return True
    return False

S=[i for i in range(1,N)]
ans =0
for s in permutations(S,N-1):
    flag =True
    if not f(table[0],s[0]):
        continue
    for i in range(N-2):
        if not f(table[s[i]],s[i+1]):
            flag =False
    if flag:
        ans+=1
print(ans)

Solution (Python):
import sys

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

array = [[int(x) for x in input().split()] for x in range(m)]

if m == 0:
    print(0)
    sys.exit()

adj_array = [[] for x in range(n + 1)]
res_array = [True] + [False for x in range(n)]
for item in array:
    adj_array[item[0]].append(item[1])
    adj_array[item[1]].append(item[0])


def dfs(n, res_array, res):
    res_array[n] = True
    if False not in res_array:
        return res+1
    else:
        for next in adj_array[n]:
            if not res_array[next]:
                res = dfs(next, list(res_array), res)
    return res


res = 0
res_array[1] = True
print(dfs(1, res_array, res))

Solution (Python):
def m():
    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
    import itertools
    perm = list(itertools.permutations([j for j in range(1,n+1)]))
    for l in perm:
        if l[0] != 1:
            continue
        flag = 0
        for i in range(1, len(l)):
            if l[i] in g[l[i-1]]:
                pass
            else:
                flag = 1
                break
        if flag:
            continue
        ans+=1
    return ans

print(m())

Solution (Python):
def dfs(now,depth):
    if vis[now]:
        return 0
    if depth==n:
        return 1
    vis[now]=1
    ans=0
    for i in range(n):
        if graph[now][i]:
            ans+=dfs(i,depth+1)
    vis[now]=0
    return ans
n,m=map(int,input().split())
edge=[[int(i)for i in input().split()]for i in range(m)]
graph=[[0 for i in range(n)] for i in range(n)]
vis=[0]*n
for i in range(m):
    graph[edge[i][0]-1][edge[i][1]-1]=1
    graph[edge[i][1]-1][edge[i][0]-1]=1
print(dfs(0,1))

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

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

def search(now, gone):
    if len(gone) == N - 1:
        return 1

    s = 0
    for i in edge[now]:
        if i not in gone:
            hoge = gone.copy()
            hoge.add(now)
            s += search(i, hoge)
    return s

print(search(1, set()))

Solution (Python):
import itertools

l = input().split(' ')

N = int(l[0])
M = int(l[1])

S = [[0 for i in range(N)]for j in range(N)]

for i in range(M):
    l = input().split(' ')
    a = int(l[0]) - 1
    b = int(l[1]) - 1 
    S[a][b] = 1
    S[b][a] = 1

seq = list(range(2,N+1))
lst = list(itertools.permutations(seq))


def solve(lst):
    bef = 1
    for k in lst:
        if S[bef-1][k-1] == 1:
            bef = k
        else:
            return False

    return True


ans = 0
for list in lst:
    if solve(list):
        ans += 1

print(ans)

Solution (Python):








def dfs(v):
    all_visited = True

    if False in visited:
        all_visited = False

    if all_visited:
        return 1

    count = 0

    for i in range(n):
        if graph[v][i] == 0:
            continue

        if visited[i]:
            continue

        visited[i] = True
        count += dfs(i)
        visited[i] = False
    return count


if __name__ == '__main__':
    n, m = list(map(int, input().split()))
    graph = [[0 for __ in range(n)] for _ in range(n)]

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

    visited = [False] * n
    visited[0] = True

    print(dfs(0))

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

ans = 0
for ptn in itertools.permutations(range(1,N)):
    prev = 0
    for v in ptn:
        if not es[prev][v]:
            break
        prev = v
    else:
        ans += 1
print(ans)

Solution (Python):
n, m = map(int, input().split())
l = []
combo = []
for i in range(max(n, m)+1):
  l.append([])
  
def dfs(path, now):
  if len(set(path)) == n and not path in combo:
    combo.append(path)
    return

  for i in l[now]:
    if not i in path:
      temp = path[:]
      temp.append(i)
      dfs(temp, i)

  return

if m == 0:
  print(0)
else:

  for i in range(m):
    f, t = map(int, input().split())
    if not t in l[f]:
      l[f].append(t)
    
    if not f in l[t]:
      l[t].append(f)

  dfs([1], 1)
  print(len(combo))

Solution (Python):
N, M = map(int, input().split())
edges = [[] for _ in range(N + 1)]
res = 0
passed_nodes = set()

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

def recur(i, tot, pns):
    global res
    pns = pns.copy()

    if tot == N:
        res += 1
        return

    flag = False
    pns.add(i)

    for e in edges[i]:
        if e not in pns:
            recur(e, tot + 1, pns)
            flag = True

    if not flag:
        return

recur(1, 1, passed_nodes.copy())

print(res)

Solution (Python):
N, M  = map(int,input().strip().split())
edges = [[x for x in  map(int,input().strip().split())] for i in range(M)]
import numpy as np
a = np.zeros([N+1,N+1],dtype = np.int32) 
for e in edges:
    a[e[0],e[1]] = 1
a = a.T+a
def iter(visited_nodes):
    if len(visited_nodes) == N:
        return 1
    else:
        now = visited_nodes[-1] 
        return sum(iter(visited_nodes+[node]) for node, aij in enumerate(a[now]) if aij == 1 and not (node in visited_nodes))
print(iter([1]))

Solution (Python):
n,m = map(int,input().split())
H = [[0 for _ in range(n)] for _ in range(n) ]

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

def dfs(node,visited):
    global ans
    if visited.count(0) == 0:
        ans += 1 
        return 0
    else:
        visited[node] = 1
        for node_,edge_ in enumerate(H[node]):
            if edge_ == 1 and visited[node_] != 1:
                visited[node_] = 1
                visited[node] = 1
                dfs(node_,visited)
                
                
                visited[node_] = 0
dfs(0,l)
print(ans)

Solution (Python):
n,m = map(int,input().split())
H = [[0 for _ in range(n)] for _ in range(n) ]

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

def dfs(node,visited):
    global ans
    if visited.count(0) == 0:
        ans += 1 
        return 0
    else:
        visited[node] = 1
        for node_,edge_ in enumerate(H[node]):
            if edge_ == 1 and visited[node_] != 1:
                visited[node_] = 1
                visited[node] = 1
                dfs(node_,visited)
                visited[node_] = 0
dfs(0,l)
print(ans)

Solution (Python):



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

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

def dfs(node,visited):
    global ans
    if visited.count(0) == 0:
        ans += 1 
        return 0
    else:
        visited[node] = 1
        for node_,edge_ in enumerate(H[node]):
            if edge_ == 1 and visited[node_] != 1:
                visited[node_] = 1
                visited[node] = 1
                dfs(node_,visited)
                visited[node_] = 0

dfs(0,l)
print(ans)

Solution (Python):


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

H = [[0 for _ in range(n)] for _ in range(n) ]

edge_list = []

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

def dfs(node,x):
    global ans
    if x.count(0) == 0:
        ans += 1 
        return 0


    else:
        visited = x
        visited[node] = 1
        for node_,edge_ in enumerate(H[node]):
            if edge_ == 1 and visited[node_] != 1:
                visited[node_] = 1
                visited[node] = 1
                dfs(node_,visited)
                visited[node_] = 0
                



dfs(0,l)
print(ans)

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 i 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):
def dfs(now,depth):
    if vis[now]:
        return 0
    if depth==n:
        return 1
    vis[now]=1
    ans=0
    for i in range(n):
        if graph[now][i]:
            ans+=dfs(i,depth+1)
    vis[now]=0
    return ans
n,m=map(int,input().split())
edge=[[int(i) for i in input().split()]for i in range(m)]
graph=[[0 for i in range(n)]for i in range(n)]
for i in range(m):
    graph[edge[i][0]-1][edge[i][1]-1]=1
    graph[edge[i][1]-1][edge[i][0]-1]=1
vis=[0]*n
print(dfs(0,1))