俾定兩棵樹 $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)$，所以交換佢哋唔會改變任何一棵樹。其他合法嘅輸出亦都係可以嘅。