图划分

时间限制：10 s

空间限制：1024 MB

题目描述

给定一张无向图。你需要把图中的每个点划分到若干个块中，使得：

1. 每个点恰好属于一个块；
2. 每个块中的点数不超过 \(B\)；
3. 块数不超过 \(C\);
4. 块间边数量不超过 \(E\)。
   

一条边的两个端点如果属于不同的块，则称这条边为一条块间边。

本题只有一个测试点，并将下发测试数据。

输入格式

输入的第一行包含四个整数 \(n,m,B,C,E\)

分别代表图的点数，边数，每块最大点数以及最大块间边数。

接下来 \(m\) 行，每行两个整数 \(u,v\)，表示一条无向边。

输出格式

输出 \(n\) 个正整数：

\(c_1,c_2 ...,c_n\)

其中 \(c_i\) 表示点 \(i\) 所属的块编号。

块编号不要求连续。只要两个点的编号相同，就表示它们在同一块；编号不同，就表示它们在不同块。

如果你的输出满足以下条件，则判定为通过：

1. 恰好输出 \(n\) 个正整数；
2. \( 1 \leq c_i \leq 10^{9}\);
3. 任意一个块的大小都不超过 \(B\)；
4. 块总数不超过 \(C\);
5. 块间边数量不超过 \(E\)。

注意：不要求每个块在图中连通。

样例输入

8 7 3 3 2
1 2
2 3
3 4
4 5
5 6
6 7
7 8

样例输出

1 1 1 2 2 2 3 3

测试数据

点击下载

数据范围

对于 100% 的数据，
\(n = 264346\)
\(m = 365050\)
\(B = 2000\)
\(C = 300\)
\(E = 11000\)
本题使用 Special Judge 判定输出是否合法。