evitata

Kaguya tocmai a reușit să programeze o nouă sesiune de shopping cu Kei, sora lui Miyuki. Doar cu Kei, de data asta, fără surorile Fujiwara... O să pot afla totul despre Miyuki! De înțeles, Kaguya nu vrea sub nicio formă să se întâlnească cu altcineva. Și tot de înțeles este și supărarea Kaguyei când află că Chika Fujiwara plănuiește propria sesiune de shopping în aceeași zi și același centru comercial.

Centrul comercial este format din N magazine numerotate de la 1 la N, unite între ele prin N − 1 alei, astfel încât să se poată ajunge din orice magazin în oricare altul parcurgând una sau mai multe alei. Kaguya și Kei plănuiesc să-și petreacă ziua plecând din magazinul S și mergând până la magazinul F, vizitând fiecare magazin de pe drumul de distanță minimă ce le unește (incluzând magazinele S și F). Notăm acest drum cu $D_{S,F}$ . În general, notăm cu $D_{x,y}$ mulțimea minimă de magazine care trebuie vizitate pentru a ajunge din magazinul x în magazinul y, traversând aleile centrului comercial.

Kaguya a aflat Q posibile planuri ale lui Chika. Similar cu planul Kaguyei, planul i presupune ca Chika să plece din magazinul $X_i$ și să meargă până în magazinul $Y_i$, vizitând toate magazinele de pe drumul minim dintre ele.

Kaguya ajunge rapid la concluzia că singura metodă pentru a o abate pe Chika din drum este de a construi o nouă alee între două magazine t și u în centrul comercial. Astfel, notăm cu $D^{t,u}_{x,y}$ o mulțime minimă de magazine care trebuie vizitate pentru a ajunge din magazinul x în magazinul y, traversând aleile centrului comercial, posibil (dar nu obligatoriu) și aleea (t, u) nou construită.

Pentru fiecare plan, Kaguya se întreabă în câte moduri poate fi adăugată o nouă alee (t, u) în centrul comercial, astfel încât t < u și niciun drum de distanță minimă $D^{t,u}_{X_i,Y_i}$ să nu aibă niciun magazin comun cu drumul $D_{S,F}$ . Întrebările Kaguyei sunt pur ipotetice și nu duc la adăugarea niciunei alei în centrul comercial după ce își află răspunsul.

Protocol de interactiune

Pentru a rezolva problema, trebuie să implementați funcția:

void solve(int N, int Q, int S, int F, std::vector<int> A, std::vector<int> B, std::vector<int> X, std::vector<int> Y, std::vector<long long> &sol);

Parametrii N, Q, S și F au semnificația din enunț. Parametrii A și B sunt două șiruri indexate de la 0, cu N−1 elemente fiecare, și reprezintă aleile din centrul comercial; poziția i reprezintă existența unei alei între magazinele A[i] și B[i]. Parametrii X și Y sunt două șiruri indexate de la 0, cu Q elemente fiecare, și conțin planurile lui Chika; poziția i reprezintă planul cu numărul i de a merge din magazinul X[i] până la magazinul Y[i]. Parametrul sol reprezintă un șir de Q elemente; voi trebuie să populați, pe fiecare poziție i de la 0 la Q − 1, răspunsul la întrebarea Kaguyei referitoare la cel de-al i-lea plan.
Funcția va fi apelată o singura dată per test.

Interactor local

Pentru a vă ajuta să vă testați codul, vă punem la dispoziție un interactor local. Din consolă, interactorul local va citi, în ordine, patru numere N, Q, S și F, apoi N−1 perechi de numere $A_i$ și $B_i$, apoi Q perechi de numere $X_i$ și $Y_i$. Interactorul va apela funcția solve corespunzător datelor citite. În consolă, interactorul va afișa apoi cele Q elemente din șirul sol, câte unul pe fiecare linie.

Restricţii

• 1 ≤ N, Q ≤ 100 000
• 1 ≤ S, F ≤ N
• $1 ≤ X_i, Y_i ≤ N$, pentru orice i, 0 ≤ i < Q
• $\sum_{i=0}^{Q−1} dist(X_i, \ Y_i) ≤ 1 \ 000 \ 000$, unde dist(a, b) reprezintă numărul minim de alei care trebuie traversate pentru a ajunge din magazinul a în magazinul b, înainte de a adăuga aleea suplimentară.
• Aleea (u, t) care este adăugată poate să existe deja în centrul comercial; în acest caz vor exista două alei între magazinele u și t.

Subtask 1 (5 puncte)

• N, Q ≤ 100

Subtask 2 (5 puncte)

• N, Q ≤ 500

Subtask 3 (10 puncte)

• N, Q ≤ 5 000, $D_{S,F}$ și $D_{X_i,Y_i}$ au cel puțin un magazin comun, ∀ i, 0 ≤ i < Q.

Subtask 4 (20 puncte)

• N, Q ≤ 5 000

Subtask 5 (15 puncte)

• N ≤ 10 000, Q ≤ 100 000, $D_{S,F}$ și $D_{X_i,Y_i}$ au cel puțin un magazin comun, ∀i, 0 ≤ i < Q.

Subtask 6 (30 puncte)

• N ≤ 10 000, Q ≤ 100 000

Subtask 7 (5 puncte)

• $D_{S,F}$ și $D_{X_i,Y_i}$ au cel puțin un magazin comun, ∀i, 0 ≤ i < Q.

Subtask 8 (10 puncte)

• Fără restricții suplimentare

Exemple

stdin

6 4 1 2
1 2
2 3
1 4
4 5
5 6
3 5
6 5
6 1
6 4

stdout

3
15
0
14

Explicații

Avem N = 6 magazine și Q = 3 planuri posibile. Drumul Kaguyei și al lui Kei pleacă din magazinul S = 1 și ajunge în magazinul F = 2, parcurgând exact o alee.

Pentru primul plan, aleile (3, 5), (4, 5), (5, 6) satisfac condiția din enunț.

Pentru al doilea plan, orice alee am adăuga satisface condiția din enunț.

Pentru al treilea plan, nicio alee nu satisface condiția din enunț, întrucât magazinul 1 se află pe drumul dintre magazinele S = 1 și F = 2.

Pentru al patrulea plan, toate aleile mai puțin una satisfac condiția din enunț. Dacă am adăuga aleea (6, 1), ar exista două drumuri de lungime minimă: 6 − 1 − 4 și 6 − 5 − 4. Primul dintre acestea are un magazin comun, magazinul 1, cu drumul dintre S = 1 și F = 2, ceea ce face ca această alee să nu satisfacă condiția din enunț.