Чемпионат Урала состоит из двух туров, на каждом из которых участникам предлагается для решения N задач. Титанические усилия жюри позволили в кратчайшие сроки подготовить 2N задач. Но затем оказалось, что среди них оказались задачи со схожими алгоритмами решения, которые нельзя предлагать в одном туре. Помогите жюри составить наборы задач для каждого тура.
Исходные данные
В первой строке даны 2 числа: N, количество задач на туре, и M, количество пар задач, которые недопустимо давать на одном туре (1 ≤ N ≤ 50; 0 ≤ M ≤ 100). Далее следуют M строк по 2 числа в каждой — номера схожих задач.
Результат
Выведите 2 строки, в каждой по N чисел — номера задач на каждый тур. Если решения нет, выведите «IMPOSSIBLE». Если задача имеет несколько решений, можно вывести любое.
Пример
исходные данные | результат |
---|
2 3
1 3
2 1
4 3
| 1 4
2 3
|
Автор задачи: Евгений Брызгалов
Источник задачи: Командный чемпионат Урала по программированию. Пермь, апрель 2001 г., английский тур.