Privatization

题意翻译

Berland 和 Beerland 之间有发达的航班网络，它们都属于 Berland 国营公司 BerAvia。每条航线将 Berland 的一个城市和 Beerland 的一个城市连接起来。 最近，Berland 决定私有化 BerAvia，他们将航线卖给了 $k$ 家私人公司。这些公司希望航线的划分尽量均匀。 具体地，对每个城市 $i$，定义不均匀度 $$w_i=\max_j a_{i,j}-\min_j a_{i,j}$$ 其中，$a_{i,j}$ 代表公司 $j$ 拥有的经过 $i$ 市的航线数量。 Berland 政府希望不均匀度的平均值最小，请帮助它们找到最佳方案，并输出不均匀度的和。

题目描述

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.

输入输出格式

输入格式

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 $ .

输出格式

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.

输入输出样例

输入样例 #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