... En raison de nouvelles réglementations, les conducteurs doivent avoir des batteries ...
Vous avez un graphe non dirigé, pondéré et connecté avec sommets et arêtes. Vous avez également une voiture avec un réservoir de carburant qui contient au maximum litres.
Lorsque vous êtes à un sommet, vous pouvez optionnellement faire le plein, ce qui remplit le réservoir exactement à litres. Pour traverser une arête de poids , vous devez avoir au moins litres de carburant dans le réservoir ; cela coûte exactement litres.
Vous recevez requêtes. Pour chaque requête : quel est le nombre minimum de pleins nécessaires pour voyager de à , en commençant avec un réservoir plein ? Si c'est impossible, imprimez -1.
La première ligne contient trois entiers , , et (3 \le n \le 2 \cdot 10^5, 1 \le q \le 2 \cdot 10^5, 1 \le V \le 10^9) — le nombre de sommets, le nombre de requêtes, et la capacité du réservoir de carburant.
Les lignes suivantes contiennent chacune trois entiers 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) — une arête entre u_i et v_i avec un poids c_i.
Il est garanti que le graphe est connecté et ne contient pas de boucles.
Les lignes suivantes contiennent chacune deux entiers s_i et t_i (1 \le s_i, t_i \le n, s_i \neq t_i) — la -ème requête.
Imprimez lignes. La -ème ligne doit contenir un seul entier — le nombre minimum de pleins pour la -ème requête, ou si c'est impossible.
Example 1
Le graphe a sommets, arêtes, et la capacité du réservoir de carburant est V = 4.
Requête 6 \to 7: voyage 6 \to 4 \to 3 \to 5 (utilisant 1 + 2 + 1 = 4 litres, réservoir vide), faire le plein au sommet , puis 5 \to 7 (utilisant litres). Pleins minimums : .
Requête 7 \to 6: voyage 7 \to 5 (utilisant litres, réservoir vide), faire le plein au sommet , puis 5 \to 3 \to 4 \to 6 (utilisant 1 + 2 + 1 = 4 litres). Pleins minimums : .
Requête 3 \to 2: voyage directement 3 \to 2 en utilisant l'arête de poids (le réservoir passe de à ). Aucun plein nécessaire. Pleins minimums : .
( points) n \le 3, q \le 10;
( points) n \le 300, q \le 300;
( points) n \le 5000, q \le 5000;
( points) V = 1, il existe un seul chemin de s_i à t_i;
( points) V = 1;
( points) il existe un seul chemin de s_i à t_i;
( points) n \le 10^5, q \le 10^5;
( points) pas de restrictions supplémentaires.