給定兩棵樹 $A$ 和 $B$，每棵樹都有 $N$ 個頂點。兩棵樹具有相同的標號頂點集 $\{1, 2, \dots, N\}$。

對於每個 $i$（$1 \le i \le N - 1$），樹 $A$ 的第 $i$ 條邊連接頂點 $u_i$ 和 $v_i$。對於每個 $j$（$1 \le j \le N - 1$），樹 $B$ 的第 $j$ 條邊連接頂點 $x_j$ 和 $y_j$。

對於每個 $i = 1, 2, \dots, N - 1$，解決以下問題。

• 找一個滿足 $1 \le j \le N - 1$ 的整數 $j$，使得進行如下交換後，$A$ 和 $B$ 仍然都是樹：
  • 從 $A$ 中移除連接 $u_i$ 和 $v_i$ 的邊，並從 $B$ 中移除連接 $x_j$ 和 $y_j$ 的邊。
  • 然後，向 $A$ 中加入一條連接 $x_j$ 和 $y_j$ 的邊，並向 $B$ 中加入一條連接 $u_i$ 和 $v_i$ 的邊。

每次交換均相互獨立地從初始的樹 $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$ 行應包含一個針對 $A$ 的第 $i$ 條邊滿足題目敘述條件的整數 $j$。

如果存在多個可能的答案，你可以輸出其中任意一個。

範例

輸入格式 1

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

輸出格式 1

1
3
2

說明

在範例輸出的第一行中，對於 $i = 1$ 選擇了 $j = 1$。將 $A$ 的邊 $(1, 3)$ 與 $B$ 的邊 $(1, 2)$ 交換後，$A$ 和 $B$ 仍然都是樹。

對於 $i = 2$，$A$ 的邊與所選的 $B$ 的邊皆為 $(2, 4)$，因此交換它們不會改變任何一棵樹。其他合法的輸出也是允許的。