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

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

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


point = [i+1 for i in range(1,N)]
root = list(permutations(point, N-1))


counter = 0
for i in range(len(root)):
    pairs = []
    pairs.append([1, root[i][0]])
    
    for j in range(N-2):
        pairs.append([root[i][j], root[i][j+1]])
    
    status = True
    for k in range(len(pairs)):
        tester = sorted(pairs[k])
        
        if(not(tester in graph)):
            status = False
    
    if(status):
        counter += 1
print(counter)

'''
counter = 0
for i in range(len(root)):
    print('i:{},root[i]:{}'.format(i, root[i]))
    spot = 1
    for j in range(N-1):
        
        n = root[i][j]
        print('spot:{}, n:{}'.format(spot, n))
        if(spot < n):
            if([spot, n] in graph):
                spot = n
            else:
                continue
        elif(spot > n):
            if([n, spot] in graph):
                spot = n
            else:
                continue
        else:
            continue
'''

Solution (Python):
def bitDP():
    dp = [[0] * N for _ in range(1 << N)]
    dp[1][0] = 1
    for i in range(1 << N):
        for v in range(N):
            if  (i >> v) & 0:
                continue
            j = i ^ (1 << v)
            for u in range(N):
                if (j >> u) & 1 and v in E[u]:
                    dp[i][v] += dp[j][u]
    res = sum(dp[-1][u] for u in range(1, N))
    return res

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

print(bitDP())

Solution (Python):
from itertools import permutations

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

ans = 0
for p in permutations([i for i in range(1, N)]):
    i = 0
    for j in p:
        if j not in E[i]:
            break
        i = j
    else:
        ans += 1
print(ans)

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

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

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


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

print(dfs(0, 1))

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


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


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




def dfs(v, used):
    
    if not False in used:
        return 1

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

print(dfs(0, used))

Solution (Python):
N, M = map(int, input().split())
edge = [[] for _ in range(N)]
for i in range(M):
    a, b = map(int, input().split())
    edge[a-1].append(b-1)
    edge[b-1].append(a-1)
def dfs(start,route):
    route.append(start)
    if len(route) == N:
        route.remove(start)
        return 1
    res = 0
    for i in edge[start]:
        if i not in route:
            res += dfs(i,route)
    route.remove(start)
    return res
print(dfs(0,[]))

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 itertools
N,M=map(int,input().split())
ab=list(list(map(int,input().split())) for _ in range(M))
l=list(l for l in range(1,N+1))
numlist=list(itertools.permutations(l))
ans=0
for I in numlist:
    if I[0]==1 and all(sorted([I[j],I[j+1]]) in ab for j in range(N-1)):
        ans+=1
print(ans)

Solution (Python):
n,m=[int(i) for i in 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)}

p=[[0]]
x=0
while p:  
  p1=p.pop()
  if len(p1)==n:
    x+=1
  else:
    for l0,l1 in es:
      if l0==p1[len(p1)-1] and l1 not in p1:
          p.append(p1+[l1])

print(x)

Solution (Python):
import itertools
N,M=map(int,input().split())
path=[list(map(int,input().split())) for _ in range(M)]
seq=list(range(2,N+1))

l=list(itertools.permutations(seq))

buf=[]
cnt=0
for i in range(len(l)):
    buf=list(l[i])
    piv1=1
    
    for j in range(len(buf)):
        flag = 0
        piv2=buf[j]
        
        for k in range(M):
            mi=min(piv1,piv2)
            ma=max(piv1,piv2)
            if (path[k][0]==mi)and(path[k][1]==ma):
                flag=1
        
        if flag==0:
            break
        else:
            piv1=piv2
    if flag==1:
        cnt=cnt+1
print(cnt)

Solution (Python):
def resolve():
    N, M = list(map(int, input().split()))
    A = [list(map(int, input().split())) for i in range(M)]
    cnt = 0
    import itertools
    L = list(itertools.permutations(range(2, N+1)))
    for route in L:
        src = 1
        for point in route:
            dst = point
            if not ([src, dst] in A or [dst, src] in A):
                break
            src = dst
        else:
            cnt += 1
    print(cnt)

if '__main__' == __name__:
    resolve()

Solution (Python):

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


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

for _ in range(M):
    A, B = map(int, input().split())
    d[A - 1][B - 1] = True
    d[B - 1][A - 1] = True


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


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

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

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

    return ret

ans = dfs(0, N, visited)

print(ans)

Solution (Python):
import itertools

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

path_dict = {}
count = 0

