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

static int findShortest(int graphNodes, int[] graphFrom, int[] graphTo, long[] ids, int val) {
    // Start by finding all nodes of the target color.
    List<Integer> targetNodes = new ArrayList<Integer>();
    for (int h = 0; h < ids.length; h++) {
        if (ids[h] == val) targetNodes.add(h);
    }
    for (int x : targetNodes) {
        System.out.println(x);
    }
    //Set up visited indicator and placeholder min. path lengths.
		boolean[] visited = new boolean[graphNodes];
    int[] pathLengths = new int[targetNodes.size()];
    for (int l = 0; l < pathLengths.length; l++) pathLengths[l] = -1;
    
    //Create the graph in the form of a list of neighbor node lists.
		List<List<Integer>> neighbors = new ArrayList<List<Integer>>();
    for (int i = 0; i < graphNodes; i++) neighbors.add(new ArrayList<Integer>());
    for (int j = 0; j < graphFrom.length; j++) {
        int nodeFrom = graphFrom[j]-1;
        int nodeTo = graphTo[j]-1;
        neighbors.get(nodeFrom).add(nodeTo);
        neighbors.get(nodeTo).add(nodeFrom);
    }
    
    //Reset the visited boolean array for each target node. Then use DFS to find the shortest path to the nearest node of the same color.
		for (int k = 0; k < targetNodes.size(); k++) {
        visited = new boolean[graphNodes];
        int node = targetNodes.get(k);
        //System.out.println("Node " + node);
        DFS(neighbors, visited, ids, val, 0, pathLengths, k, node);
    }
    
    //Lastly, find the shortest path if present by sorting the array and looking for the first non-negative number.
		Arrays.sort(pathLengths);
    for (int m = 0; m < pathLengths.length; m++) {
        //System.out.println(pathLengths[m]);
        if (pathLengths[m] > 0) return pathLengths[m];
    }
    
    return -1;
}

static void DFS(List<List<Integer>> neighbors, boolean[] visited, long[] ids, int val, int len, int[] pathLengths, int node, int curr) {
    //System.out.println("START: Node " + node);
    visited[curr] = true;
    List<Integer> nodeNeighbors = neighbors.get(curr);
    if (ids[curr] == val && len > 0) { //If the function isn't at the starting node and the current node is of the target color, update the path length for the starting node. If the starting node already has a path length assigned, pick the minimum of len and the previous path length.
        //System.out.println("MATCH: Node " + curr);
        if (pathLengths[node] == -1) {
            //System.out.println("ADD: Node " + node);
            pathLengths[node] = len;
        }
        else {
            //System.out.println("UPDATE: Node " + node);
            pathLengths[node] = Math.min(pathLengths[node], len);
        }
    }
		
		//Run the DFS function recursively with all neighbors that haven't been visited yet, adding 1 to the previous path length.
    for (int neighbor : nodeNeighbors) {
        if (!visited[neighbor]) {
        //System.out.println("Node " + curr + " (" + ids[curr] + "), Neighbor " + neighbor);
        DFS(neighbors, visited, ids, val, len+1, pathLengths, node, neighbor); }
    }
}

def findShortest(graph_nodes, graph_from, graph_to, ids, val):
    graph = defaultdict(set)
    for start, end in zip(graph_from, graph_to):
        graph[start].add(end)
        graph[end].add(start)
    
    min_path_len = math.inf
    for node, node_color in enumerate(ids, start=1):
        if node_color != val:
            continue
        visited = set([node])
        queue = deque(graph[node])
        curr_path_len = 0
        found_at = None
        while queue:
            curr = queue.popleft()
            if curr in visited:
                continue
            visited.add(curr)
            curr_path_len += 1
            curr_color = ids[curr-1]
            if curr_color == node_color:
                found_at = curr_path_len
                break
            queue.extend(graph[curr])
        if found_at:
            min_path_len = min(min_path_len, found_at)
    if min_path_len == math.inf:
        return -1
    return min_path_len

function findShortest(graphNodes, graphFrom, graphTo, ids, val) {
  let map = new Map()
  for (let i = 0; i < graphFrom.length; i++) {
    if (!map.has(graphFrom[i])) map.set(graphFrom[i], [])
    map.get(graphFrom[i]).push(graphTo[i])
    if (!map.has(graphTo[i])) map.set(graphTo[i], [])
    map.get(graphTo[i]).push(graphFrom[i])
  }

  let nodesToInvestigate = []
  for (let i = 1; i <= ids.length; i++) {
    if (ids[i - 1] == val) nodesToInvestigate.push(i)
  }

  if (nodesToInvestigate.length < 2) return -1

  let visited = new Set(), distances = []
  for (let i = 0; i < nodesToInvestigate.length; i++) {
    let queue = [[nodesToInvestigate[i], 0]]
    visited.add(nodesToInvestigate[i])
    while (queue.length > 0) {
      let [cur, steps] = queue.shift()
      visited.add(cur)
      if (ids[cur - 1] == val && cur != nodesToInvestigate[i]) {
        distances.push(steps)
        continue
      }
      queue.push(...map.get(cur).filter(to => !visited.has(to))
        .map(node => [node, steps + 1]))
    }
  }
  return Math.min(...distances)
}