Galaxy Interconnection
Более 1000 лет прошло с момента первого ACM ICPC. Несколько цивилизаций нашей Галактики, включая Землю, объединились в Великий Круг, где они обмениваются научной и культурной информацией. Из-за распределения гравитации и потоков темной энергии в галактике существуют двунаправленные каналы связи между некоторыми планетами. Через эти каналы цивилизации могут распространять знания по всему Великому Кругу.
Сейчас настало время распределить исследования между цивилизациями: каждая планета должна выбрать одну из k основных областей исследований (например, Репагулярное Исчисление или Теория Данного Строка).
Выбор k не был случайным. Великий Круг начался с Начального Круга — набора из k планет, которые были соединены каналами, образующими цикл. Позже были исследованы и построены новые каналы, и новые планеты были подключены к Великому Кругу. Однако из-за высокой энергетической стоимости каналов связи каждая планета Великого Круга имеет строго меньше k каналов.
Две планеты, соединенные прямым каналом, не должны выбирать одну и ту же область исследований: лучше выбрать разные и делиться результатами исследований.
Есть еще одно ограничение. Периодически цивилизации отправляют космические экспедиции для исследования новых планет и посещения соседей из Великого Круга. Экспедиции планируются так, чтобы космические корабли могли летать с одной планеты на другую, если эти планеты соединены каналом связи. Это помогает подготовить экспедицию: построить станции дозаправки, оптимизировать системы связи корабля и т.д.
Некоторые экспедиции, так называемые Аудиты Исследований, планируются таким образом, что космический корабль стартует с какой-то планеты, затем совершает k − 1 прыжков, посещая всего k планет (включая исходную). Эти k планет вместе должны предоставить все k областей исследований: экспедиция проверит прогресс исследований.
Ваша задача — выбрать одну область исследований для каждой планеты таким образом, чтобы: - не было двух планет, соединенных каналом связи, с одной и той же областью исследований; - была возможность отправить Аудит Исследований с каждой планеты Великого Круга.
Входные данные
Первая строка входного файла содержит три целых числа: n, k и m — количество планет в Великом Круге, количество областей исследований и количество каналов связи соответственно (3 ≤ n ≤ 5000; 3 ≤ k ≤ min(n,10); 1 ≤ m ≤ 10000).
Следующие m строк описывают каналы, по одному на строку. Канал связи описывается двумя целыми числами — идентификаторами планет, которые он соединяет. Планеты идентифицируются целыми числами от 1 до n таким образом, что планеты от 1 до k образуют Начальный Цикл.
Выходные данные
Выведите ровно n целых чисел в одной строке, i-е целое число должно идентифицировать область исследований для планеты i (целое число от 1 до k).