P6865 [RC-03] Coloring

Note: The input file is very large, so downloading may be slow (about 3 minutes). Please wait patiently. **This is an output-only problem.** Please download the input data from [here](http://119.27.163.117/images/files/input.zip). The answers you submit are **best** named in order as: - 01.out - 02.out - $\dots$ - 18.out

Given an undirected graph, find a $k$ as small as possible such that the vertices can be divided into $k$ sets, and there is no edge between any two vertices in the same set.

The first line contains three integers: $n,m,k_0$, meaning there are $n$ vertices and $m$ edges. As long as your $k$ satisfies $k\le k_0$, you can get full score. The next $m$ lines each contain two integers $x,y$, describing an edge $(x,y)$. $(1\le x,y\le n,x\ne y)$.

Two lines. The first line contains an integer $k$, your answer. $(1\le k\le n)$. The second line contains $n$ integers. The $i$-th integer indicates the set number $a_i$ that vertex $i$ is assigned to. $(1\le a_i\le k)$.

For each test point: - If your output is invalid, you will get $0$ points. - If $k\le k_0$, you will get full score. - Otherwise, you will get (suppose the full score of this test point is $a$): $\lfloor a \times \dfrac{k_0}{k}\rfloor$ points. There are $18$ test points in total. All test points satisfy $1\le n\le 10^5$, $1\le m\le 5\times 10^5$, and it is guaranteed that there exists a solution with $k\le k_0$. The scores for each test point are as follows: | Test Point ID | Score | | :----------: | :----------: | | $1\sim 4$ | $4$ | | $5\sim 6$ | $5$ | | $7\sim 17$ | $6$ | | $18$ | $8$ | Translated by ChatGPT 5