for path in path_list:
    if path[0] in path_dict:
        path_dict[path[0]].append(path[1])
    else:
        path_dict[path[0]] = [path[1]]
    if path[1] in path_dict:
        path_dict[path[1]].append(path[0])
    else:
        path_dict[path[1]] = [path[0]]

order_list = list(range(2,n+1))
order_list = list(itertools.permutations(order_list))

for order in order_list:
    order = list(order)
    order.insert(0,1)
    for i,num in enumerate(order):
        if i >= 1:
            if num not in target_list:
                break
        if i == len(order)-1:
            count += 1
        target_list = path_dict[num]

print(count)

Solution (Python):
from itertools import permutations
N, M = list(map(int, input().split(' ')))
ADJ_MAT = [[0 for _ in range(N)] for _ in range(N)]
for _ in range(M):
    a, b = list(map(int, input().split(' ')))
    ADJ_MAT[a - 1][b - 1] = 1
    ADJ_MAT[b - 1][a - 1] = 1
answer = 0
for node_pattern in permutations(range(1, N)):
    
    node_pattern = [0] + list(node_pattern)
    exists_path = True
    for i in range(N - 1):
        node_from = node_pattern[i]
        node_to = node_pattern[i + 1]
        if ADJ_MAT[node_from][node_to] == 0:
            exists_path = False
            break
    if exists_path:
        answer += 1
print(answer)

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


is_checked = [False] * N

def dfs(i):
    cnt = 0
    is_checked[i] = True
    if not(False in is_checked):
        return 1
    else:
        for j in g[i]:
            if not(is_checked[j]):
                cnt += dfs(j)
                is_checked[j] = False
        return cnt
            
ans = dfs(0)
print(ans)

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


is_checked = [False] * N

import sys
sys.setrecursionlimit(10 ** 8)
def dfs(i):
    cnt = 0
    is_checked[i] = True
    if not(False in is_checked):
        return 1
    else:
        for j in g[i]:
            if not(is_checked[j]):
                cnt += dfs(j)
                is_checked[j] = False
        return cnt
            
ans = dfs(0)
print(ans)

Solution (Python):
import itertools
nums = [int(e) for e in input().split()]
pairs = []
count = 0
for i in range(nums[1]):
    s = [int(t) for t in input().split()]
    pairs.append(s)
lis = [i for i in range(1,nums[0]+1)]
permutatin_lis = itertools.permutations(lis)
for one in permutatin_lis:
    if(one[0] != 1):
        continue
    else:
        for i in range(nums[0]-1):
            checker = [one[i],one[i+1]]
            checker.sort()
            if checker in pairs:
                pass
            else:
                break
        else:
            count += 1
print(count)

Solution (Python):
import itertools

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

path = [[False]*N for i in range(N)]
ans = 0

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

for i in list(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):
N, M = map(int, input().split())
G = [list(map(int, input().split())) for _ in range(M)]
edges = [[] for _ in range(N)]
for a, b in G:
    edges[a - 1].append(b - 1)
    edges[b - 1].append(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):
import itertools

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


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


cnt = 0




for each in itertools.permutations(range(N)):

    
    if each[0]!=0:
        break

    factor=1
    for i in range(N-1):
        
        
        factor *= adj_mtrx[each[i]][each[i+1]]
    cnt += factor

print(cnt)

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

def solve(s,p):
  global res
  dp=format(s,'08b')[::-1]
  if s == (1<<n)-1 :
    res += 1
    return res
  for u in graph[p-1]:
    if dp[u-1] == '1':
      continue
    res = solve(s|(1<<(u-1)),u)
  return res

print(solve(1,1))

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

t=[i for i in range(N-1)]
premu=list(itertools.permutations(t))

cnt=0
for elem in premu:
    eb=1
    for e in elem:
        ec=e+2
        flag=False
        for ab in AB:
            if (ec in ab) and (eb in ab):
                flag=True    
        if flag:
            eb=ec
        else:
            break
    if flag:
        cnt+=1

print(cnt)

Solution (Python):
import itertools

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

lis = [i for i in range(1, N+1)]
T = itertools.permutations(lis)

ans = 0

for t in T:
    if t[0] == 1:
        for i in range(N-1):
            A = [list(t)[i], list(t)[i+1]]
            B = [list(t)[i+1], list(t)[i]]
            if not (A in L or B in L):
                break
        else:
            ans += 1
print(ans)

Solution (Python):
import itertools

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

ans = 0
for li in itertools.permutations(range(n), n):
    if li[0] == 0:
        for i in range(n-1):
            if not li[i + 1] in relation[li[i]]:
                break
        else:
            ans += 1

