ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules

Ural Championship 2006

About     Problems     Submit solution     Judge status     Standings
Contest is over

C. From the History of Gringotts Bank

Time limit: 2.0 second
Memory limit: 64 MB
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.

Input

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.

Output

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.

Sample

inputoutput
7 7
1 2
4 1
6 7
5 7
7 4
2 3
4 2
3
5 7 4 2 1 4
2 3
6 7
Problem Author: Idea — Magaz Asanov, text — Stanislav Vasilyev, prepared — Pavel Zuev
Problem Source: The Xth Urals Collegiate Programing Championship, March 24-25, 2006
To submit the solution for this problem go to the Problem set: 1441. From the History of Gringotts Bank