Aufgabenbeschreibung

Es gibt $N$ Bälle, die von $1$ bis $N$ nummeriert sind. Außerdem gibt es $N$ Kisten, in die beliebig viele Bälle passen, und die Kisten sind von $1$ bis $N$ nummeriert.

Anfangs befand sich in Kiste $i$ ($1 \le i \le N$) der Ball $i$.

Aoi, eine Schülerin der JOI-Oberschule, hat ausgehend von diesem Zustand $M$ Operationen an den Kisten und Bällen durchgeführt. Die $j$-te Operation ($1 \le j \le M$) wurde wie folgt durchgeführt:

• Suche die Kiste, in der sich Ball $X_j$ befindet, und nimm Ball $X_j$ aus dieser Kiste heraus. Lege anschließend Ball $X_j$ in Kiste $Y_j$.

Bestimme, in welcher Kiste sich jeder der $N$ Bälle befindet, nachdem Aoi alle $M$ Operationen beendet hat.

Einschränkungen

• $1 \le N \le 2000$.
• $1 \le M \le 2000$.
• $1 \le X_j \le N$ ($1 \le j \le M$).
• $1 \le Y_j \le N$ ($1 \le j \le M$).
• Alle Eingabewerte sind ganze Zahlen.

Eingabe

Die Eingabe erfolgt über die Standardeingabe im folgenden Format:

N M
X_1 Y_1
X_2 Y_2
:
X_M Y_M

Ausgabe

Gib $N$ Zeilen aus. Gib in der $i$-ten Zeile ($1 \le i \le N$) die Nummer der Kiste aus, in der sich Ball $i$ befindet, nachdem Aoi alle $M$ Operationen beendet hat.

Beispiele

Beispiel-Eingabe 1

3 4
1 2
3 2
2 1
1 3

Beispiel-Ausgabe 1

3
1
2

Anfangs befand sich in Kiste $1$ der Ball $1$, in Kiste $2$ der Ball $2$ und in Kiste $3$ der Ball $3$.

Aoi hat wie folgt $4$ Operationen durchgeführt:

• In der $1$. Operation nahm sie Ball $1$ aus Kiste $1$ und legte ihn in Kiste $2$.
• In der $2$. Operation nahm sie Ball $3$ aus Kiste $3$ und legte ihn in Kiste $2$.
• In der $3$. Operation nahm sie Ball $2$ aus Kiste $2$ und legte ihn in Kiste $1$.
• In der $4$. Operation nahm sie Ball $1$ aus Kiste $2$ und legte ihn in Kiste $3$.

Nach Abschluss aller Operationen befindet sich Ball $1$ in Kiste $3$, Ball $2$ in Kiste $1$ und Ball $3$ in Kiste $2$. Daher werden $3, 1, 2$ in dieser Reihenfolge durch Zeilenumbrüche getrennt ausgegeben.

Beispiel-Eingabe 2

3 3
1 1
2 2
3 3

Beispiel-Ausgabe 2

1
2
3

Nach Abschluss aller Operationen befindet sich Ball $1$ in Kiste $1$, Ball $2$ in Kiste $2$ und Ball $3$ in Kiste $3$. Daher werden $1, 2, 3$ in dieser Reihenfolge durch Zeilenumbrüche getrennt ausgegeben.

Beispiel-Eingabe 3

4 2
1 3
2 4

Beispiel-Ausgabe 3

3
4
3
4

Beispiel-Eingabe 4

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

Beispiel-Ausgabe 4

4
1
3
1