For each connected friend group, choose a vertex with the largest number of direct friends in that group; break ties by smaller vertex number.

Input

The first line contains n and m. The next m lines contain friendships.

• 1 <= n <= 1000

Output

Print the selected leaders in increasing order.

Example

Input

10 6
4 3
4 1
8 5
8 6
4 2
8 2

Output

4 7 9 10