print(ans)

Solution (Python):
from itertools import permutations

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


counter = 0
for perm in permutations(range(2, N+1)):
    if lines[1][perm[0]]:
        if all(lines[perm[i]][perm[i+1]] for i in range(N-2)):
            counter += 1

print(counter)

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

from itertools import permutations
perm=permutations(range(1,n))
ans=0
for p in perm:
    newp=[0]+list(p)
    flg=True
    for i in range(n-1):
        if newp[i+1] not in es[newp[i]]:
            flg=False
            break
    if flg: ans+=1
print(ans)

Solution (Python):
import itertools

N, M = map(int, input().split())
c = [[False] * N for i in range(N)]
for i in range(M):
	a, b = map(int, input().split())
	c[a - 1][b - 1] = True
	c[b - 1][a - 1] = True
ans, d = 0, [i for i in range(N)]
for i in itertools.permutations(d[1:]):
	e, f = True, list(i)
	f.insert(0, d[0])
	for j in range(N - 1):
		if not c[f[j]][f[j + 1]]:
			e = False
			break
	if e:
		ans += 1
print(ans)

Solution (Python):
q=[]
qq=[]
def dfs(j,q,count,n,qq):
    if len(qq)==n:
        count+=1
        return count   
    for j2 in q[j]:
        if not j2 in qq:
            qq.append(j2)
            count=dfs(j2,q,count,n,qq)
            qq.pop()
    return count

n,m=map(int,input().split())
q=[[]*2 for i in range(n)]
for i in range(m):
    ai,bi=list(map(int,input().split()))
    if not q[bi-1] in q[ai-1]:
        q[ai-1].append(bi-1)    
        q[bi-1].append(ai-1)    

count=0
j=0
qq=[j]
count=dfs(j,q,count,n,qq)
print(count)

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

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

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

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

print(dfs(0, 1))

Solution (Python):
q=[]
qq=[]
def dfs(j,q,count,n,qq):
    if len(qq)==n:
        count+=1
        return count    
    for j2 in q[j]:
        if not j2 in qq:
            qq.append(j2)
            count=dfs(j2,q,count,n,qq)
            qq.pop()
    return count

n,m=map(int,input().split())
q=[[]*2 for i in range(n)]
for i in range(m):
    ai,bi=list(map(int,input().split()))
    if not q[bi-1] in q[ai-1]:
        q[ai-1].append(bi-1)    
    if not q[ai-1] in q[bi-1]:
        q[bi-1].append(ai-1)    

count=0
j=0
qq=[j]
count=dfs(j,q,count,n,qq)
print(count)

Solution (Python):
q=[]
qq=[]
def dfs(j,q,icnt,count,n,qq):
    if len(qq)==n:
        count+=1

        return count
    icnt+=1
    
    for j2 in q[j]:
        if not j2 in qq:
            qq.append(j2)

            count=dfs(j2,q,icnt,count,n,qq)
            qq.pop()

    return count

n,m=map(int,input().split())
ab=[[0]*2 for i in range(m)]
for i in range(m):
    ab[i]=list(map(int,input().split()))









q=[[]*2 for i in range(n)]
for i in range(m):
    if not q[ab[i][1]-1] in q[ab[i][0]-1]:
        q[ab[i][0]-1].append(ab[i][1]-1)    
    if not q[ab[i][0]-1] in q[ab[i][1]-1]:
        q[ab[i][1]-1].append(ab[i][0]-1)    


count=0
j=0
qq=[j]
icnt=1
count=dfs(j,q,icnt,count,n,qq)
print(count)

Solution (Python):
import sys
import heapq, math
from itertools import zip_longest, permutations, combinations, combinations_with_replacement
from itertools import accumulate, dropwhile, takewhile, groupby
from functools import lru_cache
from copy import deepcopy

N, M = map(int, input().split())
G = [[] for _ 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)


def search(idx, S):
    if S == (1 << N) - 1:
        return 1

    cnt = 0
    for n in G[idx]:
        if ((S >> n) & 1) == 1:
            continue

        cnt += search(n, S | (1 << n))

    return cnt

print(search(0, 1))

Solution (Python):
N, M = map(int, input().split())
adj_matrix = [[0]*N for _ in range(N)]

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

def dfs(v, used):
    if not False in used:
        return 1

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

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

Solution (Python):
def dfs(now, depth):
    if used[now]:
        return 0
    if depth == N:
        return 1

    used[now] = 1
    ans = 0

    for i in range(N):
        if connect[now][i]:
            ans += dfs(i, depth + 1)

    used[now] = 0
    return ans


