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
from collections import deque

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

graph = defaultdict(list)
edges = []


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

ans = 0
def dfs(graph, node_start, visited):
    global ans
    if sum(visited) == len(graph):
        ans += 1
        return
    for node_end in graph[node_start]:
        
        if not visited[node_end]:
            visited[node_end] = True
            dfs(graph, node_end, visited)
            visited[node_end] = False
    return

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

Solution (Python):
import itertools
n,m = map(int,input().split())
info = [list(map(int,input().split())) for i in range(m)]

tree= [[] for i in range(n)]
for i in range(m):
  tree[info[i][0]-1].append(info[i][1]-1)
  tree[info[i][1]-1].append(info[i][0]-1)

num = []  
for i in range(n):
  num.append(i)
  
ans = 0
for li in itertools.permutations(num, n):
  flag =True
  if li[0]==0:
    for i in range(n-1):
      if li[i+1] not in tree[li[i]]:
        flag =False
    if flag:
      ans = ans +1
    
  else:
    print(ans)
    exit()

Solution (Python):
import itertools

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

Solution (Python):

import sys
sys.setrecursionlimit(1000000000)

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

c = [[0]*N for _ in range(N)]
for x, y in zip(a, b):
    c[x-1][y-1] = 1
    c[y-1][x-1] = 1
visited = [-1]*N
visited[0] = 1
ans = 0

def dfs(n):
    global ans
    if sum(visited) == N:
        ans += 1
        return
    else:
        for i, x in enumerate(c[n]):
            if x == 1 and visited[i] == -1:
                visited[i] = 1
                dfs(i)
                visited[i] = -1
    return

dfs(0)
print(ans)

Solution (Python):
from collections import *
n,m=map(int,input().split())
d=defaultdict(list)
for s in m*[0]:
    a,b=map(int,input().split())
    d[a].append(b)
    d[b].append(a)
def DFS_dict(point,TFlist):
    if all(TFlist):
        return 1
    ans=0
    for i in d[point]:
        if TFlist[i-1]:
            continue
        TFlist[i-1]=True
        ans+=DFS_dict(i,TFlist)
        TFlist[i-1]=False
    return ans
TFlist=[True]+[False]*(n-1)
print(DFS_dict(1,TFlist))

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

d=defaultdict(list)

for s in m*[0]:
    a,b=map(int,input().split())
    d[a].append(b)
    d[b].append(a)





def DFS_dict(point,TFlist):


    if not False in TFlist:
        return 1
    ans=0
    for i in d[point]:
        if TFlist[i-1]:
            continue  
        TFlist[i-1]=True 
        ans+=DFS_dict(i,TFlist)
        TFlist[i-1]=False
    return ans

TFlist=[True]+[False]*(n-1)
print(DFS_dict(1,TFlist))

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


def DFS(point,TFlist):

  if not False in TFlist:
    return 1
  ans=0
  for i in range(n):
    if not AdjacencyMatrix[point][i]:
      continue  
    if TFlist[i]:
      continue  
    TFlist[i]=True 
    ans+=DFS(i,TFlist) 
    TFlist[i]=False 
  return ans

TFlist=[True]+[False]*(n-1)
print(DFS(0,TFlist))

Solution (Python):
from itertools import permutations

N, M = [int(i) for i in input().split()]
edge_dict = dict()
for i in range(M):
    _from, _to = [int(i) for i in input().split()]
    if edge_dict.get(_from) is None:
        edge_dict[_from] = list()
    if edge_dict.get(_to) is None:
        edge_dict[_to] = list()
    edge_dict[_from].append(_to)
    edge_dict[_to].append(_from)

cnt = 0
for combi in permutations(range(2,N+1)):
    flg = 0
    combi = [1] + list(combi)
    for i in range(N-1):
        candidate = edge_dict.get(combi[i])
        if candidate is None:
            flg = 1
            break
        if combi[i+1] not in candidate:
            flg = 1
            break
    if flg == 0:
        cnt += 1
print(cnt)

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

def dfs(cur,*a): 
  if cur in a:
    return 0
  else:
    if len(a) == N-1:
      return 1
    else:
      a = list(a)
      a.append(cur)
      count = 0
      for i in data[cur]:
        count += dfs(i,*a)
      return count
print(dfs(1,*[]))

