Комітет громадського порядку
Комітет громадського порядку повинен бути законодавчо представленим у парламенті Демократичної Республіки Байтляндії згідно Дуже Важливому Закону. На жаль, однією з перепон є те, що деякі депутати не можуть ніяк домовитись з іншими.
Комітет повинен задовольняти наступним умовам:
Кожна партія має у точності одного представника у комітеті,
Якщо два депутати не подобаються один одному, вони не можуть увійти до комітету.
Кожна партія має у точності двох депутатів у Парламенті. Усі вони пронумеровані від 1 до 2n. Депутати під номерами 2i-1 та 2i належать i-ій партії.
Напишіть програму, яка:
прочитає кількість партій та число пар депутатів, які знаходяться не в дружніх відносинах,
визначить, чи можна організувати комітет. У випадку позитивної відповіді потрібно вказати список цого членів,
виведе результат.
Вхідні дані
Перший рядок містить два невід'ємних цілих числа n та m: відповідно кількість партій n (1 ≤ n ≤ 8000) та число пар депутатів m (0 ≤ m ≤ 20000), які не подобаються один одному. Кожен з настпних m рядків містить два цілих числа a та b, 1 ≤ a < b ≤ 2n, відокремлених одним пропуском. Такий рядок означає, що депутати a та b не подобаються один одному.
Вхідні дані містять декілька тестів. Вхідні дані потрібно опрацьовувати до кінця файлу.
Вихідні дані
Вивести одне слово NIE (означає НІ польською мовою), якщо організувати комітет неможливо. У протилежному випадку потрібно вивести n цілих чисел з інтервалу від 1 до 2n у зростаючому порядку, які вказують номери депутатів, з яких і буде складатись комітет. Кожне з цих чисел потрібно вивести у окремому рядку. Якщо комітет можна організувати декількома варіантами, то потрібно вивести найменшу послідовність чисел.