题目背景

提示：输入文件很大，因此下载可能较慢（约需 3 分钟），请耐心等待。

本题为提交答案题。 输入数据请在这里下载。

你提交的答案最好依次命名为：

• 01.out
• 02.out
• $\dots$
• 18.out

题目描述

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

输入格式

第一行三个整数：$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)$

输出格式

两行，第一行为一个整数 $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

提示

对于每个测试点：

• 若你的输出不合法，你将得到 $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$ 的方案。以下是每个测试点的分值：