Problembeskrivning

Det finns $N$ bollar, numrerade från $1$ till $N$. Det finns också $N$ lådor som var och en rymmer hur många bollar som helst, och lådorna är numrerade från $1$ till $N$.

Från början låg boll $i$ i låda $i$ ($1 \le i \le N$).

Aoi, en elev på JOI-gymnasiet, utförde utifrån detta tillstånd $M$ operationer på lådorna och bollarna. Den $j$-te operationen ($1 \le j \le M$) utfördes enligt följande:

• Hitta lådan som innehåller boll $X_j$ och ta ut boll $X_j$ ur den lådan. Lägg därefter boll $X_j$ i låda $Y_j$.

Bestäm i vilken låda var och en av de $N$ bollarna ligger efter att Aoi har avslutat alla $M$ operationer.

Begränsningar

• $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$).
• Alla indatavärden är heltal.

Indata

Indatan ges från standardindata i följande format:

N M
X_1 Y_1
X_2 Y_2
:
X_M Y_M

Utdata

Skriv ut $N$ rader. På den $i$-te raden ($1 \le i \le N$), skriv ut numret på lådan som innehåller boll $i$ efter att Aoi har avslutat alla $M$ operationer.

Exempel

Indataexempel 1

3 4
1 2
3 2
2 1
1 3

Utdataexempel 1

3
1
2

Från början låg boll $1$ i låda $1$, boll $2$ i låda $2$ och boll $3$ i låda $3$.

Aoi utförde $4$ operationer enligt följande:

• I den $1$:a operationen tog hon ut boll $1$ ur låda $1$ och lade den i låda $2$.
• I den $2$:a operationen tog hon ut boll $3$ ur låda $3$ och lade den i låda $2$.
• I den $3$:e operationen tog hon ut boll $2$ ur låda $2$ och lade den i låda $1$.
• I den $4$:e operationen tog hon ut boll $1$ ur låda $2$ och lade den i låda $3$.

Efter att alla operationer har avslutats ligger boll $1$ i låda $3$, boll $2$ i låda $1$ och boll $3$ i låda $2$. Därför skrivs $3, 1, 2$ ut i denna ordning, åtskilda av radbrytningar.

Indataexempel 2

3 3
1 1
2 2
3 3

Utdataexempel 2

1
2
3

Efter att alla operationer har avslutats ligger boll $1$ i låda $1$, boll $2$ i låda $2$ och boll $3$ i låda $3$. Därför skrivs $1, 2, 3$ ut i denna ordning, åtskilda av radbrytningar.

Indataexempel 3

4 2
1 3
2 4

Utdataexempel 3

3
4
3
4

Indataexempel 4

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

Utdataexempel 4

4
1
3
1