Комитет общественного порядка
Комитет общественного порядка должен быть законодательно представлен в парламенте Демократической Республики Байтляндии согласно Очень Важному Закону. К сожалению, одним из препятствий является то, что некоторые депутаты не могут никак договориться с другими.
Комитет должен удовлетворять следующим условиям:
Каждая партия имеет в точности одного представителя в комитете,
Если два депутата не нравятся друг другу, они не могут войти в комитет.
Каждая партия имеет в точности двух депутатов в Парламенте. Все они пронумерованы от 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 в возрастающем порядке, указывающих номера депутатов, из которых и будет состоять комитет. Каждое из этих чисел следует вывести в отдельной строке. Если комитет можно организовать несколькими вариантами, то следует вывести наименьшую последовательность чисел.