Lýsing á verkefni

Það eru $N$ boltar, númeraðir frá $1$ til $N$. Einnig eru $N$ kassar sem hver um sig getur rúmað hve marga bolta sem er, og kassarnir eru númeraðir frá $1$ til $N$.

Í upphafi var bolti $i$ í kassa $i$ ($1 \le i \le N$).

Aoi, nemandi í JOI-menntaskólanum, framkvæmdi $M$ aðgerðir á kassana og boltana út frá þessari stöðu. $j$-ta aðgerðin ($1 \le j \le M$) fór þannig fram:

• Finndu kassann sem inniheldur bolta $X_j$ og taktu bolta $X_j$ úr þeim kassa. Settu síðan bolta $X_j$ í kassa $Y_j$.

Eftir að Aoi hefur lokið öllum $M$ aðgerðunum, finndu í hvaða kassa hver af boltunum $N$ er.

Takmarkanir

• $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$).
• Öll inntaksgildi eru heiltölur.

Inntak

Inntakið er gefið úr staðalinntaki á eftirfarandi sniði:

N M
X_1 Y_1
X_2 Y_2
:
X_M Y_M

Úttak

Skrifið út $N$ línur. Á $i$-tu línu ($1 \le i \le N$) skal skrifa út númer kassans sem inniheldur bolta $i$ eftir að Aoi hefur lokið öllum $M$ aðgerðunum.

Dæmi

Sýnidæmi um inntak 1

3 4
1 2
3 2
2 1
1 3

Sýnidæmi um úttak 1

3
1
2

Í upphafi var bolti $1$ í kassa $1$, bolti $2$ í kassa $2$ og bolti $3$ í kassa $3$.

Aoi framkvæmdi $4$ aðgerðir á eftirfarandi hátt:

• Í $1$. aðgerðinni tók hún bolta $1$ úr kassa $1$ og setti hann í kassa $2$.
• Í $2$. aðgerðinni tók hún bolta $3$ úr kassa $3$ og setti hann í kassa $2$.
• Í $3$. aðgerðinni tók hún bolta $2$ úr kassa $2$ og setti hann í kassa $1$.
• Í $4$. aðgerðinni tók hún bolta $1$ úr kassa $2$ og setti hann í kassa $3$.

Eftir að öllum aðgerðunum er lokið er bolti $1$ í kassa $3$, bolti $2$ í kassa $1$ og bolti $3$ í kassa $2$. Því er skrifað út $3, 1, 2$ í þessari röð, aðskilið með línuskilum.

Sýnidæmi um inntak 2

3 3
1 1
2 2
3 3

Sýnidæmi um úttak 2

1
2
3

Eftir að öllum aðgerðunum er lokið er bolti $1$ í kassa $1$, bolti $2$ í kassa $2$ og bolti $3$ í kassa $3$. Því er skrifað út $1, 2, 3$ í þessari röð, aðskilið með línuskilum.

Sýnidæmi um inntak 3

4 2
1 3
2 4

Sýnidæmi um úttak 3

3
4
3
4

Sýnidæmi um inntak 4

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

Sýnidæmi um úttak 4

4
1
3
1