Nerăbdătoare să afle descrierea soluțiilor de la concursul de **inserează gluma aici**, Maia s-a gândit la următoarea problemă:

Se dă un arbore T cu N noduri numerotate de la 0 la N − 1 și un graf neorientat G cu V ≥ N noduri (numerotate de la 0 la V − 1) și E muchii. Se cere o colorare c : {0, ... , V − 1} → {0, ... , N − 1} a nodurilor lui G cu numere de la 0 la N − 1, astfel încât următoarele să se respecte:

• Pentru orice 0 ≤ i < N, c(i) = i;
• Dacă există muchia (x, y) în graful G, atunci există muchia (c(x), c(y)) în arborele T. Această implicație nu este un “dacă și numai dacă”; adică, pentru două noduri x, y, dacă muchia (c(x), c(y)) există în arbore, nu este necesar ca muchia (x, y) să existe în graf.

Date de intrare

Pe prima linie se va găsi Q, numărul de scenarii. Urmează apoi Q grupe de linii, fiecare descriind câte un scenariu de rezolvat. Pe prima linie a unui scenariu se găsește N, numărul de noduri din arborele T. Pe următoarele N - 1 linii se găsesc numerele $A_i$ și $B_i$, cu semnificația că există o muchie în T între $A_i$ și $B_i$ pentru fiecare i de la 0 la N − 2. Pe următoarea linie se află numerele V E, unde V reprezintă numărul de noduri din graful G, iar E reprezintă numărul de muchii din graful G. Pe următoarele E linii se găsesc numerele $X_i$ și $Y_i$, cu semnificația că există o muchie în G între $X_i$ și $Y_i$ pentru fiecare i de la 0 la E − 1

Date de ieșire

Se vor afișa T linii, fiecare formată din V numere separate prin spații, pentru fiecare i de la 0 la V − 1 culoarea nodului i din graful G.

Restricții și precizări

• 1 ≤ Q ≤ 100 000
• 1 ≤ N ≤ V ≤ 100 000
• 1 ≤ E ≤ 100 000
• $0 ≤ A_i, B_i ≤ N − 1$ pentru 0 ≤ i ≤ N − 2 și $A_i ≠ B_i$
• $0 ≤ X_i, Y_i ≤ V − 1$ pentru 0 ≤ i ≤ E − 1 și $X_i ≠ Y_i$
• Fie $S_N$ suma N-urilor pentru toate scenariile, $S_V$ suma V-urilor, $S_E$ suma E-urilor. $1 ≤ S_N, S_E, S_V ≤ 100 \ 000$
• Se garantează că nici una dintre cele E muchii ale grafului G nu unește două noduri cu indici din mulțimea {0, ... , N − 1}.
• Se garantează că va exista cel puțin o colorare pentru fiecare test.
• Dacă există mai multe colorări posibile, se va accepta oricare dintre ele.

Subtask 1 (4 puncte)

• N = 2

Subtask 2 (8 puncte)

• $1 ≤ S_N, S_E, S_V ≤ 20$

Subtask 3 (21 de puncte)

• $1 ≤ S_N, S_E, S_V ≤ 500$
• Arborele este lanț.

Subtask 4 (30 de puncte)

• $1 ≤ S_N, S_E, S_V ≤ 2 \ 000$

Subtask 5 (14 puncte)

• Arborele este lanț.

Subtask 6 (23 de puncte)

• Fără restricții suplimentare.

Exemplu

stdin

2
2
0 1
4 2
2 0
3 1
4
0 1
0 2
0 3
5 3
1 4
2 4
3 4

stdout

0 1 1 0
0 1 2 3 0

stdin

1
3
0 1
1 2
4 2
3 0
3 2

stdout

0 1 2 1