... Yeni tənzimləmələrə görə, sürücülərin batareyaları olmalıdır ...
Sizdə zirvəsi və kənarı olan bağlı ağırlıqlı yönsüz qraf var. Həmçinin, maksimum litr tutumlu bir yanacaq çəninə sahib bir avtomobiliniz var.
Bir zirvədə olduqda, siz istəyə görə yanacaq doldura bilərsiniz ki, bu da çəni tam olaraq litr ilə doldurur. Ağırlığı olan bir kənarı keçmək üçün çəninizdə ən azı litr yanacaq olmalıdır; bunu etmək tam olaraq litr başa gəlir.
Sizə sorğu verilib. Hər bir sorğu üçün: -dən -yə keçmək üçün lazım olan minimum yanacaq doldurma sayı nədir, tam çən ilə başlayaraq? Əgər bu mümkün deyilsə, -1 çap edin.
İlk sətir üç tam ədəd , və (3 \le n \le 2 \cdot 10^5, 1 \le q \le 2 \cdot 10^5, 1 \le V \le 10^9) — zirvələrin sayı, sorğuların sayı və yanacaq çəninin tutumu.
Sonrakı sətir hər biri üç tam ədəd 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ə v_i arasında ağırlığı c_i olan bir kənar.
Qrafın bağlı olduğu və öz-özünə döngələrin olmadığı təmin edilir.
Sonrakı sətir hər biri iki tam ədəd s_i və t_i (1 \le s_i, t_i \le n, s_i \neq t_i) — -ci sorğu.
sətir çap edin. -ci sətir bir tam ədəd içerməlidir — -ci sorğu üçün minimum yanacaq doldurma sayı, ya da əgər bu mümkün deyilsə, .
Example 1
Qrafın zirvəsi, kənarı var və yanacaq çəninin tutumu V = 4-dür.
Sorğu 6 \to 7: 6 \to 4 \to 3 \to 5 (istifadə edərək 1 + 2 + 1 = 4 litr, çən boş), zirvə -də yanacaq doldur, sonra 5 \to 7 (istifadə edərək litr). Minimum yanacaq doldurmalar: .
Sorğu 7 \to 6: 7 \to 5 (istifadə edərək litr, çən boş), zirvə -də yanacaq doldur, sonra 5 \to 3 \to 4 \to 6 (istifadə edərək 1 + 2 + 1 = 4 litr). Minimum yanacaq doldurmalar: .
Sorğu 3 \to 2: birbaşa 3 \to 2 keçin, ağırlığı olan kənardan istifadə edərək (çən -dən -a keçir). Yanacaq doldurma lazım deyil. Minimum yanacaq doldurmalar: .
( bal) n \le 3, q \le 10;
( bal) n \le 300, q \le 300;
( bal) n \le 5000, q \le 5000;
( bal) V = 1, s_i-dən t_i-yə yalnız bir yol var;
( bal) V = 1;
( bal) s_i-dən t_i-yə yalnız bir yol var;
( bal) n \le 10^5, q \le 10^5;
( bal) əlavə məhdudiyyət yoxdur.