Даны два дерева $A$ и $B$, каждое из которых содержит $N$ вершин. Оба дерева имеют одно и то же множество пронумерованных вершин $\{1, 2, \dots, N\}$.

Для каждого $i$ ($1 \le i \le N - 1$) $i$-е ребро дерева $A$ соединяет вершины $u_i$ и $v_i$. Для каждого $j$ ($1 \le j \le N - 1$) $j$-е ребро дерева $B$ соединяет вершины $x_j$ и $y_j$.

Для каждого $i = 1, 2, \dots, N - 1$ решите следующую задачу.

• Найдите целое число $j$ ($1 \le j \le N - 1$), такое что в результате следующего обмена и $A$, и $B$ останутся деревьями:
  • Удалите ребро, соединяющее $u_i$ и $v_i$, из $A$, и удалите ребро, соединяющее $x_j$ и $y_j$, из $B$.
  • Затем добавьте ребро, соединяющее $x_j$ и $y_j$, в $A$, и добавьте ребро, соединяющее $u_i$ и $v_i$, в $B$.

Каждый обмен рассматривается независимо, начиная с исходных деревьев $A$ и $B$.

Можно доказать, что при заданных ограничениях для каждого $i$ существует хотя бы одно такое целое число $j$.

Входные данные

Входные данные состоят из одного тестового примера в следующем формате.

$$ \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} $$

Целое число $N$ — количество вершин в деревьях $A$ и $B$ ($2 \le N \le 2 \times 10^5$).

Следующие $N - 1$ строк описывают рёбра дерева $A$. Для каждого $i = 1, \dots, N - 1$ целые числа $u_i$ и $v_i$ ($1 \le u_i, v_i \le N$) означают, что $i$-е ребро соединяет вершины $u_i$ и $v_i$. Гарантируется, что $A$ является деревом.

Следующие $N - 1$ строк описывают рёбра дерева $B$. Для каждого $j = 1, \dots, N - 1$ целые числа $x_j$ и $y_j$ ($1 \le x_j, y_j \le N$) означают, что $j$-е ребро соединяет вершины $x_j$ и $y_j$. Гарантируется, что $B$ является деревом.

Выходные данные

Выведите $N - 1$ строк. Для каждого $i = 1, 2, \dots, N - 1$ в $i$-й строке должно содержаться целое число $j$, удовлетворяющее условию задачи для $i$-го ребра дерева $A$.

Если возможных ответов несколько, вы можете вывести любой из них.

Примеры

Входные данные 1

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

Выходные данные 1

1
3
2

Примечание

В первой строке примера выходных данных для $i = 1$ выбрано $j = 1$. Обмен ребра $(1, 3)$ дерева $A$ с ребром $(1, 2)$ дерева $B$ оставляет оба графа $A$ и $B$ деревьями.

Для $i = 2$ и ребро из $A$, и выбранное ребро из $B$ равны $(2, 4)$, поэтому их обмен не меняет ни одно из деревьев. Возможны и другие корректные ответы.