Painting

painting

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 2 numere $X Y$, cu semnificatia ca subarborele nodului $X$ este colorat cu culoarea $Y$.

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

h2. Date de ieşire

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

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

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

h2. Exemplu