Problem Description

Cats like to swap seats, Rar the cat is no exception. In Rar the cat's class, cats swap seats so often that even teachers get confused about the identity of the cats.

As such, Rar's teacher has requested that you make a program to monitor who is in which seat.

For convenience, the chairs are numbered from 0 to n-1 and each cat is also numbered from 0 to n-1 as well.

At the start of the class, the cat numbered i will be in the chair numbered i, where i can be any number between 0 and n-1 inclusive.

When 2 cats swap seats, Rar's teacher takes notes of the chair numbers for the 2 seats involved.

Input

The first line consists of a single integer, n, which refers to both the number of cats and the number of chairs. n will be always not more than 10000.

The second line consists of s, the number of times 2 cats swapped seats. s will always be not more than 10000 as well.

The following s line consists of 2 integers each, which are the chair numbers of the 2 seats involved in the swap. The 2 numbers will never be the same.

Output

Output will consist of n lines. On the first line, output the cat number of the cat sitting in chair 0. On the ith line, output the cat number of the cat sitting in chair (i-1)th line.

Sample Input

8
5
2 4
0 1
3 7
4 2
3 5

Sample Output

1
0
2
5
4
7
6
3

Explanation for Output

Initial:

0 1 2 3 4 5 6 7

After the 1st swap:

0 1 4 3 2 5 6 7
[Seat 2(Cat 2) and Seat 4(Cat 4) swapped]

After the 2nd swap:

1 0 4 3 2 5 6 7
[Seat 0(Cat 0) and Seat 1(Cat 1) swapped]

After the 3rd swap:

1 0 4 7 2 5 6 3
[Seat 3(Cat 3) and Seat 7(Cat 7) swapped]

After the 4th swap:

1 0 2 7 4 5 6 3
[Seat 4(Cat 2) and Seat 2(Cat 4) swapped]

After the 5th swap:

1 0 2 5 4 7 6 3
[Seat 3(Cat 7) and Seat 5(Cat 5) swapped]