A. Приватизация
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Между Берляндией и Бирляндией существует развитая сеть авиарейсов. Все они являются собственностью берляндской государственной компании БерАвиа. Каждый рейс соединяет некоторый город Берляндии с некоторым городом Бирляндии. По каждому рейсу самолеты летают в обоих направлениях.

В Берляндии грядут перемены — принято решение приватизировать БерАвиа, а именно распродать все авиарейсы t частным авиакомпаниям. Каждая из этих компаний хочет заполучить максимальное количество авиарейсов, поэтому в случае неравномерной продажи авиарейсов компаниям Берляндия может быть обвинена в пристрастности. Решено распродать авиарейсы как можно более равномерно между t компаниями.

Неравномерность способа распределения рейсов по компаниям считается так. Для каждого города i (как Берляндии, так и Бирляндии) посчитаем величину

где aij — это количество рейсов из города i, которые принадлежат компании j. Сумма wi по всем городам в обеих странах называется неравномерностью способа. Способ с наименьшей неравномерностью — наиболее равномерный.

Помогите правительству Берляндии придумать план наиболее равномерного способа продажи авиарейсов.

Входные данные

В первой строке входных данных записано четыре целых числа n, m, k и t (1 ≤ n, m, t ≤ 200;1 ≤ k ≤ 5000), где n, m — количество городов в Берляндии и Бирляндии, соответственно, k — количество авиарейсов между ними, а t — количество частных компаний. Далее в k строках описаны авиарейсы по одному в строке парами натуральных чисел xi, yi (1 ≤ xi ≤ n;1 ≤ yi ≤ m), где xi и yi — номера городов в Берляндии и Бирляндии, соответственно, которые соединены i-ым рейсом. Между любой парой городов не более одного рейса, каждый рейс соединяет города разных стран. Города в Берляндии пронумерованы от 1 до n, а в Бирляндии — от 1 до m.

Выходные данные

В первую строку выведите неравномерность искомого способа. Во вторую строку выведите последовательность k целых чисел c1, c2, ..., ck (1 ≤ ci ≤ t), где ci — номер авиакомпании, которой следует продать i-ый авиарейс. Считайте, что авиарейсы пронумерованы от 1 до k в порядке появления во входных данных. Если решений несколько, выведите любое из них.

Примеры
Входные данные
3 5 8 2
1 4
1 3
3 3
1 2
1 1
2 1
1 5
2 2
Выходные данные
4
2 1 2 1 2 1 2 2