Énoncé du problème

Il y a $N$ balles, numérotées de $1$ à $N$. Il y a également $N$ boîtes pouvant contenir un nombre quelconque de balles, et ces boîtes sont numérotées de $1$ à $N$.

Initialement, la boîte $i$ ($1 \le i \le N$) contenait la balle $i$.

Aoi, une élève du lycée JOI, a effectué $M$ opérations sur les boîtes et les balles à partir de cet état. La $j$-ème opération ($1 \le j \le M$) s'est déroulée comme suit :

• Chercher la boîte contenant la balle $X_j$, et retirer la balle $X_j$ de cette boîte. Ensuite, placer la balle $X_j$ dans la boîte $Y_j$.

Une fois qu'Aoi a terminé toutes les $M$ opérations, déterminez dans quelle boîte se trouve chacune des $N$ balles.

Contraintes

• $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$).
• Toutes les valeurs d'entrée sont des entiers.

Entrée

L'entrée est fournie depuis l'entrée standard sous le format suivant :

N M
X_1 Y_1
X_2 Y_2
:
X_M Y_M

Sortie

Affichez $N$ lignes. Sur la $i$-ème ligne ($1 \le i \le N$), affichez le numéro de la boîte contenant la balle $i$ après qu'Aoi a terminé les $M$ opérations.

Exemples d'entrée/sortie

Exemple d'entrée 1

3 4
1 2
3 2
2 1
1 3

Exemple de sortie 1

3
1
2

Initialement, la boîte $1$ contenait la balle $1$, la boîte $2$ contenait la balle $2$ et la boîte $3$ contenait la balle $3$.

Aoi a effectué $4$ opérations comme suit :

• Lors de la $1$-re opération, elle a retiré la balle $1$ de la boîte $1$, puis l'a mise dans la boîte $2$.
• Lors de la $2$-e opération, elle a retiré la balle $3$ de la boîte $3$, puis l'a mise dans la boîte $2$.
• Lors de la $3$-e opération, elle a retiré la balle $2$ de la boîte $2$, puis l'a mise dans la boîte $1$.
• Lors de la $4$-e opération, elle a retiré la balle $1$ de la boîte $2$, puis l'a mise dans la boîte $3$.

Une fois toutes les opérations terminées, la balle $1$ est dans la boîte $3$, la balle $2$ est dans la boîte $1$ et la balle $3$ est dans la boîte $2$. On affiche donc $3, 1, 2$ dans cet ordre, séparés par des sauts de ligne.

Exemple d'entrée 2

3 3
1 1
2 2
3 3

Exemple de sortie 2

1
2
3

Une fois toutes les opérations terminées, la balle $1$ est dans la boîte $1$, la balle $2$ est dans la boîte $2$ et la balle $3$ est dans la boîte $3$. On affiche donc $1, 2, 3$ dans cet ordre, séparés par des sauts de ligne.

Exemple d'entrée 3

4 2
1 3
2 4

Exemple de sortie 3

3
4
3
4

Exemple d'entrée 4

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

Exemple de sortie 4

4
1
3
1