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):
from collections import defaultdict, Counter
from itertools import product, groupby, count, permutations, combinations
from math import pi, sqrt
from collections import deque
from bisect import bisect, bisect_left, bisect_right
from string import ascii_lowercase
from functools import lru_cache
import sys
sys.setrecursionlimit(10000)
INF = float("inf")
YES, Yes, yes, NO, No, no = "YES", "Yes", "yes", "NO", "No", "no"
dy4, dx4 = [0, 1, 0, -1], [1, 0, -1, 0]
dy8, dx8 = [0, -1, 0, 1, 1, -1, -1, 1], [1, 0, -1, 0, 1, 1, -1, -1]


def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W


def ceil(a, b):
    return (a + b - 1) // b


def main():
    N, M = map(int, input().split())

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

    ans = 0
    for p in permutations(range(1, N)):
        now = 0
        ok = True
        for n in p:
            ok &= g[now][n]
            now = n
        ans += ok

    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):

from collections import deque

ans = 0

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

def main():
    global ans
    n, m = map(int, input().split())
    linked_list = [[] for _ in range(n+1)]
    for _ in range(m):
        a, b = map(int, input().split())
        linked_list[a].append(b)
        linked_list[b].append(a)
    used = [1]
    dfs(1, n, used, linked_list)
    print(ans)

if __name__ == '__main__':
    main()

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

graph = [ [False] * 8 for _ in range(8) ]
visited = [False] * n

def dfs(a, N, visited):
    finish = True
    for i in range(N):
        if not visited[i]:
            finish = False
    if finish:
        return 1
    ans = 0
    for i in range(N):
        if not graph[a][i] or visited[i]:
            continue
        visited[i] = True
        ans += dfs(i,N,visited)
        visited[i] = False
    return ans

for i in range(m):
    graph[ab[i][0]-1][ab[i][1]-1], graph[ab[i][1]-1][ab[i][0]-1] = True, True

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

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)
cnt = [0]
def dfs(V, s):
  V[s] = 1
  if sum(V) == N:
    cnt[0] += 1
  else:
    for adj in G[s]:
      if V[adj] == 0:
        dfs(V[:adj] + [1] + V[adj + 1:], adj)
dfs([0] * N, 0)
print(cnt[0])

Solution (Python):
import copy

N, M = [ int(x) for x in input().split() ]

class Node:
    def __init__(self, id):
        self.id = id
        self.path = []
    def __str__(self):
        return "id: " + str(self.id) + " path: " + str(self.path)

nodes = []
for i in range(N):
    nodes.append(Node(i))

for i in range(M):
    from_id, to_id = [ int(x) - 1 for x in input().split() ]
    nodes[from_id].path.append(to_id)
    nodes[to_id].path.append(from_id)

def if_all_passed(passed_nodes):
    if len(passed_nodes) == N:
        return True
    else:
        return False

def go_child(id_new, passed_nodes):
    passed_nodes.append(id_new)
    if if_all_passed(passed_nodes):
        return 1

    count = 0
    for i in nodes[id_new].path:
        if not i in passed_nodes:
            count += go_child(i, copy.deepcopy(passed_nodes))
    return count

count = go_child(0, [])
print(count)

Solution (Python):
import sys
import numpy as np

N, M = [int(i) for i in sys.stdin.readline().split()]
edges = [[] for _ in range(N)]
for l in sys.stdin.readlines():
  a, b = [int(i)-1 for i in l.strip().split()]
  edges[a].append(b)
  edges[b].append(a)

def search(p, current_paths):
  
  finished_paths = [path for path in current_paths if p in path and len(path) == N]
  unfinished_paths = [tuple(list(path) + [p]) for path in current_paths if p not in path]
  if not unfinished_paths:
    return finished_paths

  paths = []
  for target in edges[p]:
    new_paths = search(target, unfinished_paths)
    paths += new_paths
  paths += finished_paths
  return set(paths + finished_paths)
  
res = search(0, [()])
print(len(res))

Solution (Python):
import sys
from collections import deque
import copy
import heapq
import math

from math import *

