artificial

# 1.DFS
graph={
    'A':['B','S'],
    'B':['A'],
    'C':['S'],
    'D':['S','F'],
    'E':['S'],
    'F':['D','G'],
    'G':['F'],
    'S':['A','C','D','E']
}
visited=[]
def dfs(graph,visited,node):
    if node not in visited:
        print(node,end=' ')
        visited.append(node)
        for neighbour in graph[node]:
            dfs(graph,visited,neighbour)
dfs(graph,visited,'A')

# 2.BFS
graph={
    'A':['B','S'],
    'B':['A'],
    'C':['S'],
    'D':['S','F'],
    'E':['S'],
    'F':['D','G'],
    'G':['F'],
    'S':['A','C','D','E']
}
visited=[]
queue=[]
def bfs(graph,visited,node):
    visited.append(node)
    queue.append(node)
    while queue:
        s=queue.pop(0)
        print(s,end=' ')
        for neighbour in graph[s]:
            if neighbour not in visited:
                visited.append(neighbour)
                queue.append(neighbour)
bfs(graph,visited,'A')

# 3.TOH
def TOH(n,from_rod,aux_rod,to_rod):
    if(n>0):
        TOH(n-1,from_rod,to_rod,aux_rod)
        print("Move disk ",n," from rod",from_rod," to rod ",to_rod)
        TOH(n-1,aux_rod,from_rod,to_rod)

n=int(input("Enter how many disk:"))
TOH(n,'A','B','C')

# 4.TSP
graph=[[0,16,11,6],
       [8,0,13,16],
       [4,7,0,9],
       [5,12,2,0]
       ]
n=4
visited=(1<<n)-1
def TSP(mask,pos):
    if(mask==visited):
        return graph[pos][0]
    ans=9999999999
    for city in range(n):
        if((mask&(1<<city))==0):
            newAns=graph[pos][city]+TSP(mask|(1<<city),city)
            ans=min(ans,newAns)
    return ans

print(TSP(1,0))