Mán lì

There are $N$ participants at 插入编程竞赛 which need to be accommodated in a hotel with $N$ available rooms.

Among these participants there are exactly $M$ friendships. If two participants are friends, then they can be assigned to the same room. Otherwise, they must be assigned to different rooms.

Task

Find the lexicographically minimum assignment of the $N$ participants to the $N$ available rooms of the hotel. We can show that such an assignment always exists.

An assignment $A_1,A_2,\ldots,A_N$ is lexicographically smaller than another assignment $B_1,B_2,\ldots, B_N$ if there exists a position $1 \le i \le N$ for which:

• $A_j=B_j$, for all $1 \le j<i$.
• $A_i<B_i$.

Here, $A_i$ denotes the number of the room assigned to the $i$-th participant in the first assignment. Similarly, $B_i$ denotes the number of the room assigned to the $i$-th participant in the second assignment.

Input data

The first line of input containts integers $N$ and $M$ - the number of participants, and the number of friendships, respectively.

Each of the next $M$ lines of input contains two integers $U_i$ and $V_i$ ($1 \le U_i, V_i \le N$, $U_i \neq V_i$), meaning that participants $U_i$ and $V_i$ are friends. Note that this relationship is bidirectional.

Output data

Print the lexicographically minimum assignment $A_1,A_2,\ldots,A_N$ ($1 \le A_i \le N$ for all $i$). We can show that such an assignment always exists.

Constraints and clarifications

• $1 \leq N \leq 300 \ 000$
• $0 \leq M \leq \min \left(\frac{n(n-1)}{2}, 300 \ 000 \right)$
• $1 \leq U_i, V_i \leq N$, $U_i \neq V_i$ for all $1 \leq i \leq M$
• It is guaranteed that all friendships given in the input are pairwise distinct.

Example 1

stdin

6 4
1 4
1 5
3 5
6 2

stdout

1 2 3 1 3 2

Explanation

Participant $1$ is assigned to room $1$.

Participant $2$ is assigned to room $2$.

Participant $3$ is assigned to room $3$.

Participant $4$ is assigned to room $1$.

Participant $5$ is assigned to room $3$.

Participant $6$ is assigned to room $2$.

For example, since participants $1$ and $4$ are friends, they can be assigned to the same room.

We can show that, under the given constratints, this is the lexicographically minimum assignment.

Example 2

stdin

4 6
1 2
1 3
1 4
2 3
2 4
3 4

stdout

1 1 1 1

Explanation

Here, all of the participants are friends with each other. Therefore, they can all be assigned to room $1$.