Галактичне з'єднання#2376
Пройшло понад років з часу проведення першого ACM ICPC. Декілька цивілізацій нашої Галактики, включаючи Землю, об'єдналися у Велике Коло, учасники якого обмінюються науковою та культурною інформацією. Через розподіл гравітації та потоків темної енергії в галактиці між деякими планетами існують двонаправлені канали зв'язку. Через ці канали цивілізації можуть обмінюватися знаннями по всьому Великому Колу.
Настав час розподілити дослідження між цивілізаціями: кожна планета має вибрати один із основних напрямків наукової діяльності (наприклад, репагулярне числення чи теорію заданого рядка).
Вибір саме був не випадковим. Велике Коло починалося з Початкового Кола — множини з планет, з'єднаних каналами, що утворюють цикл. Згодом були досліджені й побудовані нові канали, а до Великого Кола приєдналися нові планети. Однак через значну енерговитратність каналів зв'язку кожна планета у Великому Колі має строго менше ніж каналів.
Дві планети, з'єднані безпосереднім каналом, не повинні обирати один і той самий напрямок досліджень: краще, щоб вони займалися різними напрямками й ділилися результатами одна з одною.
Є ще одне обмеження. Періодично цивілізації споряджають космічні експедиції для дослідження нових планет і візитів до сусідів у Великому Колі. Такі експедиції планують так, щоб кораблі могли рухатися від однієї планети до іншої, якщо між цими планетами є канал зв'язку. Це допомагає готувати експедиції: будувати заправні станції, оптимізувати комунікаційні системи кораблів тощо.
Деякі експедиції, які називаються Науковими Аудитами, планують так, що корабель стартує з якоїсь планети, потім здійснює k - 1 переходів, відвідуючи загалом планет (включаючи початкову). Ці планет разом повинні представляти всі дослідницьких напрямків: експедиція перевірятиме прогрес досліджень.
Ваше завдання — вибрати напрямок досліджень для кожної планети так, щоб виконувались такі умови: - Жодні дві планети, з'єднані каналом зв'язку, не мають однакового напрямку досліджень; - З кожної планети Великого Кола можна розпочати експедицію Наукового Аудиту.
У першому рядку містяться три цілі числа: , і — кількість планет у Великому Колі, кількість дослідницьких напрямків та кількість каналів зв'язку (3 \le n \le 5000; 3 \le k \le \min(n, 10); 1 \le m \le 10000).
У наступних рядках описуються канали, по одному в рядку. Кожен канал зв'язку описується двома цілими числами — номерами планет, які він з'єднує. Планети пронумеровані від до , причому планети, пронумеровані від до , утворюють Початковий Цикл.
Виведіть рівно цілих чисел в одному рядку. -те число повинно позначати дослідницький напрямок для -тої планети (ціле число від до ).
Приклад 1