Minimum Hops between Servers

You are given a data center with N servers interconnected by M bidirectional links. Each link connects two distinct servers and has an associated bandwidth. Although the bandwidth is provided, your task is not to optimize bandwidth utilization but to compute the minimum number of hops (edges) required to travel from a source server to a destination server.

For each query consisting of a pair of servers \(s_i\) and \(t_i\), determine the least number of hops needed to travel from \(s_i\) to \(t_i\). If \(t_i\) is unreachable from \(s_i\), output \(-1\).

The problem constraints are as follows:

• \(2 \leq N \leq 300\)
• \(1 \leq M \leq \frac{N \cdot (N - 1)}{2}\)
• Each link is described by three integers \(A_i\), \(B_i\), and \(C_i\) where \(1 \leq A_i, B_i \leq N\), \(A_i \neq B_i\), and \(1 \leq C_i \leq 10^9\).
• \(1 \leq Q \leq N \cdot (N - 1)\) where Q is the number of queries.
• For each query, \(1 \leq s_i, t_i \leq N\) and \(s_i \neq t_i\).

Note: Even though the input constraints specify that \(s_i \neq t_i\), your implementation should handle the case when the source and destination are the same by returning 0 hops.

inputFormat

The input is read from stdin and has the following format:

N M
A1 B1 C1
A2 B2 C2
... (M lines)
Q
s1 t1
s2 t2
... (Q lines)

Here:

• N is the number of servers.
• M is the number of bidirectional links.
• Each of the next M lines contains three integers \(A_i\), \(B_i\), and \(C_i\). Note that \(C_i\) is provided but is not used in computing the minimum number of hops.
• Q is the number of queries.
• Each of the next Q lines contains two integers \(s_i\) and \(t_i\), representing the source and destination servers respectively.

outputFormat

For each query, output a single integer on a new line, representing the minimum number of hops required to travel from the source to the destination server. If the destination is unreachable, output \(-1\).

The output should be written to stdout.

## sample

4 3
1 2 100
2 3 200
3 4 150
2
1 4
1 3

3
2

</p>