== 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 vopseste in negru şi invers, dacă avea culoarea neagră, o vopseste in alb.
Din păcate pentru grădinarul Marian, cand a ajuns acasă era deja prea târziu, Marius terminând de efectuat toate cele $M$ operatii. Ingrozit, Marian vrea să afle câte muchii mai au acum culoarea albă.

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ă.

h2. Cerinţă

Determinaţi câte muchii din arbore au culoarea albă după efectuarea tuturor celor $M$ operaţii.

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.

h2. Date de intrare

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.

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).

h2. Date de ieşire

Î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.

Î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.

h2. Restricţii

* $2 ≤ N ≤ 1.000.000$
* $1 ≤ M ≤ 1.000.000$
* Operatiile efectuate de Marius se executa in ordinea din fisierul de intrare.

* $2 ≤ N ≤ 100.000$
* $1 ≤ M ≤ 100.000$
* Operaţiile efectuate de Marius se execută in ordinea din fişierul de intrare.

h2. Exemplu

h3. Explicaţie

Prima operatie schimba culoarea muchiilor dintre nodurile: $(4, 2), (2, 1), (1, 5)$, toate acestea avand acum culoarea neagra (ele fiind initial albe).
A doua operatie schimba culoarea muchiilor dintre nodurile: $(7, 5), (5, 1), (1, 2), (2, 3)$, astfel muchiile $(7, 5)$ si $(2, 3)$ devin neagre (inaintea acestei operatii fiind albe), iar muchiile $(5, 1)$ si $(1, 2)$ devin albe (ele fiind negre din cauza operatiei precedente).
Astfel, dupa aplicarea celor doua operatii, numarul de muchii albe este 4: $(1, 2), (1, 5), (5, 8), (6, 1)$.

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") ==

7808