painting

Painting

== include(page="template/taskheader" task_id="painting") ==

Fie un arbore cu $N$ noduri, fiecare nod avand o culoare. Initial, toate nodurile au culoarea $1$. Pe acest arbore se fac $M$ operatii de tipul: la se coloreaza toate nodurile din subarborele lui $X$ cu culoarea $Y$. Se considera ca radacina arborelui este nodul $1$.

Fie un arbore cu $N$ noduri, fiecare nod avand o culoare. Initial, toate nodurile au culoarea $1$. Pe acest arbore se fac $M$ operatii de tipul: se coloreaza toate nodurile din subarborele lui $X$ cu culoarea $Y$. Se considera ca radacina arborelui este nodul $1$.

Culoarea unui nod este data de culoarea ultimei operatii aplicate nodului respectiv.
Care este culoarea fiecarui nod dupa executarea tuturor operatiilor?

Fişierul de intrare $painting.in$ va contine pe prima linie numerele $N$ si $M$.
Urmatoarele $N - 1$ linii vor contine cate o pereche $X Y$, cu semnificatia ca exista muchie in arbore intre nodurile respective.

Urmatoarele $M$ linii vor contine cate trei numere $X Y$, cu semnificatia ca subarborele nodului $X$ este colorat cu culoarea $Y$.

Urmatoarele $M$ linii vor contine cate 2 numere $X Y$, cu semnificatia ca subarborele nodului $X$ este colorat cu culoarea $Y$.

h2. Date de ieşire

În fişierul de ieşire $painting.out$ va contine $N$ numere, reprezentand culoarea fiecarui nod.

În fişierul de ieşire $painting.out$ va contine $N$ numere, al $i$-lea numar reprezentand culoarea nodului $i$.

h2. Restricţii
* $1 ≤ N, M ≤ 10^5^$

* $1 ≤ Culoarea unu nod ≤ 10^4^$

* $1 ≤ Culoarea unui nod ≤ 10^4^$

h2. Exemplu
table(example). |_. painting.in |_. painting.out |

| 7 5

|7 4

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

2 7
4 5
3 9
5 4

2 4
|
1

|1 7 9 5 4 5 9

|