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