def get_read_func(fileobject):
    if fileobject == None :
        return raw_input
    else:
        return fileobject.readline


count = 0

def dfs(N, adj_list, nd, visit_num, is_visit):
    global count
    is_visit[nd] = True
    if visit_num == N:
        count += 1
    for adj in adj_list[nd]:
        if is_visit[adj] == False:
            dfs(N, adj_list, adj, visit_num + 1, is_visit)
            is_visit[adj] = False


def main():
    global count
    if len(sys.argv) > 1:
        f = open(sys.argv[1])
    else:
        f = None
    read_func = get_read_func(f);
    input_raw = read_func().strip().split()
    [N, M] = [long(input_raw[0]), long(input_raw[1])]
    adj_list = {}
    for i in range(M):
        input_raw = read_func().strip().split()
        [a, b] = [long(input_raw[0]), long(input_raw[1])]
        if a not in adj_list:
            adj_list[a] = [b]
        else:
            adj_list[a].append(b)

        if b not in adj_list:
            adj_list[b] = [a]
        else:
            adj_list[b].append(a)
    is_visit = [False for i in range(N + 1)]

    dfs(N, adj_list, 1, 1, is_visit)

    print count






if __name__ == '__main__':
    main()

Solution (Python):
import numpy as np
import math





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

edges = []
E = np.zeros((N, N), dtype=int)

for m in range(M):
    s, t = map(int, input().split())
    s = s - 1
    t = t - 1
    E[s][t] = 1
    E[t][s] = 1




def count(path, E):
    if len(path) == N:
        return 1
    else:
        edges = []
        cur = path[-1]
        ret = 0
        for n in range(N):
            if E[cur][n] == 1 and n not in path:
                npath = path + [n]
                ret += count(npath, E)
        return ret

ret = count([0], E)
print(ret)

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

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

visited = [0] * N
visited[0] = 1

ans = 0

def DFS(v,cnt):
  
  if sum(visited) == N:
    cnt += 1
    return cnt
  for i in range(M):
    if E[i][0] == v + 1:
      v_next = E[i][1] - 1
    elif E[i][1] == v + 1:
      v_next = E[i][0] - 1
    else:
      continue
    
    if visited[v_next] == 1:
      continue
    
    
    visited[v_next] = 1
    cnt = DFS(v_next,cnt)
    visited[v_next] = 0
    
  return cnt

ans = DFS(0,0)

print(ans)

Solution (Python):
from itertools import permutations
n, m = map(int, input().split())
pair = [tuple(map(int, input().split())) for i in range(m)]
num = [i for i in range(1,n+1)]
ans = 0
for p in permutations(num):
    if p[0] != 1:
        continue
    already = []
    state = True
    for i in range(n-1):
        if p[i] in already:
            state = False
            break
        if (min(p[i], p[i+1]), max(p[i], p[i+1])) not in pair:
            state = False
            break
        already.append(p[i])
    if state:
        ans += 1
print(ans)

Solution (Python):
from itertools import permutations
n, m = map(int, input().split())
pair = [tuple(map(int, input().split())) for i in range(m)]
num = [i+1 for i in range(n)]
box = []
for p in permutations(num):
    if p[0] == 1:
        box.append(p)
ans = 0
for p in box:
    already = []
    state = True
    for i in range(n-1):
        if p[i] in already:
            state = False
            break
        if (min(p[i], p[i+1]), max(p[i], p[i+1])) not in pair:
            state = False
            break
        already.append(p[i])
    if state:
        ans += 1
print(ans)

Solution (Python):
import itertools


def f(j, adj):
    for i, node in enumerate(j):
        if i == 0:
            if node not in adj[1]:
                return False
        else:
            if j[i - 1] not in adj[node]:
                return False
    return True


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

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

count = 0
for j in itertools.permutations(range(2, n + 1)):
    count += f(j, adj)

print(count)

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

ans = 0


def dfs(pStack):
    global ans
    if len(pStack) == n:
        ans += 1
        pStack.pop()
        return
    cNode = pStack[-1]
    for nNode in range(n):
        if path[cNode][nNode] and not nNode in pStack:
            pStack.append(nNode)
            dfs(pStack)
    pStack.pop()


