## Enter Team ID 
import os 
os.environ["TEAMID"] = "Excalibur"

def get_min_swaps_line(N, controls, targets, connectivity_map):
    min_swaps = []
    ### You code goes here 
    length=len(controls)  
    for i in range(length):
        if(targets[i] in connectivity_map[controls[i]]):
            min_swaps.append(0)
        else:
            min_swaps.append(abs(targets[i]-controls[i])-1)
   
    
    ### your code goes here 
    
    return min_swaps

def test_function_1():
    controls = [1,1,1,1,2,2,2,2,3,3,3,3,4,4,4,4,5,5,5,5]
    targets = [2,3,4,5,1,3,4,5,1,2,4,5,1,2,3,5,1,2,3,4]
    connectivity_map = {
        1 : [2],
        2 : [1,3],
        3 : [2,4],
        4 : [3,5],
        5 : [4]
    }   
    N = 5  

    min_swaps = get_min_swaps_line(N, controls, targets, connectivity_map)
    
    return min_swaps

test_function_1()

from grader.graders.problem_2.grader import grader1
grader1.evaluate(get_min_swaps_line)

import sys
def get_min_swaps_graph(N, M, controls, targets, connectivity_map):
    min_swaps = []
    ### You code goes here
    length=len(controls)  
    for i in range(length):
        if(targets[i] in connectivity_map[controls[i]]):
            min_swaps.append(0)
        else:
            u=controls[i]
            v=targets[i]
            visited=[]
            distance=[]
            q=[]
            for i in range(N):
                visited.append(0)
                distance.append(sys.maxsize)
            for k in connectivity_map[u]:
                distance[k-1]=1
            distance[u-1]=0
            q.append(u)
            visited[u-1]=1
            while(q):
                x=q.pop(0)
                templist=connectivity_map[x]
                length2=len(templist)
                for j in range(length2):
                    if(visited[templist[j]-1]==1):
                        continue
                    if((distance[x-1]+1)<distance[templist[j]-1]):
                        distance[templist[j]-1]=distance[x-1]+1
                    q.append(templist[j])
                    visited[templist[j]-1]=1
            if(distance[v-1]==sys.maxsize):
                min_swaps.append(-1)
                continue
            min_swaps.append(distance[v-1]-1)        
    ### your code goes here 
    
    return min_swaps

def test_function_2():
    controls = [1, 2]
    targets = [2, 5]
    connectivity_map = {
        1 : [2],
        2 : [1,3],
        3 : [2,4,5],
        4 : [3],
        5 : [3]
    }   
    N = 5 
    M = 4
    min_swaps = get_min_swaps_graph(N, M, controls, targets, connectivity_map)
    
    return min_swaps

test_function_2()

from grader.graders.problem_2.grader import grader2
grader2.evaluate(get_min_swaps_graph)

