图划分

时间限制：10 s

空间限制：1024 MB

题目描述

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

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

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

本题只有一个测试点。

输入格式

输入的第一行包含四个整数 \(n,m,B,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. 块间边数量不超过 \(E\)。

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

样例输入

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

样例输出

1 1 1 2 2 2 3 3

样例解释

样例输出把点划分为三个块：

• 块 1：点 1, 2, 3；
• 块 2：点 4, 5, 6；
• 块 3：点 7, 8。

每个块的大小都不超过 3。块间边为 (3,4) 和 (6,7)，共 2 条，不超过 E = 2。

数据范围

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