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

2132. Разбиение графа. Версия 2

Ограничение времени: 1.0 секунды
Ограничение памяти: 128 МБ
Дан обыкновенный граф с чётным количеством ребер. Требуется представить его в виде набора пар смежных (имеющих общую вершину) ребер.

Исходные данные

Входные данные содержат последовательность пар целых чисел. Длина последовательности чётная и лежит в пределах от 2 до 100000. Каждая пара чисел обозначает идентификаторы вершин одного ребра. Все идентификаторы вершин лежат в пределах от 1 до 100000. Граф не содержит петель и кратных рёбер.

Результат

Если требуемое разбиение существует, выведите в первой строке целое число m — количество пар смежных рёбер. Далее в m строках выведите тройки целых чисел a, b, c, обозначающих рёбра исходного графа {ab} и {bc}. Если разбиения графа не существует, выведите число -1.

Примеры

исходные данныерезультат
1 2
2 3
3 1
1 10
2
1 2 3
3 1 10
1 2
2 3
3 1
4 10
-1

Замечания

Это усложнённая версия задачи “Разбиение графа”.
Автор задачи: Александр Петров, подготовка — Александр Ипатов
Источник задачи: Контест "Лучше поздно, чем никогда"