נתונים שני עצים, $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$ כעצים:
  • הסירו מ-$A$ את הקשת המחברת את $u_i$ ו-$v_i$, והסירו מ-$B$ את הקשת המחברת את $x_j$ ו-$y_j$.
  • לאחר מכן, הוסיפו ל-$A$ קשת המחברת את $x_j$ ו-$y_j$, והוסיפו ל-$B$ קשת המחברת את $u_i$ ו-$v_i$.

כל החלפה נבחנת באופן בלתי תלוי, החל מהעצים המקוריים $A$ ו-$B$.

ניתן להוכיח שתחת האילוצים הנתונים קיים לפחות מספר שלם $j$ אחד כזה עבור כל $i$.

Input

הקלט מורכב ממקרה בדיקה יחיד בפורמט הבא.

$$ \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$ הוא עץ.

Output

הדפיסו $N - 1$ שורות. עבור כל $i = 1, 2, \dots, N - 1$, השורה ה-$i$ צריכה להכיל מספר שלם $j$ המקיים את התנאי שבתיאור הבעיה עבור הקשת ה-$i$ של $A$.

אם יש מספר תשובות אפשריות, ניתן להדפיס כל אחת מהן.

Examples

Input 1

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

Output 1

1
3
2

Note

בשורה הראשונה של פלט הדוגמה, נבחר $j = 1$ עבור $i = 1$. החלפת הקשת $(1, 3)$ של $A$ עם הקשת $(1, 2)$ של $B$ משאירה הן את $A$ והן את $B$ כעצים.

עבור $i = 2$, גם הקשת של $A$ וגם הקשת שנבחרה מ-$B$ הן $(2, 4)$, ולכן החלפתן אינה משנה אף אחד מהעצים. קיימים גם פלטים חוקיים אחרים.