لديك شجرتان $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$.

يمكن إثبات أنه يوجد على الأقل عدد صحيح واحد $j$ يحقق الشرط لكل $i$ ضمن القيود المعطاة.

الإدخال

يتكون الإدخال من حالة اختبار واحدة بالتنسيق التالي.

$$ \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$ على عدد صحيح $j$ يحقق الشرط الوارد في نص المسألة للضلع ذي الترتيب $i$ من $A$.

إذا كانت هناك عدة إجابات ممكنة، فيمكنك طباعة أي منها.

أمثلة

الإدخال 1

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

الإخراج 1

1
3
2

ملاحظة

في السطر الأول من مخرجات المثال، تم اختيار $j = 1$ من أجل $i = 1$. إن تبادل الضلع $(1, 3)$ من $A$ مع الضلع $(1, 2)$ من $B$ يبقي كلاً من $A$ و $B$ شجرتين.

بالنسبة إلى $i = 2$، فإن كلاً من ضلع $A$ والضلع المختار من $B$ هو $(2, 4)$، لذا فإن تبادلهما لا يغير أياً من الشجرتين. توجد أيضاً مخرجات صحيحة أخرى ممكنة.