Solution (Python):
import copy

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

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


def dfs(graph, now, done):
    result = 0
    doneCache = copy.deepcopy(done)
    doneCache.append(now)
    if len(doneCache) == N:
        return 1
    for a,b in graph:
        if a == now:
            if b not in doneCache:
                result += dfs(graph, b, doneCache)
        if b == now:
            if a not in doneCache:
                result += dfs(graph, a, doneCache)

    return result

print(dfs(abList, 1, []))

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

def dfs(edge, reach):
  if(all(reach)):
    return 1
  ret = 0
  for e in edges[edge]:
    if(reach[e]):
      continue
    reach[e] = True
    ret += dfs(e, reach)
    reach[e] = False
  return ret

edges = [[] for _ in range(N)]
all_reach = [False for _ in range(N)]

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

all_reach[0] = True
print(dfs(0, all_reach))

Solution (Python):
n, m = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(m)]
edges = [[] for _ in range(n)]
for a, b in ab:
    edges[a-1].append(b-1)
    edges[b-1].append(a-1)
reached = [False for i in range(n)]
def dfs(edge, r):
    if all(r):
        return 1
    ret = 0
    for e in edges[edge]:
        if r[e]:
            continue
        r[e] = True
        ret += dfs(e, r)
        r[e] = False
    return ret
reached[0] = True
print(dfs(0, reached))

Solution (Python):
import itertools

N,M=map(int,input().split())
g=[[0]*N for _ in range(N)]

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

num=0
for a in itertools.permutations(range(N)):
    
    connect=1
    if a[0]==0:
        for i in range(N-1):
            connect=connect*g[a[i]][a[i+1]]
            
        num=num+connect
        
print(num)

Solution (Python):
n, m = map(int, input().split())
array = [[int(x) for x in input().split()] for y in range(m)]
modify = [[] for x in range(n + 1)]

for value1, value2 in array:
    modify[value1].append(value2)
    modify[value2].append(value1)


def solver(start, array, visited, cnt):
    if visited[start]:
        return cnt
    else:
        visited[start] = True

    for i in array[start]:
        if len(set(visited)) == 1:
            return cnt+1
        else:
            cnt = solver(i, array, list(visited), cnt)

    return cnt



start = modify[1]
res = 0
for i in start:
    visited = [False if x != 0 and x != 1 else True for x in range(n + 1)]
    res += solver(i, modify, visited, 0)

print(res)

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

route = [0]*N  
connect=[[0]*N for _ in range(N)]
def dfs(now, depth):
    
    
    if route[now]: return 0
    
    if depth == N: return 1
    
    route[now] = 1
    ans = 0
    for i in range(N):
        if connect[now][i]:
            ans += dfs(i, depth+1)
    route[now] = 0
    return ans

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



print(dfs(0,1))

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

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

for x,y in EDGE:
    EDGELIST[x].append(y)
    EDGELIST[y].append(x)


import itertools

ITER=list(itertools.permutations(range(2,N+1),N-1))
ANS=0

for ite in ITER:
    ROUTE=(1,)+ite

    for j in range(1,N):
        if ROUTE[j] in EDGELIST[ROUTE[j-1]]:
            continue
        else:
            break
    else:
        ANS+=1

print(ANS)

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

Solution (Python):
import itertools
N, M = map(int, input().split())
ab = []
for i in range(M):
    ab.append(list(map(int, input().split())))
ans = 0
if M >= N - 1:
    for i in list(itertools.combinations(ab, N - 1)):
        g = {}
        for j in range(N):
            g[j + 1] = []
        for j, k in i:
            g[j].append(k)
            g[k].append(j)
        if len(g[1]) == 1:
            p = 1
            q = g[p][0]
            for j in range(N - 2):
                l = g[q]
                if len(l) != 2:
                    break
                l.remove(p)
                p = q
                q = l[0]
            else:
                ans += 1
print(ans)

Solution (Python):

count=0
def check(now,v,n):
    global count
    v[now]=1
    if sum(v)==n:
        count+=1
    else:
        for i in range(n):
            if v[i]==0 and g[now][i]==1:
                check(i,v[:],n)

n,m=map(int,input().split())
g=[[0 for i in range(n)]for i in range(n)]
for i in range(m):
    a,b=map(int,input().split())
    g[a-1][b-1]=1
    g[b-1][a-1]=1
