АиСД. ПМИ2. 1 курс, 2 семестр

Задача G3. КПК ≡

задачи
видимые пробелы
простые формулы
широкий текст
редактор

Автор:	И. Олейников, Т. Чистяков	Ограничение времени:	2 сек
Входной файл:	input.txt	Ограничение памяти:	64 Мб
Выходной файл:	output.txt

Условие

Хакер Вася решил собрать карманный персональный компьютер (КПК). Согласно найденной им в Интернет инструкции компьютер собран правильно тогда, когда ток из каждой микросхемы может пройти в каждую и притом единственным путем.

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

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

Входной файл содержит числа N и M — соответственно число микросхем и проводов в КПК, за которыми следуют M пар чисел a_i a_j, означающие, что i-ая и j-ая микросхемы соединены проводом. Ток по проводу может течь в любом направлении.

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

Выходной файл содержит сначала число K₁ — количество проводов, которые нужно оставить в схеме, затем K₁ пар чисел a_i a_j — описание проводов. После этого следует число K₂ — число проводов, которые нужно добавить в схему, затем K₂ пар чисел a_i a_j — описание проводов. Если решений несколько, выведите любое из них.

Ограничения

1 ≤ N ≤ 1000, 0 ≤ M ≤ 10⁶

Примеры тестов

№	Входной файл (`input.txt`)	Выходной файл (`output.txt`)
1	`3 1 2 3`	`1 2 3 1 1 2`