Description

给一个无向图，求尽量小的 $k$，使得能够把节点分为 $k$ 个集合，且同一集合的点间没有边。

Input Format

第一行三个整数：$n,m,k_0$，表示有 $n$ 个点，$m$ 条边，你的 $k$ 只要满足 $k\le k_0$ 就能得到满分。

接下来 $m$ 行，每行两个数 $x,y$，描述一条边 $(x,y)$。$(1\le x,y\le n,x\ne y)$

Output Format

两行，第一行为一个整数 $k$，为你的答案。$(1\le k\le n)$

第二行 $n$ 个整数，第 $i$ 个表示 $i$ 被分到的集合编号 $a_i$。$(1\le a_i\le k)$

3 3 3
1 2
2 3
3 1

3
1 2 3

Hint

对于每个测试点：

• 若你的输出不合法，你将得到 $0$ 分。
• 若 $k\le k_0$，你将得到满分。
• 否则你将得到（设该测试点满分为 $a$）：$\lfloor a \times \dfrac{k_0}{k}\rfloor$ 分。

本题共有 $18$ 个测试点，所有测试点均满足 $1\le n\le 10^5$，$1\le m\le 5\times 10^5$，且保证存在一种满足 $k\le k_0$ 的方案。以下是每个测试点的分值：