makethemmeet
Day2 Tasks

European Girls'
Olympiad in Informatics
21 – 27 July 2024
The Netherlands

Ukrainian (UKR)

D. Нехай вони зустрінуться!
Назва задачіmakethemmeetОбмеження часу9сОбмеження використання пам'яті1024 МБДар'я та Каріна вже давно дружать онлайн; вони ніколи не зустрічалися в реальному житті.
Зараз вони обидві перебувають на одному заході в офлайн-форматі, що означає, що вони точно
зустрінуться. Однак готель, де вони обидві зупинилися, дуже великий і заплутаний. Тому, післякількох днів, вони досі не натрапили одна на одну.
Готель складається з N кімнат, пронумерованих від 0 до N − 1. У кожній кімнаті є лампа, якаможе світитись різними кольорами. Ви знайшли в готелі перемикач, за допомогою якого у вас єзмога змінювати кольори цих ламп. Ваша мета — направити Дар'ю та Каріну за допомогою ламп,щоб зрештою вони все ж зустрілись.
Готель можна представити, як граф, що містить N вершин (кімнати) і M ребер (коридори, щоз'єднують кімнати). Дар'я і Каріна спочатку знаходяться в двох різних кімнатах, але ви не знаєтев яких саме. Ви можете зробити кілька ходів. Кожен хід складається з виведення списку з Nцілих чисел c0 , c1 , ..., cN −1 , що означає, що колір лампи в кімнаті з номером i стає рівним ci длявсіх i = 0, 1, ..., N − 1. Після цього кожна з дівчат подивиться на колір лампи в кімнаті, в якійвона перебуває, і піде у сусідню кімнату (кімнату, що з'єднана коридором з поточною), де лампамає такий самий колір. Якщо такої сусідньої кімнати немає, тоді відповідна дівчина рухатись небуде. Якщо ж існуватиме кілька підходящих сусідніх кімнат, тоді відповідна дівчина вибере однуз них довільним чином.
Якщо Дар'я та Каріна коли-небудь опиняться в одній кімнаті, або використовуватимуть один ітой самий коридор одночасно, то вважатиметься, що ви досягли успіху в їх зустрічі. Ви можетезробити не більше 20 000 ходів, але ви отримаєте вищий бал, якщо використаєте менше ходів.
Зверніть увагу, що ви не знаєте, в яких кімнатах початково перебувають дівчата і як вонипересуваються, якщо у них під час ходу є кілька кімнат одного кольору на вибір. Ваше рішеннямає бути правильним незалежно від їхніх початкових кімнат та способу пересування.

Формат вхідних даних

makethemmeet (1 of 4)У першому рядку задано два цілі числа N та M — кількість кімнат та кількість коридорів у готелівідповідно.
У наступних M рядках задано по два цілі числа ui and vi — номери кімнат, які з'єднує
відповідний коридор.

Формат вихідних данихУ першому рядку виведіть одне ціле число K — кількість ходів.
У наспуних K рядках виведіть по N цілих чисел c0 , c1 , ..., cN −1 , таких що 0 ≤ ci ≤ N для всіх i —кольори ламп для відповідного ходу. Ці K рядків представляють ваші ходи у хронологічномупорядку.

Обмеження та оцінювання2 ≤ N ≤ 100.
N − 1 ≤ M ≤ N (N2−1) .
0 ≤ ui , vi ≤ N − 1, та ui ≠ vi .
Можливо дістатися до будь-якої кімнати з будь-якої іншої кімнати. Крім того, немаєкоридорів, які ведуть з кімнати до самої себе, і між будь-якою парою кімнат існує не більшеодного коридору.
Ви можете використати не більше, ніж 20 000 ходів (тому K ≤ 20 000).
Ваше рішення буде протестоване на наборі груп, кожна з яких оцінюється в певну кількість балів.
Кожна група містить певний набір тестів. Щоб отримати бали за певну групу, вам необхідно
вирішити всі тести цієї групи.

ГрупаМаксимальний
бал

110213311436

M = N − 1. Іншими словами, граф є деревом.

530

Без додаткових обмежень.

ОбмеженняM = N − 1, та коридорами є (0, 1), (0, 2), (0, 3), ..., (0, N − 1).
Іншими словами, граф є зіркою.

M = N (N2−1) , тобто існує коридор між кожною парою кімнат.
Іншими словами, граф є повним.

M = N − 1, та коридорами є (0, 1), (1, 2), (2, 3), ..., (N − 2, N − 1).
Іншими словами, граф є бамбуком.

За кожну групу тестів, яку ваша програма вирішить правильно, ви отримаєте оцінку на основінаступної формули:makethemmeet (2 of 4)1score = ⌊Sg ⋅ min (1, Kg2000+1900 + 5 )⌋ ,де Sg — максимальний бал для групи тестів, а Kg — максимальна кількість ходів, яку вашерішення використало для будь-якого з тестів групи. Це означає, що для отримання повного балувам потрібно використати не більше, ніж 600 ходів у кожному з тестів. Графік нижче показуєкількість балів як функцію від Kg .

Приклад
Приклад є бамбуком довжиною 3, тому він може належати до груп 3, 4 або 5. Якщо лампивмикаються відповідно до наведеного виводу, то Дар'я і Каріна завжди зустрінуться.
Наприклад, нехай Дар'я починає з вершини 0, а Каріна — з вершини 1:Перший хід: Дар'я повинна перейти до вершини 1. Якщо Каріна перейде до вершини 0, товони зустрінуться на ребрі між 0 і 1. Припустимо, що Каріна переходить до вершини 2.
Другий хід: Дар'я повертається до вершини 0, а Каріна залишається у вершині 2.
Третій хід: Дар'я знову переходить до вершини 1, а Каріна залишається у вершині 2.
Четвертий хід: Дар'я переходить до вершини 2, а Каріна переходить до вершини 1. Такимчином, вони зустрінуться у коридорі між вершинами 1 і 2.
П’ятий хід: Дар'я і Каріна міняються місцями і знову зустрічаються (але це не важливо,оскільки вони вже зустрілися).
Нижче наведена ілюстрація перших чотирьох ходів прикладу.

makethemmeet (3 of 4)Зверніть увагу, що тут було розглянуто лише випадок, коли подруги початково знаходяться укімнатах 0 і 1. Можна перевірити, що та ж сама послідовність ходів гарантує, що вонизустрінуться, незалежно від того, звідки вони починають і як саме рухаються, коли в них є кількаваріантів для пересування.
ВвідВивід

3 2

50 11 22 2 22 2 32 2 3
1 2 2
1 2 2

makethemmeet (4 of 4)