... Через нові регуляції водії повинні мати акумулятори ...
У вас є з'єднаний зважений неорієнтований граф з вершинами та ребрами. У вас також є автомобіль з паливним баком, який вміщує не більше літрів.
Коли ви перебуваєте на вершині, ви можете за бажанням заправитися, що заповнює бак рівно на літрів. Щоб пройти ребро з вагою , ви повинні мати принаймні літрів пального в баку; це коштує рівно літрів.
Вам дано запитів. Для кожного запиту : яка мінімальна кількість заправок потрібна, щоб проїхати від до , починаючи з повним баком? Якщо це неможливо, виведіть -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
Граф має вершин, ребер, а ємність паливного бака V = 4.
Запит 6 \to 7: подорож 6 \to 4 \to 3 \to 5 (використовуючи 1 + 2 + 1 = 4 літри, бак порожній), заправка на вершині , потім 5 \to 7 (використовуючи літри). Мінімальна кількість заправок: .
Запит 7 \to 6: подорож 7 \to 5 (використовуючи літри, бак порожній), заправка на вершині , потім 5 \to 3 \to 4 \to 6 (використовуючи 1 + 2 + 1 = 4 літри). Мінімальна кількість заправок: .
Запит 3 \to 2: подорож безпосередньо 3 \to 2, використовуючи ребро з вагою (бак переходить з до ). Заправка не потрібна. Мінімальна кількість заправок: .
( бали) n \le 3, q \le 10;
( балів) n \le 300, q \le 300;
( балів) n \le 5000, q \le 5000;
( бали) V = 1, існує лише один шлях від s_i до t_i;
( балів) V = 1;
( балів) існує лише один шлях від s_i до t_i;
( балів) n \le 10^5, q \le 10^5;
( бали) без додаткових обмежень.