def main():

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

    print(dfs(0, 1))


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

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

    used = [0 for i in range(N)]
    connect = [[0 for i in range(N)] for i in range(N)]
    main()

Solution (Python):
import itertools

n,m=map(int,input().split())
linelist=[list(map(int,input().split())) for i in range(m)]

numlist=[i for i in range(1,n+1)]

plist=list(itertools.permutations(numlist))

sum=0

for challenger in plist:
	if challenger[0] != 1:
		pass
	else:
		needlist=[]
		for i in range(n-1):
			tmp=[]
			tmp.extend([challenger[i],challenger[i+1]])
			tmp.sort()
			needlist.append(tmp)
		addflag=True
		for need in needlist:
			if not need in linelist:
				addflag = False
		
		if addflag:
			sum+=1

print(sum)

Solution (Python):
import itertools

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


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

cnt = 0

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

print(cnt)

Solution (Python):
import itertools

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

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

cnt = 0

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

print(cnt)

Solution (Python):
from itertools import permutations

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


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

T = []
for i in range(1, N):
    T.append(i)

ans = 0
for I in permutations(T):
    flag = True
    S = [0]
    S.extend(I)
    for j in range(N-1):
        if S[j+1] not in Hen[S[j]]:
            flag = False
            break
    if flag:
        ans += 1

print(ans)

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

li = set()
for i in range(m):
    a,b = map(int,input().split())
    li.add((a,b))
    li.add((b,a))


ans = 0

for v in permutations(range(1,n+1)):
    if v[0] != 1:
        continue
    flag = True
    for i in range(len(v)-1):
        if (v[i],v[i+1]) not in li:
            flag = False
            break
    if flag:
        ans +=1
print(ans)

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

def dfs(v, used):
    cnt = 0
    used[v] = 1
    if all(used):
        cnt+=1
    for nv in es[v]:
        if used[nv]:
            continue
        cnt += dfs(nv, used)
    used[v] = 0
    return cnt

used = [0] * N
cnt = dfs(0, used)
print(cnt)

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

def dfs(v, used, cnt):
    used[v] = 1
    if all(used):
        cnt[0]+=1
    for nv in es[v]:
        if used[nv]:
            continue
        dfs(nv, used, cnt)
    used[v] = 0

used = [0] * N
cnt = [0]
dfs(0, used, cnt)

print(cnt[0])

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

def dfs(v, used):
    global cnt
    used[v] = 1
    if all(used):
        cnt+=1
    for nv in es[v]:
        if used[nv]:
            continue
        dfs(nv, used)
    used[v] = 0


used = [0] * N
cnt = 0
dfs(0, used)
print(cnt)

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

def dfs(v, used, cnt):
    used[v] = 1
    if all(used):
        cnt.append(1)
    for nv in es[v]:
        if used[nv]:
            continue
        dfs(nv, used, cnt)
    used[v] = 0

used = [0] * N
cnt = []
dfs(0, used, cnt)

print(sum(cnt))

Solution (Python):
import itertools

n,m= map(int, input().split())
a= [list(map(int, input().split())) for i in range(m)]

ans=0
for v in itertools.combinations(a, n-1):
    b=[[] for i in range(n)]
    for x,y in v:
        b[x - 1].append(y - 1)
        b[y - 1].append(x - 1)

    import collections
    from collections import deque


    def tree(s):

        INF = -10 ** 9
        dis = [INF for i in range(n)]
        dis[s] = 0

        def bfs():
            d = deque()
            d.append(s)

            while len(d):
                x = d.popleft()

                for i in range(len(b[x])):
                    y = b[x][i]
                    if dis[y] == INF:
                        d.append(y)
                        dis[y] = dis[x] + 1

            return max(dis)

        return bfs()
    if tree(0)==n-1:
        ans+=1

print(ans)

Solution (Python):

import io
import math
import itertools as it

nim,mike = map(int, input().split())

arrat = []

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

per = it.permutations(range(2,nim+1),nim-1)

result = 0

for pe in per:
    Flag = True
    pe = list(pe)
    pe.insert(0,1)
    for i in range(len(pe)-1):
        if [pe[i],pe[i+1]] not in arrat and [pe[i+1],pe[i]] not in arrat:
            Flag = False
            break
    if Flag == True:
        result +=1

print(result)

Solution (Python):
import copy

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

V = []


def dfs(node, seen, V):

    if seen[node] is True:
        return 0

    seen[node] = True
    if not(False in seen):
        return 1

    ret = 0
    for next_node in V[node]:
        ret += dfs(next_node, copy.deepcopy(seen), V)
    return ret


