Background

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.

The answers you submit are best named in order as:

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

Problem Description

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.

Input Format

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)$.

Output Format

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)$.

3 3 3
1 2
2 3
3 1

3
1 2 3

Hint

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:

Translated by ChatGPT 5