Descrizione del problema

Ci sono $N$ palline, numerate da $1$ a $N$. Ci sono anche $N$ scatole, ciascuna delle quali può contenere un numero qualsiasi di palline, e le scatole sono numerate da $1$ a $N$.

Inizialmente, la scatola $i$ ($1 \le i \le N$) conteneva la pallina $i$.

Aoi, una studentessa della scuola superiore JOI, ha effettuato $M$ operazioni sulle scatole e sulle palline a partire da questo stato. La $j$-esima operazione ($1 \le j \le M$) è stata eseguita come segue:

• Trova la scatola che contiene la pallina $X_j$ e togli la pallina $X_j$ da quella scatola. Successivamente, metti la pallina $X_j$ nella scatola $Y_j$.

Dopo che Aoi ha terminato tutte le $M$ operazioni, determina in quale scatola si trova ciascuna delle $N$ palline.

Vincoli

• $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$).
• Tutti i valori di input sono numeri interi.

Dati di input

L'input viene fornito dallo standard input nel seguente formato:

N M
X_1 Y_1
X_2 Y_2
:
X_M Y_M

Dati di output

Stampa $N$ righe. Sulla $i$-esima riga ($1 \le i \le N$), stampa il numero della scatola che contiene la pallina $i$ dopo che Aoi ha completato tutte le $M$ operazioni.

Esempi di input/output

Input di esempio 1

3 4
1 2
3 2
2 1
1 3

Output di esempio 1

3
1
2

Inizialmente, la scatola $1$ conteneva la pallina $1$, la scatola $2$ conteneva la pallina $2$ e la scatola $3$ conteneva la pallina $3$.

Aoi ha eseguito $4$ operazioni come segue:

• Nella $1$ª operazione, ha tolto la pallina $1$ dalla scatola $1$ e l'ha messa nella scatola $2$.
• Nella $2$ª operazione, ha tolto la pallina $3$ dalla scatola $3$ e l'ha messa nella scatola $2$.
• Nella $3$ª operazione, ha tolto la pallina $2$ dalla scatola $2$ e l'ha messa nella scatola $1$.
• Nella $4$ª operazione, ha tolto la pallina $1$ dalla scatola $2$ e l'ha messa nella scatola $3$.

Al termine di tutte le operazioni, la pallina $1$ si trova nella scatola $3$, la pallina $2$ nella scatola $1$ e la pallina $3$ nella scatola $2$. Pertanto, si stampa $3, 1, 2$ in quest'ordine, separati da a capo.

Input di esempio 2

3 3
1 1
2 2
3 3

Output di esempio 2

1
2
3

Al termine di tutte le operazioni, la pallina $1$ si trova nella scatola $1$, la pallina $2$ nella scatola $2$ e la pallina $3$ nella scatola $3$. Pertanto, si stampa $1, 2, 3$ in quest'ordine, separati da a capo.

Input di esempio 3

4 2
1 3
2 4

Output di esempio 3

3
4
3
4

Input di esempio 4

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

Output di esempio 4

4
1
3
1