==Include(page="template/taskheader" task_id="atac")==

==Include(page="template/raw")==
 
In tara Arboreea lucrurile au iesit de sub control. OTPB (Organizatia Terorista Petrica Bomba) a hotarat sa atace doua orase din aceasta tara deoarece liderul organizatiei, Petrica, a pierdut alegerile prezidentiale din anul 2004. Tara are $N$ orase, numerotate de la $1$ la $N$, iar reteaua oraselor si strazile dintre aceastea formeaza un arbore (graf neorientat conex ce nu contine cicluri). OTPB stie pentru fiecare strada cate bombe trebuie sa utilizeze pentru a o scoate din uz. Acum se pune problema determinarii numarului cel mai mic de bombe pe care trebuie sa-l utilizeze OTPB pentru ca intre cele doua orase alese (considerate de importanta majora in Arboreea) sa nu mai existe drum intre ele dupa bombardament. Cum importanta oraselor se schimba pe parcusul evolutiei tarii, OTPB vrea sa stie numarul minim de bombe pentru atacul asupra mai multor perechi de orase, mai exact $M$. Totusi se doreste comunicarea usoara a acestor $M$ perechi intre organizatiile teroriste din tara. Astfel, nu se poate transmite intreaga lista a celor $M$ perechi de orase asupra carora se doreste efectuarea unui atac deoarece reteaua de legatura dintre organizatii este cam inceata la capitolul trasmiterea datelor. Totusi s-a gasit o solutie: stiind prima pereche de orase $X$ si $Y$ asupra carora se va efectua un atac si numarul minim de bombe $Z$ ce trebuie utilizate in cazul atacului in orasele $X$ si $Y$, urmatoarea pereche de orase, a doua, se determina utilizand relatiile:

In tara Arboreea lucrurile au iesit de sub control. OTPB (Organizatia Terorista Petrica Bomba) a hotarat sa atace doua orase din aceasta tara deoarece liderul organizatiei, Petrica, a pierdut alegerile prezidentiale din anul 2004. Tara are $N$ orase, numerotate de la $1$ la $N$, iar reteaua oraselor si strazile dintre aceastea formeaza un arbore (graf neorientat conex ce nu contine cicluri). OTPB stie pentru fiecare strada cate bombe trebuie sa utilizeze pentru a o scoate din uz. Acum se pune problema determinarii numarului cel mai mic de bombe pe care trebuie sa-l utilizeze OTPB pentru ca intre cele doua orase alese (considerate de importanta majora in Arboreea) sa nu mai existe drum dupa bombardament. Cum importanta oraselor se schimba pe parcusul evolutiei tarii, OTPB vrea sa stie numarul minim de bombe pentru atacul asupra mai multor perechi de orase, mai exact $M$. Totusi se doreste comunicarea usoara a acestor $M$ perechi intre organizatiile teroriste din tara. Astfel, nu se poate transmite intreaga lista a celor $M$ perechi de orase asupra carora se doreste efectuarea unui atac deoarece reteaua de legatura dintre organizatii este cam inceata la capitolul trasmiterea datelor. Totusi s-a gasit o solutie: stiind prima pereche de orase $X$ si $Y$ asupra carora se va efectua un atac si numarul minim de bombe $Z$ ce trebuie utilizate in cazul atacului in orasele $X$ si $Y$, urmatoarea pereche de orase, a doua, se determina utilizand relatiile:

$X' = (X*A + Y*B) mod N + 1$
$Y' = (Y*C + Z*D) mod N + 1$

h2. Date de Intrare

Pe prima linie a fisierului $atac.in$ se afla trei numere reprezentand numarul de orase, numarul de perechi de orase pentru care organizatia vrea sa afle numarul minim de bombe in cazul unui atac asupra lor si numarul $P$ de perechi pentru care programul vostru trebuie sa afiseze raspunsul. Pe urmatoarele $N-1$ linii se afla cate doua numere naturale $U$, $V$ cu semnificatia: exista o strada de la orasul $U$ la orasul $i$ ($i$ este indicele liniei care va lua valori de la $2$ la $N$) pentru care OTPB trebuie sa utilizeze $V$ bombe pentru a o scoate din uz. Pe urmatoarea linie se afla $6$ numere $X, Y, A, B, C, D$ cu semnificatia din enunt.

Pe prima linie a fisierului $atac.in$ se afla trei numere reprezentand numarul de orase, numarul de perechi de orase pentru care organizatia vrea sa afle numarul minim de bombe in cazul unui atac asupra lor si numarul $P$ de perechi pentru care programul vostru trebuie sa afiseze raspunsul. Pe urmatoarele $N-1$ linii se afla cate doua numere naturale $U$, $V$ cu semnificatia: exista o strada de la orasul $U$ la orasul $i$ ({$i$} este indicele liniei care va lua valori de la $2$ la $N$) pentru care OTPB trebuie sa utilizeze $V$ bombe pentru a o scoate din uz. Pe urmatoarea linie se afla $6$ numere $X, Y, A, B, C, D$ cu semnificatia din enunt.

h2. Date de Iesire

h2. Restrictii si precizari

* 1 ≤ N ≤ 32.000
* 0 < P < M &le; 500.000
* P &le; 10.000
* 0 &le; A, B, C, D &le; 10.000
* numarul de bombe pentru a scoate din uz o strada este un numar natural mai mic decat 100.000

* $1 ≤ N ≤ 32.000$
* $0 < P < M &le; 500.000$
* $P &le; 10.000$
* $0 &le; A, B, C, D &le; 10.000$
* numarul de bombe pentru a scoate din uz o strada este un numar natural mai mic decat $100.000$

* OTPB nu va scoate din uz nici o strada; se doreste sondarea terenului si nimic mai mult, momentan; deci pentru fiecare pereche de orase din cele $M$ se considera ca reteaua de strazi este intacta (nici o strada nu este bombardata).
* Se vor acorda puncte pe un test doar daca toate cele $P$ numere din fisierul de iesire sunt corect aflate.
* Este clar ca pentru a afla corect cele $P$ numere trebuie sa calculati numarul minim de bombe pentru toate cele $M$ perechi de orase.

h2. Exemplu

table(example). |_. atac.in |_. atac.out |
| 7 3 2
1 1

| 1
1 |

==Include(page="template/taskfooter" task_id="atac")==

==Include(page="template/taskfooter" task_id="atac")==
 
 
 

98