Гоблинский банк "Гринготтс" по праву считается одним из самых надёжных банков в мире волшебников. Он находится в сотнях километров под Лондоном, и охраняется мощными заклинаниями и драконами. А знаете ли вы, как был построен этот банк? Гоблины ведь не такие дураки, как гномы — они не станут копать многокилометровые подземные ходы киркой и лопатой. Как они проложили все туннели без лопат и кирок? Очень просто: чтобы прорыть туннель, гоблины с помощью магии вызывали гипервяка. Гипервяк — это нечто вроде большущей змеи мощностью более тысячи мегачервей. Двигаясь, он поедает всё, что находится на его пути, оставляя за собой удобный, ровный и прочный коридор. Гипервяком легко управлять с помощью магии, заставляя его рыть туннели в нужном направлении.

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

К сожалению, министру магии попала в руки полная схема туннелей между помещениями банка. Он хочет потребовать штраф за каждый прорытый туннель. Гоблины, конечно, могут заявить, что если два туннеля приходят в одну комнату, то они обошлись всего одним гипервяком для прокладывания обоих туннелей, проведя гипервяка по краю комнаты. И вообще, для любой цепочки туннелей, где конечная комната очередного туннеля совпадает с начальной комнатой следующего, хватит одного гипервяка. Но, разумеется, никто не поверит, что гоблины перетаскивали гипервяка из одного помещения в другое, а расширять существующие туннели они не могли из соображений безопасности.

Помогите гоблинам представить министру магии такой план рытья туннелей, при котором погибло бы минимальное количество гипервяков.

В первой стоке входа находятся числа N и M (2 ≤ N ≤ 20000; 1 ≤ M ≤ 20000) — количество помещений банка и туннелей между помещениями. В следующих M строках указаны пары чисел (каждое число от 1 до N) — номера помещений, которые соединяет очередной туннель. От каждого помещения банка можно добраться до другого, пользуясь только прогрызенными гипервяками туннелями.

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