static int findShortest(int graphNodes, int[] graphFrom, int[] graphTo, long[] ids, int val) {
        // solve here
        Dictionary<int, List<int>> graph = new Dictionary<int, List<int>>();
        for(int i = 0; i < graphFrom.Length; i++)
        {
            int from = graphFrom[i];
            int to = graphTo[i];
            if(!graph.ContainsKey(from)) graph[from] = new();
            if(!graph.ContainsKey(to)) graph[to] = new();
            graph[from].Add(to);
            graph[to].Add(from);
        }
        Dictionary<long, List<int>> colorMap = new Dictionary<long, List<int>>();
        for(int i = 1; i <= graphNodes; i++)
        {
            long color = ids[i-1];
            if(!colorMap.ContainsKey(color)) colorMap[color] = new();
            colorMap[color].Add(i);
        }
        if(!colorMap.ContainsKey(val)) return -1;
        var colorIds = colorMap[val].ToHashSet();
        if(colorIds.Count() <= 1) return -1;
        HashSet<int> seen = new HashSet<int>();
        int shortPath = graphNodes * 2;
        foreach(var id in colorIds)
        {
            if(seen.Contains(id)) continue;
            seen.Add(id);
            bool isFind = false;
            Queue<(int, int)> q = new Queue<(int, int)>();
            q.Enqueue((id, 0));
            while(q.Count() > 0)
            {
                var (front, pathCount) = q.Dequeue();
                if(!graph.ContainsKey(front)) continue;
                var nearNodes = graph[front];
                foreach(var entry in nearNodes)
                {
                    if(seen.Contains(entry)) continue;
                    seen.Add(entry);
                    q.Enqueue((entry, pathCount+1));
                    if(colorIds.Contains(entry))
                    {
                        shortPath = Math.Min(shortPath, pathCount+1);
                    }
                }
            }
        }
        
        if(shortPath == graphNodes*2) return -1;
        return shortPath;
    }

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