← 返回题目列表

Codeforces · 212/A

A. 私有化

中文机器翻译题面 查看原题

Berland 和 Beerland 之间有发达的航班网络。它们全部属于柏林国营公司 BerAvia。每个航班将贝尔兰的一些城市与贝尔兰的一些城市连接起来。对于每次飞行,飞机都会向两个方向飞行。

Berland正在发生变化——国家决定将BerAvia私有化,即将所有航班出售给私营公司。这些公司都希望获得最大数量的航班,因此如果 Berland 的航班销售不均,则 Berland 可能会被指责为偏袒。伯兰州政府决定在各航空公司之间尽可能平均地出售航班。

公司之间航班分布的不均匀性计算如下。对于每个城市 i(Berland 和 Beerland),我们将计算

$${ w } _ { i } = \operatorname* { m a x } _ { j } a _ { i j } - \operatorname* { m i n } _ { j } a _ { i j },$$

帮助柏林政府制定最均匀的航班销售分配方案。

输入

第一输入行包含四个整数 n、m、k 和 t (1 ≤ n, m, t ≤ 200;1 ≤ k ≤ 5000),其中 n、m 是 Berland 和 Beerland 的城市数量,相应地,k 是它们之间的航班数量,t 是私营公司的数量。接下来的 k 行描述航班,每行一个,作为正整数对 xi, yi (1 ≤ xi ≤ n;1 ≤ yi ≤ m),其中 xi 和 yi 是 Berland 和 Beerland 的城市索引,相应地,由第 i 个航班连接。任意一对城市之间最多有一个航班,每个航班连接不同国家的城市。 Berland 的城市索引从 1 到 n,Beerland 的城市索引从 1 到 m。

输出

在第一行打印所需计划的不平整度。在第二行打印 k 个整数 c1, c2, ..., ck (1 ≤ ci ≤ t) 的序列,其中 ci 是应该购买第 i 个航班的公司的索引。假设航班按照它们在输入中出现的顺序从 1 到 k 进行索引。如果有多个解决方案,请打印其中任何一个。

示例

输入 #1

3 5 8 2
1 4
1 3
3 3
1 2
1 1
2 1
1 5
2 2

输出 #1

4
2 1 2 1 2 1 2 2