Get Final Locations

Initially there are n distinct data positions. In input order, move the data at position from to position to; it is guaranteed that from currently holds data and to currently does not. Output all final positions in ascending order.

输入格式

The first line contains n m, the second line the initial positions, followed by m lines from to. This site uses 1≤n≤100000, 0≤m≤100000, positions 0..10^9.

输出格式

Output the n final positions in strictly ascending order, separated by spaces.

样例 1

输入：

2 2
1 3
1 2
2 4

输出：

3 4

样例 2

输入：

2 0
2 5

输出：

2 5

样例 3

输入：

1 2
0
0 10
10 0

输出：

0

样例说明

The answers are 3 4, 2 5 and 0; the third example shows that data may move back to a position that was vacated.