Description

There are $N$ balls, numbered from $1$ to $N$. There are also $N$ boxes, each of which can hold any number of balls, and the boxes are numbered from $1$ to $N$.

Initially, box $i$ ($1 \le i \le N$) contained ball $i$.

Aoi, a student at JOI High School, performed $M$ operations on the boxes and balls starting from this state. The $j$-th operation ($1 \le j \le M$) was performed as follows:

• Find the box containing ball $X_j$, and remove ball $X_j$ from that box. Then, put ball $X_j$ into box $Y_j$.

After Aoi finishes all $M$ operations, find which box each of the $N$ balls is in.

Constraints

• $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$).
• All input values are integers.

Input

The input is given from standard input in the following format:

N M
X_1 Y_1
X_2 Y_2
:
X_M Y_M

Output

Output $N$ lines. On the $i$-th line ($1 \le i \le N$), output the number of the box containing ball $i$ after Aoi finishes all $M$ operations.

Sample I/O

Sample Input 1

3 4
1 2
3 2
2 1
1 3

Sample Output 1

3
1
2

Initially, box $1$ contained ball $1$, box $2$ contained ball $2$, and box $3$ contained ball $3$.

Aoi performed $4$ operations as follows:

• In the $1$-st operation, she removed ball $1$ from box $1$ and then put it into box $2$.
• In the $2$-nd operation, she removed ball $3$ from box $3$ and then put it into box $2$.
• In the $3$-rd operation, she removed ball $2$ from box $2$ and then put it into box $1$.
• In the $4$-th operation, she removed ball $1$ from box $2$ and then put it into box $3$.

After finishing all operations, ball $1$ is in box $3$, ball $2$ is in box $1$, and ball $3$ is in box $2$. Therefore, output $3, 1, 2$ in this order, separated by newlines.

Sample Input 2

3 3
1 1
2 2
3 3

Sample Output 2

1
2
3

After finishing all operations, ball $1$ is in box $1$, ball $2$ is in box $2$, and ball $3$ is in box $3$. Therefore, output $1, 2, 3$ in this order, separated by newlines.

Sample Input 3

4 2
1 3
2 4

Sample Output 3

3
4
3
4

Sample Input 4

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

Sample Output 4

4
1
3
1