Fişierul intrare/ieşire:	arbore5.in, arbore5.out	Sursă	Infoarena Monthly 2012, Runda 4
Autor	Silviu Popescu	Adăugată de	Mr. Noname •cezar305
Timp execuţie pe test	0.1 sec	Limită de memorie	20480 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Arbore5

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.

Cerinta

Determinati cate muchii din arbore au culoarea alba dupa efectuarea tuturor celor M operatii.

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.

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.

Restricţii

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

Exemplu

Explicaţie

...

Cum se trimit solutii?