Друзі та вороги#2476
На острові Ґенту живе крокодилів. У кожного крокодила є рівно один друг і один ворог серед інших крокодилів. Взаємини симетричні: якщо крокодил є другом крокодила , то і є другом ; аналогічно, якщо є ворогом , то і — ворог . Жоден крокодил не може бути одночасно і другом, і ворогом для іншого крокодила, а також не може бути своїм власним другом або ворогом.
Крокодили дуже емоційні. Коли зустрічаються два вороги, вони люто грюкають хвостами об землю, влаштовуючи Крокодилячий Бій. Коли зустрічаються двоє друзів, вони виконують танець дружби крокодилів.
Нещодавно ці танці й бої розбудили вулкан під островом, через що його роз’єднало на дві частини. Хоча вулкан заспокоївся, крокодили бояться, що подальші танці або бої можуть знову його розбудити, затопивши обидві частини острова лавою.
Тепер крокодили бажають оселитися на двох частинах острова так, щоб у кожній частині була нейтральна група крокодилів — тобто жодна пара крокодилів у групі не повинна бути друзями чи ворогами. Таким чином, вони сподіваються уникнути танців і бійок і запобігти новому виверженню вулкана.
Крокодили острова Ґенту мудрі, але непрактичні. Вони знають, що для їхніх дружніх та ворожих зв'язків завжди можливо розділити себе на дві нейтральні групи, проте не знають, як це зробити.
Допоможіть їм! Знайдіть спосіб розділити крокодилів на дві групи так, щоб у жодній групі не було крокодилів, які є друзями чи ворогами.
Перший рядок містить натуральне число — кількість крокодилів (4 \leq n \leq 100). Наступні рядків описують крокодилів. Перший рядок містить два числа f_1 і e_1, розділених пробілом — друга та ворога першого крокодила. Другий рядок містить f_2 і e_2 — друга та ворога другого крокодила, і так далі. Останній рядок містить f_n і e_n — друга та ворога -го крокодила. Крокодили нумеруються з до у порядку появи у вхідних даних.
Усі числа f_k та e_k — це цілі числа від до включно. Взаємини дружби та ворожнечі симетричні. Друг і ворог кожного крокодила — різні крокодили. Жоден крокодил не може бути своїм другом чи ворогом.
У першому рядку виведіть чисел, розділених пробілами. Кожне число має бути або . Якщо -те і -те числа однакові, то крокодили і знаходяться на одній половині острова. Якщо різні — то на різних.
Якщо існує декілька правильних відповідей, дозволяється вивести будь-яку з них.
Приклад 1