Metro

metro

h2. Date de intrare

Fişierul $metro.in$ conţine două numere întregi pe prima linie, N şi M. Pe următoarele N-1 linii se află două numere întregi xi, yi  reprezentând calea între staţiile xi si yi. Următoarele M linii descriu câte un metrou folosind trei numere întregi ai, bi şi oi  cu semificaţia ca metroul numerotat cu oi  merge de la staţia ai la bi.

Fişierul $metro.in$ conţine două numere întregi pe prima linie, N şi M. Pe următoarele N-1 linii se află două numere întregi xi, yi  reprezentând calea între staţiile xi si yi. Următoarele M linii descriu câte un metrou folosind trei numere întregi ai, bi şi noi  cu semificaţia ca metroul numerotat cu noi  merge de la staţia ai la bi.

h2. Date de ieşire

1 ≤ M ≤ 200,000
1 ≤ noi ≤ M pentru toţi 1 ≤ i ≤ M
Se garantează că se poate ajunge dintr-o staţie în oricare alta

Limită de timp: 2.5 secunde
Limită de memorie: 512 MB

h2. Exemplu