check(0,[0 for i in range(n)],n)
print(count)

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

Solution (Python):

n,m=map(int,input().split())
from collections import defaultdict
branch=defaultdict(set)
for i in range(m):
    a,b=map(int,input().split())
    branch[a]|={b,}
    branch[b]|={a,}

def roop(now,nonvisit,ans):
    nownonvisit=nonvisit.copy()
    nownonvisit-={now,}
    if len(nownonvisit)==0:return ans+1
    nex=branch[now].copy()
    for x in nex&nownonvisit:
        ans=roop(x,nownonvisit,ans)
    return ans

print(roop(1,{i for i in range(1,n+1)},0))

Solution (Python):
import itertools

n,m = map(int, input().split())
edges = [list(map(int, input().split())) for _ in range(m)]
num = list(range(1,n+1))
ans = 0
for l in itertools.permutations(num):
    if l[0]!=1:
        continue
    flag = True
    for i in range(len(l)-1):
        if not([l[i],l[i+1]] in edges or [l[i+1],l[i]] in edges):
            flag = False
            break
    if flag:
        
        ans+=1
print(ans)

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


dp = [[0]*N for i in range(1 << N)]
dp[1][0]=1

for S in range(1 << N):
    for v in range(N):
        
        if S & (1<<v) == 0:
            continue
        
        
        sub = S ^ (1 << v)

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

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

print(ans)

Solution (Python):
N, M = [int(x) for x in input().split()]
G = [[] for x in range(N)]
V = (1 << N) - 1
count = 0

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


def dfs(s, v):
    global count
    if v == V:
        count += 1
    for t in G[s]:
        if (v >> t & 1) == 0:
            dfs(t, v | 1 << t)


dfs(0, 1)

print(count)

Solution (Python):


from collections import deque

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

all = set(range(1, N + 1))
q = deque()
q.append((1, [1]))

ans = 0
while q:
    n, v = q.popleft()
    if set(v) == all:
        ans += 1
        continue
    for to in Ms[n]:
        if not to in v:
            q.append((to, v + [to]))

print(ans)

Solution (Python):

import itertools


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

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

seq = [i + 1 for i in range(1, N)]


count = 0
for l in itertools.permutations(seq):
    
    connected = True
    for i in range(len(l) - 1):
        a = min(l[i], l[i+1])
        b = max(l[i], l[i+1])
        if i == 0 and [1, l[i]] not in C:
            connected = False
            break
        if [a, b] not in C:
            connected = False
            break
    if connected:
        
        count += 1

print(count)

Solution (Python):
from itertools import permutations
N, M = map(int, input().split())
edge = []
for _ in range(M):
    a, b = map(int, input().split())
    edge.append(set((a, b)))

p = list(map(lambda x: [1] + list(x), permutations([i for i in range(2, N + 1)])))

ans = 0

for root in p:
    for i in range(len(root) - 1):
        if not set((root[i], root[i + 1])) in edge:
            break
    else:
        ans += 1

print(ans)

Solution (Python):


import itertools

def array2d(dim1, dim2, init=None):
    return [[init for _ in range(dim2)] for _ in range(dim1)]

II = lambda: int(input())
MI = lambda: map(int, input().split())
MIL = lambda: list(MI())
MIS = lambda: input().split()


def main():
    N, M = MI()
    nb = array2d(N, N, False)
    for i in range(M):
        a, b = MI()
        a -= 1
        b -= 1
        nb[a][b] = nb[b][a] = True
    cnt = 0
    for perm in itertools.permutations(range(1, N)):
        p = [0] + list(perm)
        cnt += all([nb[p[i-1]][p[i]] for i in range(1, N)])
    return cnt

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

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

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

def print_set(s):
    for e in s:
        print(e + 1, end=" ")
    print()

checker = N*(N - 1)//2
cnt = 0
def dfs(visited: set, stack: list):
    global cnt
    if sum(list(visited)) == checker:
        cnt += 1
    elif len(stack) > 0:
        v = stack.pop()
        for i in range(N):
            if g[v][i] and not (i in visited):
                dfs(visited | set([i]), stack + [i])

dfs(set([0]), [0])
print(cnt)

