... Նոր կանոնակարգերի պատճառով, վարորդները պարտավոր են ունենալ մարտկոցներ ...
Դուք ունեք մի կապակցված կշիռներով չուղղորդված գրաֆ, որը բաղկացած է գագաթներից և եզրերից: Դուք նաև ունեք ավտոմեքենա, որի վառելիքի բաքը կարող է պահել առավելագույնը լիտր:
Երբ դուք գտնվում եք գագաթում, դուք կարող եք, ցանկության դեպքում, վերալիցքավորել, ինչը լցնում է բաքը մինչև ճիշտ լիտր: Որպեսզի անցնեք քաշով կող, դուք պետք է ունենաք առնվազն լիտր վառելիք բաքում; դա անելը արժե լիտր:
Դուք ստանում եք հարցում: Յուրաքանչյուր հարցման համար . ինչքան նվազագույն վերալիցքավորումներ են անհրաժեշտ -ից -ի ճանապարհորդելու համար, սկսելով լի բաքով: Եթե դա անհնար է, տպեք -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) թվեր — -րդ հարցումը:
Տպեք տող: -րդ տողը պետք է պարունակի մեկ ամբողջ թիվ — -րդ հարցման համար նվազագույն վերալիցքավորումների քանակը, կամ , եթե դա անհնար է:
Example 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;
( միավոր) լրացուցիչ սահմանափակումներ չկան.