class Node:
    def __init__(self, id, color):
        self.id = id
        self.connections = []
        self.color = color
    def connect(self, nodeid):
        self.connections.append(nodeid)
          
def findShortest(graph_nodes, graph_from, graph_to, ids, val):
    nodes = {}
    for f, t in zip(graph_from, graph_to):
        color_f = ids[f-1]
        color_t = ids[t-1]
        
        node_from = nodes.get(f, Node(f, color_f))
        node_to = nodes.get(t, Node(t, color_t))
    
        node_from.connect(t)
        node_to.connect(f)
        
        nodes[f] = node_from
        nodes[t] = node_to
        
    nodes_to_check = [n+1 for n, i in enumerate(ids) if i == val]
    dists = []
    
    if len(nodes_to_check) <= 1:
        return -1
    
    for nc in nodes_to_check:
        dist = find_closest_connection(nodes, nc, val, [nc], 0)
        dists.append(dist)
        
    return min(dists)

def find_closest_connection(nodes, start_node, color, searched = [], distance = 0):
    node = nodes[start_node]
    distance += 1
    
    for nc in node.connections:
        if nc in searched:
            continue
            
        searched.append(nc)
        if nodes[nc].color == color:
            return distance
            
        else:
            distance = find_closest_connection(nodes, nc, color, searched, distance)
    
    return distance