for _ in range(N):
    V.append(set())

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

print(dfs(0, copy.deepcopy([False] * N), V))

Solution (Python):
import copy

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

V = []

def dfs(node, seen):

    if seen[node]==True:
        return 0

    seen[node] = True
    if not(False in seen):
        return 1
    ret = 0
    for next_node in V[node]:
        ret += dfs(next_node, copy.deepcopy(seen))
    return ret

for _ in range(N):
    V.append(set())

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

print(dfs(0, copy.deepcopy([False]*N)))

Solution (Python):

from itertools import permutations

def main():
    n, m = map(int, input().split())
    edge = set()
    for _ in range(m):
        a, b = map(int, input().split())
        edge.add((a-1, b-1))
        edge.add((b-1, a-1))
    
    node = []
    for i in range(n):
        node.append(i)
    cnt = 0
    for p in permutations(node):
        if p[0] == 0:
            f = True
            for j in range(n-1): 
                if (p[j], p[j+1]) not in edge:
                    f = False
            if f:
                cnt += 1 
    print(cnt)
main()

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

    edge = set()
    for _ in range(m):
        a, b = map(lambda x: int(x)-1, input().split())
        edge.add((a, b))  
        edge.add((b, a))

    
    
    

    
    node_num = []
    for i in range(n):
        node_num.append(i)
    
    cnt = 0
    for p in permutations(node_num):
        
        if p[0] == 0:
            
            flag = True
            for i in range(n-1):
                
                if (p[i], p[i+1]) not in edge:
                    flag = False
            if flag:
                cnt += 1 
    print(cnt) 
main()

Solution (Python):
from itertools import permutations

def int0(s):
    return int(s) - 1

def main():
    N, M = map(int, input().split())
    edges = [tuple(map(int0, input().split())) for _ in range(M)]

    to = [[False]*N for _ in range(N)]
    for a, b in edges:
        to[a][b] = True
        to[b][a] = True
    
    ans = 0
    for p in permutations(range(1, N)):
        if to[0][p[0]] and all(to[p[i]][p[i+1]] for i in range(N-2)):
            ans += 1
    print(ans)

if __name__ == "__main__":
    main()

Solution (Python):
n, m = [int(x) for x in input().split()] 
line = [ tuple( int(x)-1 for x in input().split() ) for _ in range(m) ]

matrix = [ [False]*n for _ in range(n) ] 
for a, b in line:
    matrix[a][b] = True
    matrix[b][a] = True

visited = [False]*n

def dfs(point, depth):
    if visited[point]:
        return 0

    if depth == n - 1:
        return 1

    visited[point] = True
    total = 0
    for i, np in enumerate(matrix[point]):
        if np:
            total += dfs(i, depth + 1)

    visited[point] = False
    return total

print(dfs(0, 0))

Solution (Python):
import itertools
n,m = map(int,input().split())
vert = [[0] for i in range(n+1)]
for i in range(m):
    a,b = map(int,input().split())
    vert[a].append(b)
    vert[b].append(a)
parents = [0]
now = 1
ans = 0
for i in list(itertools.permutations(range(1,n+1))):
    if i[0] == 1:
        for j in range(1,n):
            if i[j] not in vert[i[j-1]]:
                break
        else:
            ans += 1
print(ans)

Solution (Python):
def dfs(now,parents):
    global ans
    global n
    for i in vert[now]:
        if i not in parents:
            dfs(i,parents+[now])
    if len(parents) == n:
        ans += 1
n,m = map(int,input().split())
vert = [[0] for i in range(n+1)]
for i in range(m):
    a,b = map(int,input().split())
    vert[a].append(b)
    vert[b].append(a)
parents = [0]
now = 1
ans = 0
dfs(1,parents)
print(ans)

Solution (Python):
from collections import deque
N,M = map(int,input().split())
T = [[] for i in range(N+1)]
for i in range(M):
    a,b = map(int,input().split())
    T[a].append(b)
    T[b].append(a)
Q = deque([(1,[1])])
ans = 0
while Q:
    p,V = Q.pop()
    if len(V)==N:
        ans += 1
        continue
    for c in T[p]:
        if not(c in V):
            Q.append((c,V+[c]))
print(ans)

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

ans = 0
l = [i for i in range(1,n)]
for p in itertools.permutations(l):
  p = [0] + list(p)
  reach = 1
  for i in range(n-1):
    if not e[p[i]][p[i+1]]:
      reach = 0
      break
  ans += reach

print(ans)