Solution (Python):
def dfs(u, g, visited):
    
    if sum(visited) == len(visited):
        return 1

    res = 0
    for v in g[u]:
        if visited[v]:
            continue

        visited[v] = True
        
        res += dfs(v, g, visited)
        visited[v] = False

    return res


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

    import collections
    g = collections.defaultdict(list)

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

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

    ans = dfs(0, g, visited)
    return ans


def main():
    print(solve())


if __name__ == '__main__':
    main()

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

Solution (Python):
N,M = map(int,input().split())
T = {}
for i in range(M):
    a,b = map(int,input().split())
    if a not in T.keys():
        T[a] = []
    if b not in T.keys():
        T[b] = []
    T[a].append(b)
    T[b].append(a)

ans = 0
def dfs(graph,start,path):
    global ans
    global N
    path = path + [start]

    if len(path) == N:
        ans += 1

    for node in graph[start]:
        if node not in path:
            new = dfs(graph,node,path)

    return ans


print(dfs(T,1,[]))

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

def res(a, i, E, visit):
    global cnt
    if i == N:
        cnt += 1
        return None
    if E[a]:
        for b in E[a]:
            if b in visit:
                pass
            else:
                res(b, i+1, E, visit + [a])
        return None
    else:
        return None

cnt = 0
res(1, 1, E, [])
print(cnt)

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

n,m=map(int,input().split())
d=dd(list)
for _ in range(m):
    a,b=map(int,input().split())
    d[a].append(b)
    d[b].append(a)
d=dict(d)
ans=0

for i in p(range(2,n+1)):
    pos=1
    for j in i:
        if not j in d[pos]:
            break
        pos=j
    else:
        ans+=1

print(ans)

Solution (Python):
def multival(): return map(int,input().split())
def data(N=1): return [list(map(int,input().split())) for _ in range(N)]
mod = 10**9 + 7
inf = float("inf")

N,M = multival()
nemat = [[0]*N for _ in range(N)]
ans = 0
for _ in range(M):
    a,b = multival()
    a -= 1; b-= 1
    nemat[a][b] = 1
    nemat[b][a] = 1

def dfs(now=0,visited=[False]*N):
    visited[now] = True
    if all(visited) is True:
        global ans
        ans += 1
    for ne in range(N):
        if nemat[now][ne] == 1 and visited[ne] is False:
            dfs(ne,visited[:])
            
            
            
            

dfs()
print(ans)

Solution (Python):
def multival(): return map(int,input().split())
def data(N=1): return [list(map(int,input().split())) for _ in range(N)]
mod = 10**9 + 7
inf = float("inf")

N,M = multival()
nemat = [[0]*N for _ in range(N)]
ans = 0
for _ in range(M):
    a,b = multival()
    a -= 1; b-= 1
    nemat[a][b] = 1
    nemat[b][a] = 1

def dfs(now=0,visited=[False]*N):
    visited[now] = True
    if all(visited) is True:
        global ans
        ans += 1
    for ne in range(N):
        if nemat[now][ne] == 1 and visited[ne] is False:
            dfs(ne,visited[:])

dfs()
print(ans)

Solution (Python):
from collections import deque

n, m = list(map(int, input().split()))
li = []
for _ in range(m):
    li.append(list(map(int, input().split())))


edges = [[] for _ in range(n)]
for i, j in li:
    edges[i - 1].append(j - 1)
    edges[j - 1].append(i - 1)

ans = 0
S = deque()
S.append([0])
while len(S) > 0:
    path = S.pop()
    for v in edges[path[-1]]:
        if v not in path:
            if len(path) + 1 == n:
                ans += 1
            else:
                S.append(path + [v])


print(ans)

Solution (Python):


from itertools import permutations

class Graph:
    def __init__(self, n_nodes):
        self.adj = [set() for i in range(n_nodes)]

    def add_edge(self, a1, b1):
        self.adj[a1 - 1].add(b1)
        self.adj[b1 - 1].add(a1)

    def are_adj(self, a1, b1):
        return b1 in self.adj[a1 - 1]

def main():
    n, m = map(int, input().split())
    gr = Graph(n)
    for i in range(m):
        a, b = map(int, input().split())
        gr.add_edge(a, b)
    paths = all_permutations_from_one(n)
    cnt = 0
    for p in paths:
        if is_possible(p, gr):
            cnt += 1
    print(cnt)