dfs([0])
print(ans)

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

V = [ 0 for i in range(N)] 
V[0] = 1 

def DPS(now, V):
    res = 0 
    if 0 not in V:
        return 1
    for i in range(N): 
        if (E[now][i] == 1) and (V[i] == 0): 
            V[i] = 1
            res = res + DPS(i, V)
            V[i] = 0
    return res

print(DPS(0, V))

Solution (Python):

import sys
stdin = sys.stdin

def li(): return [int(x) for x in stdin.readline().split()]
def li_(): return [int(x)-1 for x in stdin.readline().split()]
def lf(): return [float(x) for x in stdin.readline().split()]
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(ns())
def nf(): return float(ns())

from itertools import permutations


n,m = li()
edges = set()
for _ in range(m):
    a,b = li()
    edges.add((a,b))
    edges.add((b,a))
    
paths = permutations([str(i) for i in range(2,n+1)],n-1)
cnt = 0
for path in paths:
    path = [1] + [int(i) for i in path]
    
    exist = True
    for i in range(n-1):
        if not (path[i], path[i+1]) in edges:
            exist = False

    if exist:
        cnt += 1
        
print(cnt)

Solution (Python):
import itertools
N,M = map(int,input().split())
src = [tuple(map(lambda x:int(x)-1,input().split())) for i in range(M)]

es = [set() for i in range(N)]
for a,b in src:
    es[a].add(b)
    es[b].add(a)

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

Solution (Python):
n,m= map(int,input().split())
a = [input().rstrip().split() for j in range(m)]
cnt = 0

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

for i in range(0,m):
    x = int(a[i][0])-1
    y = int(a[i][1])-1
    graph[x][y]=graph[y][x]=True

    
def DFS(v,n,visited):
    
    all_visited = True 
    for i in range(0,n):
        if(visited[i]==0):
            all_visited = False
    if(all_visited):
        return 1

    ret = 0

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

        visited[i] = True
        ret += DFS(i,n,visited)
        visited[i] = False

    return ret
visited[0]=True
print(DFS(0,n,visited))

Solution (Python):
import itertools
na = lambda: list(map(int, input().split()))

n, m = na()
t = [[0] * 10 for _ in range(10)]
for _ in range(m):
    a, b = na()
    a -= 1
    b -= 1
    t[a][b] = t[b][a] = 1

ans = 0
for l in itertools.permutations(range(n)):
    if l[0]: continue
    flag = 1
    for i in range(1, n):
        if t[l[i]][l[i-1]] == 0:
            flag = 0
            break
    if flag:
        ans += 1

print(ans)

Solution (Python):
n,m=map(int, input().split())
ab=[list(map(int, input().split())) for _ in range(m)]
graph=[[False for _ in range(n)] for _ in range(n)]
visited=[False for _ in range(n)]
visited[0]=True

for x in ab:
    graph[x[0]-1][x[1]-1]=True
    graph[x[1]-1][x[0]-1]=True
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]:
            continue
        visited[i]=True
        ret+=dfs(i,n,visited)
        visited[i]=False
    return ret
print(dfs(0,n,visited))

Solution (Python):
import copy
def explore(key, flags):
    flags = copy.copy(flags)
    if flags[key-1]:
        return 0
    flags[key-1] = True
    if False not in flags:
        return 1
    elif key in graph:
        value = graph[key]
        ans = 0
        for i in value:
            ans += explore(i, flags)
        return ans
    else:
        return 0

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

flags = [False for i in range(n)]
ans = explore(1, flags)
print(ans)

Solution (Python):

"""
Created on Sun Aug 26 11:59:46 2018

@author: maezawa
"""

n, m = list(map(int, input().split()))
array = [[0]*n for _ in range(n)]
for i in range(m):
    ai, bi = list(map(int, input().split()))
    array[ai-1][bi-1] = 1
    array[bi-1][ai-1] = 1



done = []

