0387. Гонки

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

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

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

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

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

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

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

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

Пример:

Source: Petrozavodsk state university championship. October 2014.

Discuss       Submit a solution



Printable version