eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Розклад роботи

Розклад роботи

Ліміт часу 2 секунди
Ліміт використання пам'яті 256 MiB

Деяка кількість нічних охоронців захищає місцеве звалише від можливих небажаних пограбувань. Цих охоронців необхідно розбити на пари, так щоб кожна пара чергувала у різні ночі. Генеральний директор звалища попросив Вас написати програму, яка за заданими характеристиками охоронців визначає максимально необхідну їхню кілбкість (інші охоронці будуть звільнені). Відмітимо, що кожен охоронець може працювати лише з одним зі своїх колег, а також жоден з охоронців не може працювати один.

Вхідні дані

Перший рядок містить кількість нічних охоронців N222. Наступні рядки являють собою неупорядковані пари (i, j), кожна з яких позначає той факт, що охоронці i та j можуть працювати разом, оскільки можна знайти уніформу, яка підходить для їх обох (на звалищі використовується різна уніформа для різних охоронціов - шоломи, штани, куртки. Неможливо надіти маленький шолом на охоронця з великою головой або великі туфлі на охоронця з маленькими ногами). Вхідні дані завершуються кінцем файлу.

Вихідні дані

Вам потрібно вивести один з можливих оптимальних розподілів охоронців. У першому рядку слід вивести парне число C - кількість потрібних охоронців. Далі потрібно вивести C/2 рядків, кожен з яких містить 2 цілих числа (i, j), які вказують на те що охоронці i та j будуть працювати разом.

Приклад

Вхідні дані #1
3
1 2
2 3
1 3
Вихідні дані #1
2
1 2