P6865 [RC-03] 染色

提示：输入文件很大，因此下载可能较慢（约需 3 分钟），请耐心等待。 **本题为提交答案题。** 输入数据请在[这里](http://119.27.163.117/images/files/input.zip)下载。 你提交的答案**最好**依次命名为： - 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)$

对于每个测试点： - 若你的输出不合法，你将得到 $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$ 的方案。以下是每个测试点的分值： | 测试点编号 | 分值 | | :----------: | :----------: | | $1\sim 4$ | $4$ | | $5\sim 6$ | $5$ | | $7\sim 17$ | $6$ | | $18$ | $8$ |