... Z powodu nowych przepisów kierowcy są zobowiązani do posiadania akumulatorów ...
Dany jest spójny, ważony, nieskierowany graf z wierzchołkami i krawędziami. Masz również samochód z bakiem paliwa, który pomieści maksymalnie litrów i którym jeździsz po grafie.
Kiedy jesteś w wierzchołku, możesz zatankować, co napełnia bak z powrotem do dokładnie litrów. Aby przejechać krawędź o wadze , musisz mieć co najmniej litrów paliwa w baku i kosztuje to dokładnie litrów.
Danych jest zapytań. Dla każdego zapytania : jaka jest minimalna liczba tankowań potrzebna do podróży z do , zaczynając z pełnym bakiem? Jeśli podróż jest niemożliwa, wypisz -1.
Pierwsza linia zawiera trzy liczby całkowite , i (3 \le n \le 2 \cdot 10^5, 1 \le q \le 2 \cdot 10^5, 1 \le V \le 10^9) — liczba wierzchołków, liczba zapytań i pojemność baku paliwa.
Następne linii zawierają po trzy liczby całkowite 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), opisujące krawędź między u_i a v_i o wadze c_i. Gwarantuje się, że graf jest spójny i nie zawiera pętli.
Następne linii zawierają po dwie liczby całkowite s_i i t_i (1 \le s_i, t_i \le n, s_i \neq t_i) — -te zapytanie.
Wypisz linii. -ta linia powinna zawierać jedną liczbę całkowitą — minimalną liczbę tankowań dla -tego zapytania, lub , jeśli podróż jest niemożliwa.
Przykład 1
Graf ma wierzchołków, krawędzi, a pojemność baku paliwa wynosi V = 4.
Zapytanie 6 \to 7: podróż 6 \to 4 \to 3 \to 5 (zużywając 1 + 2 + 1 = 4 litry, bak pusty), tankowanie na wierzchołku , następnie 5 \to 7 (zużywając litry). Minimalna liczba tankowań: .
Zapytanie 7 \to 6: podróż 7 \to 5 (zużywając litry, bak pusty), tankowanie na wierzchołku , następnie 5 \to 3 \to 4 \to 6 (zużywając 1 + 2 + 1 = 4 litry). Minimalna liczba tankowań: .
Zapytanie 3 \to 2: podróż bezpośrednia 3 \to 2 używając krawędzi o wadze (bak przechodzi z do ). Nie potrzeba tankowania. Minimalna liczba tankowań: .
( punkty) n \le 3, q \le 10;
( punkty) n \le 300, q \le 300;
( punkty) n \le 5000, q \le 5000;
( punkty) V = 1, istnieje tylko jedna ścieżka z s_i do t_i;
( punkty) V = 1;
( punkty) istnieje tylko jedna ścieżka z s_i do t_i;
( punkty) n \le 10^5, q \le 10^5;
( punkty) brak dodatkowych ograniczeń.