Задача D. КПК

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

Условие

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

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

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

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

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

Выходной файл содержит сначала число K1 — количество проводов, которые нужно оставить в схеме, затем K1 пар чисел ai aj — описание проводов. После этого следует число K2 — число проводов, которые нужно добавить в схему, затем K2 пар чисел ai aj — описание проводов. Если решений несколько, выведите любое из них.

Ограничения

1 ≤ N ≤ 1000, 0 ≤ M ≤ 106

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

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

0.035s 0.008s 15