Поїздка на автомобілі#520

Поїздка на автомобілі

... Через нові регуляції водії повинні мати акумулятори ...

У вас є з'єднаний зважений неорієнтований граф з вершинами та ребрами. У вас також є автомобіль з паливним баком, який вміщує не більше літрів.

Коли ви перебуваєте на вершині, ви можете за бажанням заправитися, що заповнює бак рівно на літрів. Щоб пройти ребро з вагою , ви повинні мати принаймні літрів пального в баку; це коштує рівно літрів.

Вам дано запитів. Для кожного запиту : яка мінімальна кількість заправок потрібна, щоб проїхати від до , починаючи з повним баком? Якщо це неможливо, виведіть -1.

Вхідні дані

Перший рядок містить три цілі числа , та (3 \le n \le 2 \cdot 10^5, 1 \le q \le 2 \cdot 10^5, 1 \le V \le 10^9) — кількість вершин, кількість запитів та ємність паливного бака.

Наступні рядків містять по три цілі числа 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) — ребро між u_i та v_i з вагою c_i.

Гарантується, що граф з'єднаний і не містить петель.

Наступні рядків містять по два цілі числа s_i та t_i (1 \le s_i, t_i \le n, s_i \neq t_i) — -й запит.

Вихідні дані

Виведіть рядків. -й рядок повинен містити одне ціле число — мінімальна кількість заправок для -го запиту, або , якщо це неможливо.

Приклади

Приклад 1

Loading
Loading

Примітка

Граф має вершин, ребер, а ємність паливного бака V = 4.

  1. Запит 6 \to 7: подорож 6 \to 4 \to 3 \to 5 (використовуючи 1 + 2 + 1 = 4 літри, бак порожній), заправка на вершині , потім 5 \to 7 (використовуючи літри). Мінімальна кількість заправок: .

  2. Запит 7 \to 6: подорож 7 \to 5 (використовуючи літри, бак порожній), заправка на вершині , потім 5 \to 3 \to 4 \to 6 (використовуючи 1 + 2 + 1 = 4 літри). Мінімальна кількість заправок: .

  3. Запит 3 \to 2: подорож безпосередньо 3 \to 2, використовуючи ребро з вагою  (бак переходить з до ). Заправка не потрібна. Мінімальна кількість заправок: .

Оцінювання

  1. ( бали) n \le 3, q \le 10;

  2. ( балів) n \le 300, q \le 300;

  3. ( балів) n \le 5000, q \le 5000;

  4. ( бали) V = 1, існує лише один шлях від s_i до t_i;

  5. ( балів) V = 1;

  6. ( балів) існує лише один шлях від s_i до t_i;

  7. ( балів) n \le 10^5, q \le 10^5;

  8. ( бали) без додаткових обмежень.