Dane są dwa drzewa, $A$ oraz $B$, każde o $N$ wierzchołkach. Oba drzewa mają ten sam zbiór poetykietowanych wierzchołków $\{1, 2, \dots, N\}$.

Dla każdego $i$ ($1 \le i \le N - 1$), $i$-ta krawędź drzewa $A$ łączy wierzchołki $u_i$ oraz $v_i$. Dla każdego $j$ ($1 \le j \le N - 1$), $j$-ta krawędź drzewa $B$ łączy wierzchołki $x_j$ oraz $y_j$.

Dla każdego $i = 1, 2, \dots, N - 1$ rozwiąż następujący problem.

• Znajdź liczbę całkowitą $j$ spełniającą $1 \le j \le N - 1$, taką że po następującej wymianie zarówno $A$, jak i $B$ pozostaną drzewami:
  • Usuń z $A$ krawędź łączącą $u_i$ oraz $v_i$, a z $B$ usuń krawędź łączącą $x_j$ oraz $y_j$.
  • Następnie dodaj do $A$ krawędź łączącą $x_j$ oraz $y_j$, a do $B$ dodaj krawędź łączącą $u_i$ oraz $v_i$.

Każda wymiana jest rozpatrywana niezależnie, zaczynając od początkowych drzew $A$ i $B$.

Można udowodnić, że przy podanych ograniczeniach dla każdego $i$ istnieje co najmniej jedna taka liczba całkowita $j$.

Wejście

Wejście składa się z pojedynczego przypadku testowego w następującym formacie.

$$ \begin{aligned} &N \\ &u_1 \ v_1 \\ &u_2 \ v_2 \\ &\vdots \\ &u_{N-1} \ v_{N-1} \\ &x_1 \ y_1 \\ &x_2 \ y_2 \\ &\vdots \\ &x_{N-1} \ y_{N-1} \end{aligned} $$

Liczba całkowita $N$ oznacza liczbę wierzchołków w obu drzewach $A$ i $B$ ($2 \le N \le 2 \times 10^5$).

Kolejne $N - 1$ wierszy opisuje krawędzie drzewa $A$. Dla każdego $i = 1, \dots, N - 1$ liczby całkowite $u_i$ oraz $v_i$ ($1 \le u_i, v_i \le N$) oznaczają, że $i$-ta krawędź łączy wierzchołki $u_i$ oraz $v_i$. Gwarantuje się, że $A$ jest drzewem.

Następne $N - 1$ wierszy opisuje krawędzie drzewa $B$. Dla każdego $j = 1, \dots, N - 1$ liczby całkowite $x_j$ oraz $y_j$ ($1 \le x_j, y_j \le N$) oznaczają, że $j$-ta krawędź łączy wierzchołki $x_j$ oraz $y_j$. Gwarantuje się, że $B$ jest drzewem.

Wyjście

Wypisz $N - 1$ wierszy. Dla każdego $i = 1, 2, \dots, N - 1$, $i$-ty wiersz powinien zawierać liczbę całkowitą $j$ spełniającą warunek z treści zadania dla $i$-tej krawędzi drzewa $A$.

Jeśli istnieje wiele możliwych odpowiedzi, możesz wypisać dowolną z nich.

Przykład

Wejście 1

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

Wyjście 1

1
3
2

Uwagi

W pierwszym wierszu przykładowego wyjścia dla $i = 1$ wybrano $j = 1$. Wymiana krawędzi $(1, 3)$ z drzewa $A$ z krawędzią $(1, 2)$ z drzewa $B$ sprawia, że zarówno $A$, jak i $B$ pozostają drzewami.

Dla $i = 2$ zarówno krawędź z $A$, jak i wybrana krawędź z $B$ to $(2, 4)$, więc ich wymiana nie zmienia żadnego z drzew. Inne poprawne odpowiedzi są również możliwe.