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

USU Championship 2007

About     Problems     Submit solution     Judge status     Standings
Contest is over

H. Networking the “Iset”

Time limit: 1.0 second
Memory limit: 64 MB
Problem illustration
There’s not much time left until the “Iset” tower opens for business, but a computer network is not yet installed in the building. The network is expected to be very robust and should have lots of branches. There are N nodes in the tower that should be connected with this network. These nodes were planned to be connected with M direct links, with no more than one direct link between each pair of nodes. To save some time, it was decided that only the links that are required to make a connected network will be installed; all the remaining wires are going to be laid after the opening ceremony. In order to be efficient network should have satisfy one more requirement: the maximal distance between it’s nodes must be as small as posible. Distance between a pair of nodes A and B is defined as the number of intermediate nodes on the path from the node A to the node B.

Input

The first line contains two integers N (2 ≤ N ≤ 100) and M (1 ≤ M ≤ 10000). The following M lines describe the initial planned network layout. Each of these lines contains a pair of integers — numbers of nodes that are connected with a direct link. Nodes are numbered from 1 to N. This network layout is guaranteed to be connected, and there are no links connecting a node with itself.

Output

The new network layout (in the same format).

Sample

inputoutput
4 4
1 2
2 3
2 4
3 4
1 2
2 3
2 4
Problem Author: Sergey Pupyrev
Problem Source: The XIIth USU Programing Championship, October 6, 2007
To submit the solution for this problem go to the Problem set: 1569. Networking the “Iset”