Между Берляндией и Бирляндией существует развитая сеть авиарейсов. Все они являются собственностью берляндской государственной компании БерАвиа. Каждый рейс соединяет некоторый город Берляндии с некоторым городом Бирляндии. По каждому рейсу самолеты летают в обоих направлениях.
В Берляндии грядут перемены — принято решение приватизировать БерАвиа, а именно распродать все авиарейсы t частным авиакомпаниям. Каждая из этих компаний хочет заполучить максимальное количество авиарейсов, поэтому в случае неравномерной продажи авиарейсов компаниям Берляндия может быть обвинена в пристрастности. Решено распродать авиарейсы как можно более равномерно между t компаниями.
Неравномерность способа распределения рейсов по компаниям считается так. Для каждого города i (как Берляндии, так и Бирляндии) посчитаем величину
Помогите правительству Берляндии придумать план наиболее равномерного способа продажи авиарейсов.
В первой строке входных данных записано четыре целых числа 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
