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