ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

1156. Два тура

Ограничение времени: 2.0 секунды
Ограничение памяти: 64 МБ
Чемпионат Урала состоит из двух туров, на каждом из которых участникам предлагается для решения 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 г., английский тур.