0387. Гонки

Имя входного файла:	stdin
Имя выходного файла:	stdout
Ограничение по времени:	2 s
Ограничение по памяти:	256 megabytes

На Берляндском чемпионате по парным гонкам кипели нешуточные страсти. К финальному заезду накал страстей был таков, что компьютер жюри не выдержал и перегрелся. Теперь у жюри остались лишь перемешанные записи о том, какие пары участников встречались в одном заезде.

Чемпионат проходил по следующим правилам. К заезду допускаются два участника. Проигравший спортсмен выбывает из чемпионата и больше участвовать не может. Заезды проводятся до тех пор, пока есть более одного не выбывшего участника. Каждый заявленный спортсмен участвует хотя бы в одном заезде.

Чтобы опубликовать итоговую информацию о прошедшем чемпионате на своем сайте, жюри наняло вас, сотрудника <<БерляндПрограмминг>>, для восстановления истории заездов. Поскольку жюри понимает, что не во всех случаях можно однозначно восстановить историю, вас просят восстановить любую историю заездов, не противоречащую правилам, состоящую из оставшегося у жюри списка заездов, либо определить, что в предоставленные данные закралась ошибка.

Формат входного файла

В первой строке ввода задано два целых числа N и M (1 ≤ N, M ≤ 100000) – количество заездов и количество участников, соответственно. В следующих N строках задано два целых числа i и j (1 ≤ i, j ≤ M, i ≠ j) – номера участников в заезде.

Формат выходного файла

Выведите N строк по два целых числа в каждой – номера участников очередного заезда. Все пары чисел должны повторять список заездов из ввода. Порядок участников внутри пары может быть произвольным. Выведенный порядок заездов должен соответствовать правилам чемпионата. В случае, если существует несколько ответов, разрешается вывести любой из них.

Если восстановить историю заездов, не противоречащую правилам, по заданному списку невозможно, выведите фразу <<INVALID DATA>> без кавычек.

Пример:

стандартный поток ввода	стандартный поток вывода
3 4 1 2 1 4 3 4	1 2 3 4 1 4
3 4 1 2 1 3 1 4	1 4 2 1 3 1
5 6 2 1 2 3 4 5 5 6 4 6	INVALID DATA

Источник: Чемпионат ПетрГУ по программированию. Октябрь 2014.

Обсудить       Отправить решение