ركوب سيارة#520

ركوب سيارة

4 ثوان
512 ميغابايت
Very hard

... بسبب اللوائح الجديدة، يُطلب من السائقين أن يكون لديهم بطاريات ...

لديك connected weighted undirected graph مع vertices edges لديك أيضًا سيارة بسعة خزان وقود لا تزيد عن لترات.

عندما تكون في vertices، يمكنك اختيارياً إعادة التعبئة، مما يعيد ملء الخزان إلى بالضبط لترات. للسير عبر edge وزنها ، يجب أن يكون لديك على الأقل لترات من الوقود في الخزان؛ القيام بذلك يكلف بالضبط لترات.

تم إعطاؤك استفسارات. لكل استفسار : ما هو الحد الأدنى لعدد عمليات إعادة التعبئة اللازمة للسفر من إلى ، بدءًا بخزان ممتلئ؟ إذا كان ذلك مستحيلاً، اطبع -1.

Input

السطر الأول يحتوي على ثلاثة أعداد صحيحة ، ، و (3 \le n \le 2 \cdot 10^5، 1 \le q \le 2 \cdot 10^5، 1 \le V \le 10^9) — عدد vertices، عدد الاستفسارات، وسعة خزان الوقود.

الأسطر التالية تحتوي كل منها على ثلاثة أعداد صحيحة 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) — edge بين u_i و v_i بوزن c_i.

يتم ضمان أن graph is connected ولا يحتوي على حلقات ذاتية.

الأسطر التالية تحتوي كل منها على عددين صحيحين s_i و t_i (1 \le s_i، t_i \le n، s_i \neq t_i) — الاستفسار .

Output

اطبع أسطر. يجب أن يحتوي السطر على عدد صحيح واحد — الحد الأدنى لعدد عمليات إعادة التعبئة للاستفسار ، أو إذا كان ذلك مستحيلاً.

Examples

Example 1

Loading
Loading

Note

The graph يحتوي على vertice، edges، وسعة خزان الوقود هي V = 4.

  1. الاستفسار 6 \to 7: السفر 6 \to 4 \to 3 \to 5 (باستخدام 1 + 2 + 1 = 4 لترات، الخزان فارغ)، إعادة التعبئة عند vertices  ، ثم 5 \to 7 (باستخدام لترات). الحد الأدنى من عمليات إعادة التعبئة: .

  2. الاستفسار 7 \to 6: السفر 7 \to 5 (باستخدام لترات، الخزان فارغ)، إعادة التعبئة عند vertices ، ثم 5 \to 3 \to 4 \to 6 (باستخدام 1 + 2 + 1 = 4 لترات). الحد الأدنى من عمليات إعادة التعبئة: .

  3. الاستفسار 3 \to 2: السفر مباشرة 3 \to 2 باستخدام edges ذات الوزن  (الخزان ينتقل من إلى ). لا حاجة لإعادة التعبئة. الحد الأدنى من عمليات إعادة التعبئة: .

Scoring

  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. ( نقاط) لا توجد قيود إضافية.