Cloud Bridge 2

Interview

Time limit1sMemory limit1024 MB

Summary

Color each building so adjacent buildings differ, and among all valid colorings output the one whose color sequence is lexicographically smallest.

Level: Medium5 of 10
Topics: Graph, Greedy, BFS, Hash map
Solved: No attempts yet

Problem

Sunlin Internet High School has several buildings and cloud bridges that connect them.

Specifically, there are $N$ buildings numbered $1$ through $N$ , and $M$ cloud bridges, each connecting two distinct buildings.

Jeonghwi, the winner of the 2019 Cheonhajeil Environmental Landscape Design Contest, felt that the colors of the school buildings were too monotonous and that school life was too boring.

So Jeonghwi hired Chaewan, the 2021 winner, to repaint the outer walls of the school buildings. Specifically, Jeonghwi required that the outer walls of the $N$ buildings be painted according to the following conditions.

A color is represented by a positive integer.
Each building is painted with exactly one color.
Two buildings connected by a cloud bridge are painted with different colors.
When the colors of buildings $1$ through $N$ are listed in order, the sequence is lexicographically smallest.

Tell Chaewan which color to paint the outer wall of each building.

Input

The first line gives $N$ and $M$ , the number of buildings and the number of cloud bridges.

From the second line, $M$ lines follow, each giving the numbers of two distinct buildings connected by a cloud bridge.

Output

Print the color of each building from building $1$ to building $N$ , separated by spaces, on one line.

Constraints

$1 \leq N \leq 100\,000$
$0\leq M \leq 100\,000$
A cloud bridge connects two distinct buildings.

Examples2

Example 1
Input
```
5 1
1 2
```
Expected output
```
1 2 1 1 1
```
Example 2
Input
```
3 3
1 2
1 3
2 3
```
Expected output
```
1 2 3
```