Du får gitt to trær, $A$ og $B$, hvert med $N$ noder. Begge trærne har den samme mengden av nummererte noder $\{1, 2, \dots, N\}$.

For hver $i$ ($1 \le i \le N - 1$) forbinder den $i$-te kanten i $A$ nodene $u_i$ og $v_i$. For hver $j$ ($1 \le j \le N - 1$) forbinder den $j$-te kanten i $B$ nodene $x_j$ og $y_j$.

Løs følgende problem for hver $i = 1, 2, \dots, N - 1$.

• Finn et heltall $j$ med $1 \le j \le N - 1$ slik at følgende bytte gjør at både $A$ og $B$ forblir trær:
  • Fjern kanten som forbinder $u_i$ og $v_i$ fra $A$, og fjern kanten som forbinder $x_j$ og $y_j$ fra $B$.
  • Legg deretter til en kant som forbinder $x_j$ og $y_j$ i $A$, og legg til en kant som forbinder $u_i$ og $v_i$ i $B$.

Hvert bytte betraktes uavhengig, med utgangspunkt i de opprinnelige trærne $A$ og $B$.

Det kan bevises at det finnes minst ett slikt heltall $j$ for hver $i$ under de gitte begrensningene.

Input

Inndataene består av ett enkelt testtilfelle på følgende format.

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

Heltallet $N$ er antallet noder i både $A$ og $B$ ($2 \le N \le 2 \times 10^5$).

De neste $N - 1$ linjene beskriver kantene i $A$. For hver $i = 1, \dots, N - 1$ betyr heltallene $u_i$ og $v_i$ ($1 \le u_i, v_i \le N$) at den $i$-te kanten forbinder nodene $u_i$ og $v_i$. Det er garantert at $A$ er et tre.

De neste $N - 1$ linjene beskriver kantene i $B$. For hver $j = 1, \dots, N - 1$ betyr heltallene $x_j$ og $y_j$ ($1 \le x_j, y_j \le N$) at den $j$-te kanten forbinder nodene $x_j$ og $y_j$. Det er garantert at $B$ er et tre.

Output

Skriv ut $N - 1$ linjer. For hver $i = 1, 2, \dots, N - 1$ skal den $i$-te linjen inneholde et heltall $j$ som oppfyller betingelsen i oppgaveteksten for den $i$-te kanten i $A$.

Hvis det finnes flere mulige svar, kan du skrive ut hvilket som helst av dem.

Examples

Input 1

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

Output 1

1
3
2

Note

På den første linjen i eksempelutskriften er $j = 1$ valgt for $i = 1$. Å bytte kanten $(1, 3)$ i $A$ med kanten $(1, 2)$ i $B$ lar både $A$ og $B$ forbli trær.

For $i = 2$ er både kanten i $A$ og den valgte kanten i $B$ lik $(2, 4)$, så det å bytte dem endrer ingen av trærne. Andre gyldige utskrifter er også mulige.