Problem Description

There are $ N $ balls numbered from $ 1 $ to $ N $. Also, there are $ N $ boxes that can contain any number of balls, and these boxes are numbered from $ 1 $ to $ $ N $.

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

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

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

Determine which box each of the $ N $ balls is in after Aoi completed all $ M $ operations.

Input Format

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

$ N $ $ M $ $ X_1 $ $ Y_1 $ $ X_2 $ $ Y_2 $ $\vdots$ $ X_M $ $ Y_M $

Output Format

Output $ N $ lines. The $ i $-th line ($1 \leq i \leq N$) should contain the number of the box that ball $ i $ is in after all $ M $ operations are completed.

Sample Input and Output

Sample Input #1

3 4
1 2
3 2
2 1
1 3

Sample Output #1

3
1
2

Sample Input #2

3 3
1 1
2 2
3 3

Sample Output #2

1
2
3

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

Notes/Hints

Constraints

• $1 \leq N \leq 2,000$.
• $1 \leq M \leq 2,000$.
• $1 \leq X_j \leq N$ ($1 \leq j \leq M$).
• $1 \leq Y_j \leq N$ ($1 \leq j \leq M$).
• All values given in the input are integers.

Sample Explanation 1

Initially, box $ 1 $ contained ball $ 1 $, box $ 2 $ contained ball $ 2 $, and box $ 3 $ contained ball $ 3 $. Aoi performed the following $ 4 $ operations:
- In the 1st operation, ball $ 1 $ was removed from box $ 1 $ and placed into box $ 2 $.
- In the 2nd operation, ball $ 3 $ was removed from box $ 3 $ and placed into box $ 2 $.
- In the 3rd operation, ball $ 2 $ was removed from box $ 2 $ and placed into box $ 1 $.
- In the 4th operation, ball $ 1 $ was removed from box $ 2 $ and placed into box $ 3 $.

After 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, each on a new line.

Sample Explanation 2

After 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, each on a new line.

见题面 Input 部分

见题面 Output 部分