def all_permutations_from_one(n):
    perms_2_n = list(permutations(range(2, n + 1)))
    perms_1_n = [(1,) + p2n for p2n in perms_2_n]
    return perms_1_n

def is_possible(path, gr):
    l = len(path)
    flag = True
    for i in range(l - 1):
        a, b = path[i:i + 2]
        if not gr.are_adj(a, b):
            flag = False
    return flag

main()

Solution (Python):


import sys
from collections import defaultdict

INF = float('inf')
MOD = 10 ** 9 + 7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()


n, m = LI()
graph = defaultdict(list)
for _ in range(m):
    a, b = LI_()
    graph[a].append(b)
    graph[b].append(a)


def DFS(v: int, visited: list) -> int:
    
    ans = 0
    visited[v] = 1
    if all(visited):
        return 1

    for next in graph[v]:
        if visited[next]:
            continue

        ans += DFS(next, visited[:])

    return ans


print(DFS(0, [0] * n))

Solution (Python):
import sys
sys.setrecursionlimit(10**9)
N,M = map(int,input().split())
note = [[0]*N for i in range(N)]
visited = [False]*N
visited[0] = True
ans = 0
for i in range(M):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    note[a][b] = 1
    note[b][a] = 1

def dfs(p=0, depth=0):
    if depth == N-1:
        global ans
        ans += 1
        return
    for i in range(N):
        if note[p][i] == 1 and visited[i] is False:
            visited[i] = True
            dfs(i,depth+1)
            visited[i] = False

dfs()
print(ans)

Solution (Python):
def bit_dp(N, Adj):
    dp = [[0]*N for i in range(1 << N)]
    

    dp[1][0] = 1

    for S in range(1 << N):
        for v in range(N):
            
            if (S & (1 << v)) == 0:
                continue

            
            sub = S ^ (1 << v)

            for u in range(N):
                
                if (sub & (1 << u)) and (Adj[u][v]):
                    dp[S][v] += dp[sub][u]
    ans = sum(dp[(1 << N) - 1][u] for u in range(1, N))
    return ans


def main():
    N, M = map(int, input().split())
    Adj = [[False]*N for _ in range(N)]

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

    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
from itertools import permutations
N, M = list(map(int, input().split()))
edges = []

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

mat = [[0]*N for _ in range(N)]

for s, g in edges:
    mat[s][g] = 1
    mat[g][s] = 1


P = permutations(range(N))
ans = 0
for route in P:
    if route[0] != 0:
        continue
    else:
        vis = 0
        for s, g in zip(route, route[1:]):
            if mat[s][g] == 1:
                vis += 1
                if vis == N-1:
                    ans += 1
                continue
            else:
                break
print(ans)

Solution (Python):
def rs(X, Y, i):
  if i not in Y:
    return 0
  elif len(Y)==1:
    return 1
  Y.remove(i)
  
  total=0
  X_tmp=[x for x in X if i in x]
  for x in X_tmp:
    st=set(x)&set(Y)
    if st!=set():
      target=list(st)[0]
    else:
      continue
    total+=rs(X, Y[:], target)
    
  return total
  

N,M=map(int, input().split())
X=[list(map(int,input().split())) for _ in range(M)]
Y=[i+1 for i in range(N)]
print(rs(X, Y, 1))

Solution (Python):
def rs(X, Y, i):
  if i not in Y:
    return 0
  elif len(Y)==1:
    return 1
  Y.remove(i)
  
  total=0
  X_tmp=[x for x in X if x[0]==i or x[1]==i]
  for x in X_tmp:
    if x[0]==i and x[1] in Y:
      target=x[1]
    elif x[1]==i and x[0] in Y:
      target=x[0]
    else:
      continue
    total+=rs(X, Y[:], target)
    
  return total
  

N,M=map(int, input().split())
X=[list(map(int,input().split())) for _ in range(M)]
Y=[i+1 for i in range(N)]
print(rs(X, Y, 1))

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

ans = 0
node = 0
remain.remove(0)

def find_next_node(remain_arr, current_node):
    global ans
    if remain_arr == []:
        ans += 1
        return
    for next_node in connected[current_node]:
        if next_node in remain_arr:
            find_next_node([i for i in remain_arr if i != next_node], next_node)

