Jazda samochodem#520

Jazda samochodem

... 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.

Dane wejściowe

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.

Dane wyjściowe

Wypisz linii. -ta linia powinna zawierać jedną liczbę całkowitą — minimalną liczbę tankowań dla -tego zapytania, lub , jeśli podróż jest niemożliwa.

Przykłady

Przykład 1

Loading
Loading

Uwaga

Graf ma wierzchołków, krawędzi, a pojemność baku paliwa wynosi V = 4.

  1. 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ń: .

  2. 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ń: .

  3. 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ń: .

Punktacja

  1. ( punkty) n \le 3, q \le 10;

  2. ( punkty) n \le 300, q \le 300;

  3. ( punkty) n \le 5000, q \le 5000;

  4. ( punkty) V = 1, istnieje tylko jedna ścieżka z s_i do t_i;

  5. ( punkty) V = 1;

  6. ( punkty) istnieje tylko jedna ścieżka z s_i do t_i;

  7. ( punkty) n \le 10^5, q \le 10^5;

  8. ( punkty) brak dodatkowych ograniczeń.