... Due to new regulations, drivers are required to have batteries ...
You have a connected weighted undirected graph with vertices and edges. You also have a car with a fuel tank that holds at most liters.
When you are at a vertex, you may optionally refuel, which fills the tank back to exactly liters. To traverse an edge of weight , you must have at least liters of fuel in the tank; doing so costs exactly liters.
You are given queries. For each query : what is the minimum number of refuels needed to travel from to , starting with a full tank? If it is impossible, print -1.
The first line contains three integers , , and (3 \le n \le 2 \cdot 10^5, 1 \le q \le 2 \cdot 10^5, 1 \le V \le 10^9) — the number of vertices, the number of queries, and the fuel tank capacity.
The following lines each contain three integers u_i, v_i, c_i (1 \le u_i, v_i \le n, u_i \neq v_i, 1 \le c_i \le 10^9) — an edge between u_i and v_i with weight c_i.
It is guaranteed that the graph is connected and contains no self-loops.
The following lines each contain two integers s_i and t_i (1 \le s_i, t_i \le n, s_i \neq t_i) — the -th query.
Print lines. The -th line should contain a single integer — the minimum number of refuels for the -th query, or if it is impossible.
Example 1
The graph has vertices, edges, and the fuel tank capacity is V = 4.
Query 6 \to 7: travel 6 \to 4 \to 3 \to 5 (using 1 + 2 + 1 = 4 liters, tank empty), refuel at vertex , then 5 \to 7 (using liters). Minimum refuels: .
Query 7 \to 6: travel 7 \to 5 (using liters, tank empty), refuel at vertex , then 5 \to 3 \to 4 \to 6 (using 1 + 2 + 1 = 4 liters). Minimum refuels: .
Query 3 \to 2: travel directly 3 \to 2 using the edge of weight (tank goes from to ). No refuel needed. Minimum refuels: .
( points) n \le 3, q \le 10;
( points) n \le 300, q \le 300;
( points) n \le 5000, q \le 5000;
( points) V = 1, there exists only one path from s_i to t_i;
( points) V = 1;
( points) there exists only one path from s_i to t_i;
( points) n \le 10^5, q \le 10^5;
( points) no additional restrictions.