johnie

В далечна страна живеел Джони Уокър, човек, който наистина обичал разходките. В страната има  N града (номерирани от 1 до N), като между някои двойки градове има алеи за пешеходци. Джони иска да обиколи всички алеи и решил да направи едно голямо пътешествие, разделено на няколко етапа. Във всеки етап Джони тръгва от някой град, прави някаква обиколка по алеите и пристига в някой град. Една обиколка представлява последователност от градове, такава че между всеки два последователни града има алея. При своето пътешествие Джони иска да премине по всяка от алеите само веднъж. Не е проблем, ако минава през някой от градовете два или повече пъти, дори и в рамките на един етап.

Задача

По дадени броя на градовете и алеите между тях, определете минималния брой етапи, за които Джони може да премине по всички алеи. Да се посочи и начин за обхождането на алеите с минимален брой етапи.

Вход

На първия ред на входния файл  johnie.in  са записани две положителни цели числа, разделени с интервал: N, представляващо броя на градовете и M, представляващо броя на алеите. Всеки от следващите M реда съдържа две различни цели положителни числа i j (от 1 до N), което означава, че има алея между градовете с номера i и j.

Изход

Изходният файл johnie.out  трябва да съдържа на първия ред едно цяло положително число min, представляващо минималния брой етапи, за които могат да се обиколят всички алеи. Следващите min реда представят обиколките, които Джони извършва на всеки етап. Първото число в реда е броя на посетените градове, а следващите числа – самите градове по реда на тяхното посещаване. Числата във всеки ред са разделени с интервали.

Ограничения

1 <= N <= 50000
1 <= M <= 100000
Възможно е да има повече от една алея между два града.
Алеите са двупосочни.
Няма алея, която започва и завършва в един и същ град.

Пример

johnie.in

johnie.out

7 7
1 2
1 3
1 4
2 3
3 5
4 5
6 7

2
7 1 4 5 3 2 1 3
2 6 7

Ограничение за време: 0.5 секунди на тест

Daniel Pasaila
"Al. I Cuza" University, Iaşi - IT Department
danielpasaila@yahoo.com

Превод на български: Стоян Капралов