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

MSU SE and Ural SU contest. Petrozavodsk training camp. Summer 2005

About     Problems     Submit solution     Judge status     Standings
Contest is over

J. Roadworks

Time limit: 1.0 second
Memory limit: 64 MB
Once upon a time there was a king. One day the king counted up the collected taxes and decided to spend the money for the road maintenance. There were N cities in that kingdom and M two-way roads connected them in such way that one could travel from a city to others using these roads. The road network was catastrophic without repairing, so the king made up his mind to repair as many roads as possible during the summer, before the money depreciated. The inhabitants of the kingdom were shocked to know that all the ways they used to go would be blocked for summer. So the king promised that at most one road from a city would be blocked. Help the king to fulfil his plan without displeasing the citizens.


The first line of input contains two natural numbers N and M (2 ≤ N ≤ 105, M = N − 1), separated with a space. Each of the next M lines describes a road in the form (ai, bi), where ai and bi are numbers of the cities connected with i'th road (1 ≤ ai, biN).


The first line of output should contain the only integer K being the maximum number of roads that the king can close for maintenance without raising disorders in his kingdom. The next K lines should describe these roads in the same form as they were given in the input.


4 3
1 2
2 3
3 4
1 2
3 4
Problem Author: Dmitry Ivankov & Alexander Ipatov
Problem Source: Petrozavodsk summer training camp, August 2005.
To submit the solution for this problem go to the Problem set: 1389. Roadworks