def f(i,done):
    if i in done:
        return 0
    if len(done) == n-1:
        return 1
    if sum(array[i]) == 1 and i != 0:
        return 0
    
    
    donecopy = done + [i]
    
    ans = sum([f(bi,donecopy) for bi in range(n) if array[i][bi] != 0])
    return ans

print(f(0,done))

Solution (Python):

import itertools
N, M=map(int,input().split())
a=[0]*0
b=[0]*0
order=list(itertools.permutations(range(N-1) ) )
c_patern=0
for i in range(M):
    a_tmp, b_tmp=map(int,input().split())
    a.append(a_tmp)
    b.append(b_tmp)
for i in range(len(order)):
    for j in range(N-1):
        flg = False
        if j==0:
            for k in range(M):
                if (a[k]==1 and b[k]==order[i][0]+2):
                    flg=True
                    break
        else:
            for k in range(M):
                if (a[k]==order[i][j-1]+2 and b[k]==order[i][j]+2) or (a[k]==order[i][j]+2 and b[k]==order[i][j-1]+2):
                    flg=True
                    break
        if flg==False:
            break
    if flg==True:
        c_patern+=1
print(c_patern)

Solution (Python):
from itertools import permutations 

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

answer = 0 
for path in permutations(range(2, N+1)):
    path = [1] + list(path)
    found = True 
    for i in range(1, len(path)):
        if not [path[i], path[i-1]] in a and not [path[i-1], path[i]] in a:
            found = False
            break
    if found:
        answer += 1
print(answer)

