Дано два дерева $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$.

Input

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

$$ \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$ є деревом.

Output

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

Якщо можливих відповідей декілька, ви можете вивести будь-яку з них.

Examples

Input 1

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

Output 1

1
3
2

Note

У першому рядку прикладу вихідних даних для $i = 1$ вибрано $j = 1$. Обмін ребра $(1, 3)$ дерева $A$ з ребром $(1, 2)$ дерева $B$ залишає і $A$, і $B$ деревами.

Для $i = 2$ і ребро з $A$, і вибране ребро з $B$ є ребром $(2, 4)$, тому їх обмін не змінює жодне з дерев. Інші коректні відповіді також можливі.