Problem Statement:

In a disaster-stricken city, a network of emergency hubs is tasked with dispatching rescue teams to incident locations across a massive road network. The city is represented as a directed graph with sectors as nodes and one-way roads as edges.

Given millions of roads and sectors, your task is to compute the shortest number of roads (i.e., path length) needed for each hub to reach its respective incident location.

Important: The input size is so large that you must use an Adjacency List to avoid memory issues. Brute-force or Adjacency Matrix solutions will exceed limits. This is an intentional challenge and must be discovered and handled properly.

Input:

• All inputs are provided in a single line, space-separated.
• n: Number of sectors (1 ≤ n ≤ 10⁶)
• m: Number of one-way roads (1 ≤ m ≤ 10⁷)
• u1 v1 u2 v2 ... um vm: m pairs of roads (from ui to vi)
• q: Number of incident reports (1 ≤ q ≤ 10⁴)
• h1 t1 h2 t2 ... hq tq: q queries, each asking the shortest path from hub hi to incident ti

Output:

A single space-separated line of q integers. Each integer is the shortest number of roads from the hub to the incident location. If no path exists, return -1.

Constraints:

• 1 ≤ n ≤ 10⁶
• 1 ≤ m ≤ 10⁷
• 1 ≤ q ≤ 10⁴
• Use Adjacency List + BFS (not Dijkstra) since all roads are equal in weight.

Example 1:

input: 6 7 1 2 1 3 2 4 3 4 4 5 5 6 3 6 2 1 6 2 6
output: 3 3

Explanation:
1 → 3 → 4 → 5 → 6 takes 3 roads.
2 → 4 → 5 → 6 also takes 3 roads.
    

Example 2:

input: 4 2 1 2 3 4 2 1 4 3 2
output: -1 -1

Explanation:
No path from 1 to 4 or from 3 to 2 due to disconnected components.
    

Example 3:

input: 5 4 1 2 2 3 3 4 4 5 1 1 5
output: 4

Explanation:
Path is 1 → 2 → 3 → 4 → 5 (4 roads).
    

Example 4:

input: 5 6 1 2 1 3 2 4 3 4 4 5 3 5 2 1 5 3 5
output: 2 1

Explanation:
1 → 3 → 5 = 2 roads, and 3 → 5 = 1 road.