Solution (Python):
n,m = map(int,input().split())
graph = [[False for i in range(n)] for i 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,True

def dfs(num,visited):
    if visited==[True]*n:
        return 1
    res = 0
    for i in range(n):
        if graph[num][i] and not visited[i]:
            visited[i] = True
            res += dfs(i,visited)
            visited[i] = False
    return res

visit = [True] + [False] * (n-1)
print(dfs(0,visit))

Solution (Python):
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,datetime
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inpl(): return list(map(int, input().split()))
def inpl_s(): return list(input().split())

N,M = inpl()
lines = defaultdict(set)
for _ in range(M):
	a,b = inpl()
	a,b = a-1,b-1
	lines[a].add(b)
	lines[b].add(a)

ans = 0

def search(s,ed,num):
	global ans

	if num == N:
		ans += 1
	else:
		for t in lines[s]:
			if not ed & (1<<t):
				search(t,ed+(1<<t),num+1)


search(0,1,1)
print(ans)

Solution (Python):
def search(node):
    global ans

    if sum(is_visit) == n:
        ans += 1

    for i in range(n):
        if is_neighbor[node][i]:
            if not is_visit[i]:
                is_visit[i] = True
                search(i)
                is_visit[i] = False

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

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

is_visit = [False for _ in range(n)]

ans = 0

is_visit[0] = True
search(0)
print(ans)

Solution (Python):
from collections import defaultdict as dd
from itertools import permutations as pe

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

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

c=0

for i in pe(range(2,n+1)):
  a=d[1]
  f=True
  for j in i:
    if not j in a:
      f=False
      break
    else:
      a=d[j]
  if f:c+=1

print(c)

Solution (Python):
import itertools
n,m = map(int,input().split())
p = []
for i in range(m):
    p.append(list(map(int, input().split())))
l = [[] for i in range(n+1)]
for pi in p:
    l[pi[0]].append(pi[1])
    l[pi[1]].append(pi[0])
c = list(itertools.permutations(range(2,n+1), n-1))
ans = 0
for i in c:
  if i[0] not in l[1]:
    continue
  else:
    for j in range(1,len(i)):
      if i[j] not in l[i[j-1]]:
        break
    else:
      ans += 1
print(ans)

Solution (Python):
def ary(r, c, v): return [[v for _ in range(c)] for _ in range(r)]
n, m = map(int, input().split())
e = ary(n, n, False)
for i in range(m):
    a, b = map(int, input().split())
    
    a -= 1
    b -= 1
    e[a][b] = True
    e[b][a] = True
ps = set()
ps.add('0')

for cnt in range(1, n):
    t = set()
    for p in ps:
        for i in map(str, range(1, n)):
            if not(i in p):
                t.add(p + i)
    ps = t.copy()

ans = 0
for p in ps:
    flg = True
    for i in range(n - 1):
        a = int(p[i])
        b = int(p[i + 1])
        if not e[a][b]:
            flg = False
            break
    if flg:
        ans += 1

print(ans)

Solution (Python):
from itertools import permutations

N,M = map(int, input().split())
AB = set()
for i in range(M):
    A,B = map(int, input().split())
    AB.add((A-1,B-1))

s = ""
for i in range(1,N):
    s = s + str(i)
    
paths = permutations(s,N-1)
paths = list(paths)

ans = 0
for path in paths:
    path = [0] + [int(i) for i in path]

    for i in range(N-1):
        if (not (path[i],path[i+1]) in AB) and (not (path[i+1], path[i]) in AB):
            break
        
        if i == N-2:
            ans += 1
    
print(ans)

Solution (Python):
def na(): return map(int, input().split())
n, m = na()
edges = [[False for _ in range(n)] for _ in range(n)]
for i in range(m):
    a, b = na()
    a -= 1
    b -= 1
    edges[a][b] = True
    edges[b][a] = True

pathes = {'0'}
for i in range(n-1):
    buf = set()
    for pre_path in pathes:
        for v in map(str, range(1, n)):
            if not(v in pre_path):
                buf.add(pre_path + v)
    pathes = buf.copy()



ans = 0
for path in pathes:
    flg = True
    for i in range(1, n):
        a, b = map(int, [path[i-1], path[i]])

        if not edges[a][b]:
            flg = False
            break
    if flg:
        ans += 1
print(ans)

Solution (Python):
from itertools import permutations
N, M = map(int, input().split())
g = [[0] * N for _ in range(N)]
for _ in range(M):
    a, b = map(int, input().split())
    a, b = a - 1, b - 1
    g[a][b] = g[b][a] = 1

cnt = 0
for e in permutations(range(1, N)):
    for a, b in zip([0] + list(e[:-1]), e):
        if not g[a][b]:
            break
    else:
        cnt += 1
print(cnt)

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

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

flag = [False] * (n+1)
flag[0] = True
cnt = 0

def dfs(i, flag):
    flag[i] = True
    for b in A[i]:
        if not flag[b]:
            dfs(b, flag[:])
    if all(flag) == True:
        global cnt
        cnt += 1

dfs(1, flag[:])
print(cnt)

Solution (Python):
n, m = [int(i) for i in input().split()]
A = [[] for i in range(n+1)]
B = [[] for i in range(n+1)]

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

flag = [False] * (n+1)
flag[0] = True
cnt = 0

def dfs(i, flag):
    flag[i] = True
    for b in A[i]+B[i]:
        if not flag[b]:
            dfs(b, flag[:])
    if all(flag) == True:
        global cnt
        cnt += 1

dfs(1, flag[:])
print(cnt)

Solution (Python):
n, m = [int(i) for i in input().split()]
A = [[] for i in range(n+1)]
B = [[] for i in range(n+1)]

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

flag = [False] * (n+1)
flag[0] = True
cnt = 0

def dfs(i, flag):
    flag[i] = True
    for b in A[i]:
        if not flag[b]:
            dfs(b, flag[:])
    for b in B[i]:
        if not flag[b]:
            dfs(b, flag[:])
    if all(flag) == True:
        global cnt
        cnt += 1

dfs(1, flag[:])
print(cnt)

Solution (Python):

N, M = map(int, input().split())
G = [list(map(int, input().split())) for _ in range(M)]
edges = [set() for _ in range(N)]

for a, b in G:
    edges[a - 1].add(b - 1)
    edges[b - 1].add(a - 1)

def dfs(start, edges, path):
    path.append(start)
    if len(path) == N:
        path.pop()
        return 1
    ans = 0
    for u in edges[start]:
        if u in path:
            continue
        ans += dfs(u, edges, path)
    path.pop()
    return ans    

print(dfs(0, edges, []))

Solution (Python):
from itertools import permutations
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].append(b-1)
    edges[b-1].append(a-1)
