Gegeben sind zwei Bäume $A$ und $B$ mit jeweils $N$ Knoten. Beide Bäume haben dieselbe beschriftete Knotenmenge $\{1, 2, \dots, N\}$.

Für jedes $i$ ($1 \le i \le N - 1$) verbindet die $i$-te Kante von $A$ die Knoten $u_i$ und $v_i$. Für jedes $j$ ($1 \le j \le N - 1$) verbindet die $j$-te Kante von $B$ die Knoten $x_j$ und $y_j$.

Löse für jedes $i = 1, 2, \dots, N - 1$ das folgende Problem.

• Finde eine ganze Zahl $j$ mit $1 \le j \le N - 1$, sodass nach dem folgenden Tausch sowohl $A$ als auch $B$ weiterhin Bäume sind:
  • Entferne die Kante zwischen $u_i$ und $v_i$ aus $A$ und entferne die Kante zwischen $x_j$ und $y_j$ aus $B$.
  • Füge anschließend eine Kante zwischen $x_j$ und $y_j$ zu $A$ hinzu und füge eine Kante zwischen $u_i$ und $v_i$ zu $B$ hinzu.

Jeder Tausch wird unabhängig betrachtet, ausgehend von den ursprünglichen Bäumen $A$ und $B$.

Es lässt sich beweisen, dass unter den gegebenen Bedingungen für jedes $i$ mindestens eine solche ganze Zahl $j$ existiert.

Eingabe

Die Eingabe besteht aus einem einzigen Testfall im folgenden 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} $$

Die ganze Zahl $N$ ist die Anzahl der Knoten von $A$ und $B$ ($2 \le N \le 2 \times 10^5$).

Die folgenden $N - 1$ Zeilen beschreiben die Kanten von $A$. Für jedes $i = 1, \dots, N - 1$ bedeuten die ganzen Zahlen $u_i$ und $v_i$ ($1 \le u_i, v_i \le N$), dass die $i$-te Kante die Knoten $u_i$ und $v_i$ verbindet. Es wird garantiert, dass $A$ ein Baum ist.

Die nächsten $N - 1$ Zeilen beschreiben die Kanten von $B$. Für jedes $j = 1, \dots, N - 1$ bedeuten die ganzen Zahlen $x_j$ und $y_j$ ($1 \le x_j, y_j \le N$), dass die $j$-te Kante die Knoten $x_j$ und $y_j$ verbindet. Es wird garantiert, dass $B$ ein Baum ist.

Ausgabe

Gib $N - 1$ Zeilen aus. Für jedes $i = 1, 2, \dots, N - 1$ soll die $i$-te Zeile eine ganze Zahl $j$ enthalten, die die Bedingung in der Aufgabenstellung für die $i$-te Kante von $A$ erfüllt.

Falls es mehrere mögliche Antworten gibt, kannst du eine beliebige davon ausgeben.

Beispiele

Eingabe 1

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

Ausgabe 1

1
3
2

Hinweis

In der ersten Zeile der Beispielausgabe wurde $j = 1$ für $i = 1$ gewählt. Der Tausch der Kante $(1, 3)$ von $A$ mit der Kante $(1, 2)$ von $B$ belässt sowohl $A$ als auch $B$ als Bäume.

Für $i = 2$ sind sowohl die Kante von $A$ als auch die gewählte Kante von $B$ gleich $(2, 4)$, sodass ihr Tausch keinen der beiden Bäume verändert. Andere gültige Ausgaben sind ebenfalls möglich.