== include(page="template/taskheader" task_id="arbore5") ==
Grădinarul Marian deţine un arbore cu $N$ noduri, fiecare muchie fiind iniţial vopsită in alb. Marian fiind plecat de acasă, prietenul său cel mai bun, Marius, strică frumuseţea de arbore aplicând $M$ operaţii de tipul: alege o pereche de noduri $(a, b)$ şi vopseşte toate muchiile de pe drumul ce uneşte nodul $a$ cu nodul $b$ în felul următor: dacă muchia avea culoarea albă, Marius o vopseşte în negru şi invers, dacă avea culoarea neagră, o vopseşte în alb.
Din păcate pentru grădinarul Marian, cand a ajuns acasă era deja prea târziu, Marius finalizând de efectuat toate cele $M$ operaţii. Îngrozit, Marian vrea să afle câte muchii mai au acum culoarea albă.
Gradinarul Marian detine un arbore cu $N$ noduri, fiecare muchie fiind initial vopsita in alb. Marian fiind plecat de acasa, prietenul sau cel mai bun, Marius, strica frumusetea de arbore aplicand $M$ operatii de tipul: alege o pereche de noduri $(a, b)$ si vopseste toate muchiile de pe drumul ce uneste nodul $a$ cu nodul $b$ in felul urmator: daca muchia avea culoarea alba, Marius o vopseste in negru si invers, daca avea culoarea neagra, o vopseste in alb.
Din pacate pentru gradinarul Marian, cand a ajuns acasa era deja prea tarziu, Marius terminand de efectuat toate cele $M$ operatii. Ingrozit, Marian vrea sa afle cate muchii mai au acum culoarea alba.
h2. Cerinţă
h2. Cerinta
Fiind precizate operaţiile aplicate de Marius, trebuie sa determinaţi câte muchii din arbore au culoarea albă după efectuarea tuturor celor $M$ operaţii.
Determinati cate muchii din arbore au culoarea alba dupa efectuarea tuturor celor $M$ operatii.
h2. Date de intrare
Fişierul de intrare $arbore5.in$ conţine pe prima linie două numere naturale $N$ şi $M$, separate prin câte un spaţiu, reprezentând numărul de noduri ale arborelui deţinut de grădinarul Marian, respectiv numărul de operaţii efectuate de Marius. Pe următoarele $N-1$ linii se află câte o pereche de numere $x y$, separate prin câte un spaţiu, reprezentând faptul că în arbore există o muchie de la nodul $x$ la nodul $y$. Pe următoarele $M$ linii se află câte o pereche de numere $a b$, separate prin câte un spaţiu, reprezentând o operaţie efectuata de Marius (toate muchiile de pe drumul care începe la nodul $a$ şi se termină la nodul $b$ îşi schimbă culoarea).
Fişierul de intrare $arbore5.in$ contine pe prima linie doua numere naturale $N$ si $M$, separate prin cate un spatiu, reprezentand numarul de noduri ale arborelui detinut de gradinarul Marian, respectiv numarul de operatii efectuate de Marius. Pe urmatoarele $N-1$ linii se afla cate o pereche de numere $x y$, separate prin cate un spatiu, reprezentand faptul ca in arbore exista o muchie de la nodul $x$ la nodul $y$. Pe urmatoarele $M$ linii se afla cate o pereche de numere $a b$, separate prin cate un spatiu, cu proprietatea ca toate muchiile de pe drumul care incepe la nodul $a$ si se termina la nodul $b$ isi schimba culoarea.
h2. Date de ieşire
În fişierul de ieşire $arbore5.out$ trebuie să existe pe prima linie un singur număr natural, reprezentând câte muchii au culoarea albă după efectuarea tuturor celor $M$ operaţii.
În fişierul de ieşire $arbore5.out$ trebuie sa existe pe prima linie un singur numar natural, reprezentand cate muchii au culoarea alba dupa efectuarea tuturor celor $M$ operatii.
h2. Restricţii
* $2 ≤ N ≤ 100.000$
* $1 ≤ M ≤ 100.000$
* Operaţiile efectuate de Marius se execută in ordinea din fişierul de intrare.
* $2 ≤ N ≤ 1.000.000$
* $1 ≤ M ≤ 1.000.000$
* Operatiile efectuate de Marius se executa in ordinea din fisierul de intrare.
h2. Exemplu
table(example). |_. arbore5.in |_. arbore5.out |
| 8 2
1 2
3 2
2 4
1 5
6 1
5 7
5 8
4 5
7 3
| 4
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|
h3. Explicaţie
Prima operatie schimbă culoarea muchiilor dintre nodurile: $(4, 2), (2, 1), (1, 5)$, toate acestea având acum culoarea neagră (ele fiind iniţial albe).
A doua operatie schimbă culoarea muchiilor dintre nodurile: $(7, 5), (5, 1), (1, 2), (2, 3)$, astfel muchiile $(7, 5)$ şi $(2, 3)$ devin neagre (înaintea acestei operatii fiind albe), iar muchiile $(5, 1)$ şi $(1, 2)$ devin albe (ele fiind negre din cauza operaţiei precedente).
Astfel, după aplicarea celor doua operaţii, numărul de muchii albe este 4: $(1, 2), (1, 5), (5, 8), (6, 1)$.
...
== include(page="template/taskfooter" task_id="arbore5") ==
