On vous donne deux arbres, $A$ et $B$, ayant chacun $N$ sommets. Les deux arbres possèdent le même ensemble de sommets numérotés $\{1, 2, \dots, N\}$.

Pour chaque $i$ ($1 \le i \le N - 1$), la $i$-ème arête de $A$ relie les sommets $u_i$ et $v_i$. Pour chaque $j$ ($1 \le j \le N - 1$), la $j$-ème arête de $B$ relie les sommets $x_j$ et $y_j$.

Pour chaque $i = 1, 2, \dots, N - 1$, résolvez le problème suivant.

• Trouvez un entier $j$ tel que $1 \le j \le N - 1$ et que l'échange suivant laisse $A$ et $B$ tous deux sous forme d'arbres :
  • Retirer de $A$ l'arête reliant $u_i$ et $v_i$, et retirer de $B$ l'arête reliant $x_j$ et $y_j$.
  • Ensuite, ajouter à $A$ une arête reliant $x_j$ et $y_j$, et ajouter à $B$ une arête reliant $u_i$ et $v_i$.

Chaque échange est considéré indépendamment, en repartant des arbres initiaux $A$ et $B$.

On peut prouver qu'il existe au moins un tel entier $j$ pour chaque $i$ sous les contraintes données.

Entrée

L'entrée consiste en un seul cas de test au format suivant.

$$ \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'entier $N$ est le nombre de sommets de $A$ et de $B$ ($2 \le N \le 2 \times 10^5$).

Les $N - 1$ lignes suivantes décrivent les arêtes de $A$. Pour chaque $i = 1, \dots, N - 1$, les entiers $u_i$ et $v_i$ ($1 \le u_i, v_i \le N$) signifient que la $i$-ème arête relie les sommets $u_i$ et $v_i$. Il est garanti que $A$ est un arbre.

Les $N - 1$ lignes suivantes décrivent les arêtes de $B$. Pour chaque $j = 1, \dots, N - 1$, les entiers $x_j$ et $y_j$ ($1 \le x_j, y_j \le N$) signifient que la $j$-ème arête relie les sommets $x_j$ et $y_j$. Il est garanti que $B$ est un arbre.

Sortie

Affichez $N - 1$ lignes. Pour chaque $i = 1, 2, \dots, N - 1$, la $i$-ème ligne doit contenir un entier $j$ satisfaisant la condition de l'énoncé pour la $i$-ème arête de $A$.

S'il existe plusieurs réponses possibles, vous pouvez afficher n'importe laquelle d'entre elles.

Exemples

Entrée 1

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

Sortie 1

1
3
2

Remarque

Dans la première ligne de la sortie d'exemple, $j = 1$ est choisi pour $i = 1$. Échanger l'arête $(1, 3)$ de $A$ avec l'arête $(1, 2)$ de $B$ laisse $A$ et $B$ tous deux sous forme d'arbres.

Pour $i = 2$, l'arête de $A$ et l'arête sélectionnée de $B$ sont toutes deux $(2, 4)$, donc les échanger ne modifie aucun des deux arbres. D'autres sorties valides sont également possibles.