Ti vengono dati due alberi, $A$ e $B$, ciascuno con $N$ vertici. Entrambi gli alberi hanno lo stesso insieme di vertici etichettati $\{1, 2, \dots, N\}$.

Per ogni $i$ ($1 \le i \le N - 1$), l'$i$-esimo arco di $A$ collega i vertici $u_i$ e $v_i$. Per ogni $j$ ($1 \le j \le N - 1$), il $j$-esimo arco di $B$ collega i vertici $x_j$ e $y_j$.

Per ogni $i = 1, 2, \dots, N - 1$, risolvi il seguente problema.

• Trova un intero $j$ con $1 \le j \le N - 1$ tale che il seguente scambio lasci sia $A$ che $B$ degli alberi:
  • Rimuovere da $A$ l'arco che collega $u_i$ e $v_i$, e rimuovere da $B$ l'arco che collega $x_j$ e $y_j$.
  • Successivamente, aggiungere ad $A$ un arco che collega $x_j$ e $y_j$, e aggiungere a $B$ un arco che collega $u_i$ e $v_i$.

Ogni scambio è considerato indipendentemente, partendo dagli alberi originali $A$ e $B$.

Si può dimostrare che esiste almeno un tale intero $j$ per ogni $i$ sotto i vincoli dati.

Input

L'input è costituito da un singolo caso di test nel seguente formato.

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

L'intero $N$ è il numero di vertici sia di $A$ che di $B$ ($2 \le N \le 2 \times 10^5$).

Le successive $N - 1$ righe descrivono gli archi di $A$. Per ogni $i = 1, \dots, N - 1$, gli interi $u_i$ e $v_i$ ($1 \le u_i, v_i \le N$) indicano che l'$i$-esimo arco collega i vertici $u_i$ e $v_i$. È garantito che $A$ è un albero.

Le successive $N - 1$ righe descrivono gli archi di $B$. Per ogni $j = 1, \dots, N - 1$, gli interi $x_j$ e $y_j$ ($1 \le x_j, y_j \le N$) indicano che il $j$-esimo arco collega i vertici $x_j$ e $y_j$. È garantito che $B$ è un albero.

Output

Stampa $N - 1$ righe. Per ogni $i = 1, 2, \dots, N - 1$, l'$i$-esima riga deve contenere un intero $j$ che soddisfa la condizione nel testo del problema per l'$i$-esimo arco di $A$.

Se esistono più risposte possibili, puoi stamparne una qualsiasi.

Examples

Input 1

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

Output 1

1
3
2

Note

Nella prima riga dell'output di esempio, viene scelto $j = 1$ per $i = 1$. Scambiando l'arco $(1, 3)$ di $A$ con l'arco $(1, 2)$ di $B$, sia $A$ che $B$ rimangono alberi.

Per $i = 2$, sia l'arco di $A$ che l'arco selezionato di $B$ sono $(2, 4)$, quindi scambiarli non modifica nessuno dei due alberi. Sono possibili anche altri output validi.