ans = 0
for X in permutations(range(N),N):
    if X[0] != 0:
        continue
    Flag = True
    for i in range(1,N):
        if X[i] in edges[X[i-1]]:
            pass
        else:
            Flag = False
            break
    if Flag:
        ans += 1
print(ans)

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

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


def dfs(k, cnt):
    global ans

    vis[k] = 1

    if cnt == n - 1:
        ans += 1
    else:
        for i in G[k]:
            if vis[i] == 0:
                dfs(i, cnt + 1)

    vis[k] = 0


dfs(0, 0)
print(ans)

Solution (Python):
def dfs(v, path):
    path.append(v)
    if len(path) == n:
        path.pop()
        return 1
    ans = 0
    for u in links[v]:
        if u in path:
            continue
        ans += dfs(u, path)
    path.pop()
    return ans


n, m = map(int, input().split())
links = [set() for _ in range(n)]
for _ in range(m):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    links[a].add(b)
    links[b].add(a)
print(dfs(0, []))

Solution (Python):
from copy import deepcopy

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

edges = {}
for i in range(m):
    a, b = list(map(int, input().split()))
    if not a in edges.keys():
        edges[a] = [b]
    else:
        edges[a].append(b)
    if not b in edges.keys():
        edges[b] = [a]
    else:
        edges[b].append(a)

ans = 0

nodes = edges[1]
visited = [1] + [0]*(n-1)
nodes_visited = [(node, visited) for node in nodes]
while len(nodes_visited) > 0:

    
    node, vstd = nodes_visited[0]
    vstd = deepcopy(vstd)
    nodes_visited = nodes_visited[1:]

    vstd[node-1] = 1
    if min(vstd) > 0:
        ans += 1
        continue

    for node_next in edges[node]:
        if vstd[node_next-1] == 1:
            continue
        else:
            nodes_visited.append((node_next, vstd))

print(ans)

Solution (Python):




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


a = [0] * M
b = [0] * M


graph = [[False for i in range(N)] for j in range(N)]


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

cnt = 0
p = [0] * N
def dfs(pos, mask):
    
    global cnt
    
    if pos == N:
        
        if p[0] == 0:
            for i in range(N-1):
                
                if graph[p[i]][p[i+1]] == False:
                    break
                
                if i == N-2:
                    cnt += 1
        return
    for i in range(N):
        
        
        if mask & (1<<i):
            p[pos] = i
            
            
            dfs(pos+1, mask^(1<<i))

dfs(0, (1<<N)-1)
print(cnt)

Solution (Python):


import itertools

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


a = [0] * M
b = [0] * M


graph = [[False for i in range(N)] for j in range(N)]


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



perm_list = list(itertools.permutations(range(N)))

cnt = 0
for i in range(len(perm_list)):
    
    if perm_list[i][0] != 0:
        break
    for j in range(len(perm_list[i])-1):
        
        if graph[perm_list[i][j]][perm_list[i][j+1]] == False:
            break
        
        if j == len(perm_list[i])-2:
            cnt += 1
print(cnt)

Solution (Python):


from itertools import permutations


N, M = [int(elem) for elem in input().split(' ')]
edge_set = set([tuple([int(elem) - 1 for elem in input().split(' ')]) for _ in range(M)])
edge_set |= {(edge[1], edge[0]) for edge in edge_set}
assert len(edge_set) == 2 * M

num_possible_path = 0
for permutation in permutations(range(1, N), N-1):
    permutation = [0] + list(permutation)
    for i in range(N - 1):
        if tuple(permutation[i:i+2]) not in edge_set:
            break
        else:
            continue
    else:
        num_possible_path += 1

print(num_possible_path)

Solution (Python):


import itertools

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

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

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

res = 0
p =  list(itertools.permutations(range(n)))

for l in p:
    if l[0] != 0: continue
    flg = True
    for i in range(n-1):
        if not(l[i+1] in dests[l[i]]):
            flg = False
            break

    if flg == True: res += 1

print(res)