题目描述

在 Olympia 有一个环形村庄，共有 N 座房子，按顺时针方向编号为 1..N。所有房子都位于同一个圆周上。

村庄内部有 M 条街道，每条街道连接两座不同的房子。保证：

• 任意两座房子之间至多有一条街道；
• 任意两条街道不会相交，但可以共用端点。

节日将至，村民们想给房子上色。若某条街道的两个端点房子颜色相同，则这条街道被称为坏街道。村民希望不存在坏街道，并且使用的颜色数尽可能少。

请你编写程序，求出最少需要多少种颜色，并给出一种合法染色方案。

输入格式

第一行两个整数 N, M，分别表示房子数和街道数。

接下来 M 行，每行两个整数 u, v，表示房子 u 与房子 v 之间有一条街道。

输出格式

第一行输出一个整数 K，表示最少需要的颜色数。

第二行输出 N 个整数，第 i 个整数表示第 i 座房子的颜色，颜色编号需在 1..K 之间。

如果有多种最优方案，输出任意一种即可。

数据范围

• 2 <= N <= 5 × 10^5
• 1 <= M <= 5 × 10^5

子任务

样例

输入

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

输出

2
1 2 1 2 1 2