Gringotts bank is run by goblins and is rightfully considered one of the most reliable banks in the wizard world. Its underground vaults are located hundreds of kilometres below London and are guarded by powerful spells and dragons. Goblins created the complicated system of vaults and tunnels using hyperworms. A hyperworm resembles a huge, very powerful snake and devours everything on its way leaving behind a smooth and durable tunnel. Goblins can summon and control a hyperworm by magic, forcing the animal to dig a tunnel in a required direction.

Though hyperworms are very powerful and easy to use, gnomes and other underground creatures do not use them, because hyperworms can only move devouring earth or stones. This means that if a hyperworm has finished digging a tunnel to a required destination and no new tunnels leading from that place are needed, then the only way to stop the beast is to dematerialize the poor thing. And this is of course severely banned since hyperworms are included in the Orange Book of Rare Magical Creatures and a substantial penalty must be paid for the death of each of them. But goblins don't care much about laws underground, where nobody can see them. What they really care about is the security of the bank, so they never dig more than one tunnel between a pair of rooms. And, of course, goblins don't ever think about digging a tunnel that does not connect two different rooms.

The Minister of Magic got hold of a complete scheme of tunnels between the bank's vaults. He wants to demand penalties for each of the tunnels. Of course, goblins may say that if two tunnels lead to the same vault, they used one hyperworm to lay them, having led the animal along the vault's border. Moreover, for digging any chain of tunnels they also could use one hyperworm. But the Minister knows for sure that goblins cannot drag a hyperworm from one vault to another, and they could not broaden out the existing tunnels because of safety reasons.

Help goblins to present to the Minister a plan of digging tunnels according to which a minimal number of hyperworms were murdered underground.

The first line contains numbers N and M (1 ≤ N ≤ 20000, 1 ≤ M ≤ 20000), which are the numbers of the bank's vaults and tunnels, respectively. The next M lines contain pairs of numbers (each number is in the range from 1 to N). Each pair indicates which vaults are connected by a tunnel. For any two vaults of the bank, there is a chain of tunnels connecting them.

In the first line you should output the minimal number of hyperworms K needed for digging all of the bank's tunnels. In each of the next K lines, output the numbers of vaults through which the corresponding hyperworm moved according to your plan. The vaults must be listed in the order in which the animal moved through them.