CF212A.Privatization

There is a developed network of flights between Berland and Beerland. All of them belong to the Berland state company BerAvia. Each flight connects some Berland city with some Beerland city. For each flight airplanes fly in both directions.

Changes are coming to Berland — the state decided to privatize BerAvia, namely, to sell out all flights to t private companies. Each of these companies wants to get the maximal number of flights, so if the Berland flights are sold unevenly, Berland can be accused of partiality. Berland Government decided to sell the flights as evenly as possible between the t companies.

The unevenness of the distribution of flights between companies is calculated as follows. For each city i (both Berland and Beerland) we'll calculate the value of

where a__ij is the number of flights from city i, which belong to company j. The sum of w__i for all cities in both countries is called the unevenness of the distribution. The distribution with the minimal unevenness is the most even one.

Help the Berland government come up with the most even distribution plan of selling flights.

贝兰国与比尔兰国之间已建成一张发达的航班网络。所有航班均隶属于贝兰国国有航空公司“贝航公司”（BerAvia）。每条航班连接一个贝兰国城市与一个比尔兰国城市，且飞机在两个方向上均运行。

变革即将降临贝兰国——政府决定对贝航公司实行私有化，即把全部航班出售给 $t$ 家私营公司。每家私营公司都希望获得尽可能多的航班；因此，若航班分配不均，贝兰国政府可能被指控存在偏袒行为。为此，贝兰国政府决定将航班尽可能均匀地分配给这 $t$ 家公司。

航班在各公司之间的分配不均衡度定义如下：对每个城市 $i$（包括贝兰国和比尔兰国的所有城市），计算如下数值：

其中 $a_{ij}$ 表示从城市 $i$ 出发、归属第 $j$ 家公司的航班数量。所有城市（两国合计）的 $w_i$ 之和即为该分配方案的不均衡度。不均衡度最小的分配方案即为最均匀的分配方案。

请帮助贝兰国政府制定出使航班分配最均匀的销售方案。

The first input line contains four integers n, m, k and t (1 ≤ n, m, t ≤ 200;1 ≤ k ≤ 5000), where n, m are the numbers of cities in Berland and Beerland, correspondingly, k is the number of flights between them, and t is the number of private companies. Next k lines describe the flights, one per line, as pairs of positive integers x__i, y__i (1 ≤ x__i ≤ n;1 ≤ y__i ≤ m), where x__i and y__i are the indexes of cities in Berland and Beerland, correspondingly, connected by the i-th flight. There is at most one flight between any pair of cities, each flight connects cities of different countries. The cities in Berland are indexed from 1 to n, and in Beerland — from 1 to m.

第一行输入包含四个整数 $n$、$m$、$k$ 和 $t$（$1 \leq n, m, t \leq 200$；$1 \leq k \leq 5000$），其中 $n$、$m$ 分别表示 Berland 国和 Beerland 国的城市数量，$k$ 表示两国之间的航班总数，$t$ 表示私营航空公司的数量。接下来的 $k$ 行每行描述一个航班，格式为一对正整数 $x_i,\ y_i$（$1 \leq x_i \leq n$；$1 \leq y_i \leq m$），其中 $x_i$ 和 $y_i$ 分别表示第 $i$ 个航班所连接的 Berland 国和 Beerland 国的城市编号。任意两个城市之间至多存在一条航班，且每条航班均连接不同国家的城市。Berland 国的城市编号为 $1$ 至 $n$，Beerland 国的城市编号为 $1$ 至 $m$。

Print the unevenness of the sought plan on the first line. On the second line print a sequence of k integers _c_1, _c_2, ..., c__k (1 ≤ c__i ≤ t), where c__i is the index of the company that should buy the i-th flight. Assume that the flights are indexed from 1 to k in the order they appear in the input. If there are multiple solutions, print any of them.

在第一行输出所求方案的不均衡度。
在第二行输出一个由 $k$ 个整数 $c_1,\,c_2,\,\dots,\,c_k$（其中 $1\le c_i\le t$）组成的序列，其中 $c_i$ 表示应购买第 $i$ 个航班的公司编号。假设航班按其在输入中出现的顺序从 $1$ 到 $k$ 编号。若存在多个解，输出任意一个即可。