Minimum Roads Navigation Problem

You are given a network of n cities and m roads connecting these cities. In addition, there are b blockage events that block certain roads for a specific duration. Your task is to answer q queries. In each query, given a starting city, an ending city, and a specific time t, determine the minimum number of roads you must traverse to travel from the start to the end city at time t. If it is impossible to travel under the blockage constraints, output -1.

The road network is undirected. A road between two cities u and v is blocked at time t if there is a blockage event on that road with a duration d such that \( t \le d \). In such a case, that road cannot be used at time t.

Input Format: The first line of input contains two integers \( n \) and \( m \) separated by a space. The next \( m \) lines each contain two integers representing a road between two cities. This is followed by an integer \( b \), and then \( b \) lines each containing three integers \( x \), \( y \), and \( d \) indicating that the road between city \( x \) and city \( y \) is blocked for times \( \le d \). Finally, an integer \( q \) is given, followed by \( q \) lines where each line contains three integers: the start city, the end city, and the time \( t \) of the query.

Output Format: For each query, output a single line containing the minimum number of roads required to travel from the start city to the end city at time \( t \), or -1 if it is not possible.

inputFormat

The input is given via standard input (stdin) and is structured as follows:

n m
u1 v1
u2 v2
... (m lines for roads)
b
x1 y1 d1
x2 y2 d2
... (b lines for blockages)
q
s1 e1 t1
s2 e2 t2
... (q lines for queries)

</p>

Where:

• n is the number of cities (cities are numbered from 1 to n).
• m is the number of roads.
• Each road is represented by two integers \( u \) and \( v \), meaning there is an undirected road connecting cities \( u \) and \( v \).
• b is the number of blockage events.
• Each blockage event is represented by three integers \( x \), \( y \), and \( d \), indicating that the road between \( x \) and \( y \) is blocked for any time \( t \le d \).
• q is the number of queries.
• Each query consists of three integers: the starting city, the ending city, and the time \( t \) at which the route is evaluated.

outputFormat

For each query, output a single line containing an integer representing the minimum number of roads needed to travel from the start to the end city at the specified time, or -1 if the journey is not possible under the given conditions.

## sample

6 7
1 2
2 3
3 4
4 5
5 6
6 1
2 5
2
2 3 3
4 5 2
3
1 5 2
1 6 1
3 6 4

2
1
3

</p>