Bạn được cho hai cây $A$ và $B$, mỗi cây có $N$ đỉnh. Cả hai cây đều có chung tập hợp các đỉnh được đánh số $\{1, 2, \dots, N\}$.

Với mỗi $i$ ($1 \le i \le N - 1$), cạnh thứ $i$ của $A$ nối hai đỉnh $u_i$ và $v_i$. Với mỗi $j$ ($1 \le j \le N - 1$), cạnh thứ $j$ của $B$ nối hai đỉnh $x_j$ và $y_j$.

Với mỗi $i = 1, 2, \dots, N - 1$, hãy giải bài toán sau.

• Tìm một số nguyên $j$ thỏa mãn $1 \le j \le N - 1$ sao cho phép hoán đổi sau đây giữ cho cả $A$ và $B$ đều là cây:
  • Xóa cạnh nối $u_i$ và $v_i$ khỏi $A$, đồng thời xóa cạnh nối $x_j$ và $y_j$ khỏi $B$.
  • Sau đó, thêm một cạnh nối $x_j$ và $y_j$ vào $A$, đồng thời thêm một cạnh nối $u_i$ và $v_i$ vào $B$.

Mỗi phép hoán đổi được xét một cách độc lập, bắt đầu từ hai cây $A$ và $B$ ban đầu.

Có thể chứng minh rằng luôn tồn tại ít nhất một số nguyên $j$ như vậy với mọi $i$ dưới các ràng buộc đã cho.

Dữ liệu vào

Dữ liệu vào gồm một bộ dữ liệu duy nhất theo định dạng sau.

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

Số nguyên $N$ là số đỉnh của cả $A$ và $B$ ($2 \le N \le 2 \times 10^5$).

$N - 1$ dòng tiếp theo mô tả các cạnh của $A$. Với mỗi $i = 1, \dots, N - 1$, hai số nguyên $u_i$ và $v_i$ ($1 \le u_i, v_i \le N$) có nghĩa là cạnh thứ $i$ nối hai đỉnh $u_i$ và $v_i$. Dữ liệu đảm bảo $A$ là một cây.

$N - 1$ dòng tiếp theo mô tả các cạnh của $B$. Với mỗi $j = 1, \dots, N - 1$, hai số nguyên $x_j$ và $y_j$ ($1 \le x_j, y_j \le N$) có nghĩa là cạnh thứ $j$ nối hai đỉnh $x_j$ và $y_j$. Dữ liệu đảm bảo $B$ là một cây.

Dữ liệu ra

In ra $N - 1$ dòng. Với mỗi $i = 1, 2, \dots, N - 1$, dòng thứ $i$ chứa một số nguyên $j$ thỏa mãn điều kiện trong đề bài đối với cạnh thứ $i$ của $A$.

Nếu có nhiều đáp án thỏa mãn, bạn có thể in ra bất kỳ đáp án nào.

Ví dụ

Dữ liệu vào 1

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

Dữ liệu ra 1

1
3
2

Ghi chú

Ở dòng đầu tiên của dữ liệu ra mẫu, $j = 1$ được chọn cho $i = 1$. Việc hoán đổi cạnh $(1, 3)$ của $A$ với cạnh $(1, 2)$ của $B$ giữ cho cả $A$ và $B$ đều là cây.

Với $i = 2$, cả cạnh của $A$ và cạnh được chọn của $B$ đều là $(2, 4)$, nên việc hoán đổi chúng không làm thay đổi cây nào. Các kết quả hợp lệ khác cũng được chấp nhận.