それぞれ $N$ 個の頂点を持つ 2 つの木 $A$ と $B$ が与えられます。どちらの木も同じラベル付き頂点集合 $\{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$ について、次の問題を解いてください。

• 次の交換を行った後も $A$ と $B$ の両方が木のままであるような、$1 \le j \le N - 1$ を満たす整数 $j$ を 1 つ見つけよ。
  • $A$ から $u_i$ と $v_i$ を結ぶ辺を取り除き、$B$ から $x_j$ と $y_j$ を結ぶ辺を取り除く。
  • その後、$A$ に $x_j$ と $y_j$ を結ぶ辺を追加し、$B$ に $u_i$ と $v_i$ を結ぶ辺を追加する。

各交換は独立に、元の木 $A$ と $B$ の状態から行うものとして考えます。

与えられた制約の下で、すべての $i$ について条件を満たす整数 $j$ が少なくとも 1 つ存在することが証明できます。

入力

入力は以下の形式の単一のテストケースからなります。

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

注記

出力例の 1 行目では、$i = 1$ に対して $j = 1$ が選ばれています。$A$ の辺 $(1, 3)$ と $B$ の辺 $(1, 2)$ を交換しても、$A$ と $B$ はともに木のままです。

$i = 2$ については、$A$ の辺も選ばれた $B$ の辺もともに $(2, 4)$ であるため、これらを交換してもどちらの木も変化しません。これ以外の正しい出力も認められます。