find_next_node(remain, 0) 
print(ans)

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

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

def conn(v1,v2):
    return (v1,v2) in edges

import itertools
ret=0
for x in itertools.permutations(list(range(1,n+1))):
    for i in range(n-1):
        if not conn(x[i],x[i+1]) or x[0]!=1:
            break
        if i==n-2:
            ret+=1

print(ret)

Solution (Python):

def getInt(): return int(input())
def getIntList(): return [int(x) for x in input().split()]
def zeros(n): return [0 for i in range(n)]
def zeros2(n, m): return [[0 for i in range(m)] for j in range(n)]

debug = True
def db(x): 
    if debug: print(x)

debug = False
N,m = getIntList()
org = zeros(m)

for i in range(m):    org[i] = getIntList()

db(('org graph',org))
Count = 0

def find(graph, fromNode, route): 
    global Count
    db(('find in',fromNode, route))
    if fromNode in route: return -1
    else:
        route = route + [fromNode]  
        if len(route)==N: 
            db(('N',N))
            Count += 1
            return 0
        for edge in graph:
            if edge[0]==fromNode:  
                val = find(graph, edge[1], route)
                
                
                
        
        return -1
    
graph = zeros(m*2)
for i in range(m):
    graph[i*2] = org[i]
    graph[i*2+1] = [org[i][1], org[i][0]]
graph.sort()
db(('new graph',graph))
route = []
find(graph, 1, route)
print(Count)

Solution (Python):
n,m=map(int,input().split())
s=[[]for i in range(n)]
for i in range(m):
    a,b=map(int,input().split())
    s[a-1].append(b-1)
    s[b-1].append(a-1)
c=0
k=[]
p=[[0]]
for i in range(m):
    k=[]
    for j in range(len(p[:])):
        for h in range(len(s[p[j][-1]])):
            t=s[p[j][-1]]
            if not t[h] in p[j]:
                k.append(p[j]+[t[h]])
                if len(k[-1])==n:
                    c+=1
                    k.pop(-1)
    else:
        p=k[:]
print(c)

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

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


def f(curpath, N):
    if len(curpath) == N:
        
        return 1
    ret = 0
    now = curpath[-1]

    for e in edges:
        if now == e[0] and e[1] not in curpath:
            temp = curpath[:]
            temp.append(e[1])
            ret += f(temp, N)
    return ret


print(f([1], N))

Solution (Python):
from itertools import permutations

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

Matrix = [[False for x in range(N)] for y in range(N)]
for i in range(N) :
    Matrix[i][i] = True
for i in range(M) :
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    Matrix[a][b] = True
    Matrix[b][a] = True

arange = permutations(range(1,N))
ans = 0
for i in arange :
    pm = [0] + list(i)
    for a,b in zip(pm, pm[1:]) :
        if not Matrix[a][b] :
            break
    else :
        ans += 1
print(ans)

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

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

cnt = 0

for each in itertools.permutations(range(n)):
  if each[0] != 0:
     break
  factor = 1
  for i in range(n-1):
    factor *= matrix[each[i]][each[i+1]]
  cnt += factor
print(cnt)

Solution (Python):
import itertools

N, M = map(int, input().split(" "))
path = [[False for j in range(N)] for i in range(N)]

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

count = 0
for order in itertools.permutations(range(1, N)):
    before = 0
    for nextNode in order:
        if not path[before][nextNode]:
            break
        before = nextNode
    if before == order[-1]:
        count += 1
print(count)

Solution (Python):
def dfs(i):
    if all(visited):
        global ans
        ans += 1
        return
    for j in range(N):
        if g[i][j] and not visited[j]:
            visited[j] = True
            dfs(j)
            visited[j] = False

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

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

Solution (Python):
def bit_dp(N, Adj):
    dp = [[0]*N for i in range(1 << N)]
    
    dp[1][0] = 1

    for S in range(1 << N):
        for v in range(N):
            
            if (S & (1 << v)) == 0:
                continue

            
            sub = S ^ (1 << v)

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

    ans = sum(dp[(1 << N) - 1][u] for u in range(1, N))
    return ans


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

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

    ans = bit_dp(N, Adj)

    print(ans)


if __name__ == '__main__':
    main()