The computer network of “Plunder & Flee
Inc.” consists of n servers and m two-way
communication links. Two servers can communicate either through a direct link,
or through a chain of links, by relaying information from server to server.
Current network setup enables communication for any pair of servers.
The network administrator strives to maximize
network reliability. Some communication links in the network were identified as
critical. A failure on any critical link will split the network into
disconnected segments. Company management responded to the administrator’s
concerns and agreed to fund another communication link, provided that when the
new link goes online the number of critical links will be minimized.
Write a program that, given a network
configuration, will pick a pair of servers to be connected by the new
communication link. If several such pairs allow minimizing the number of
critical links then any of them will be considered as a correct answer.
Example. The following figure presents a network
consisting of 7 servers and 7 communication links. Essential links are shown as
bold lines. A new link connecting servers #1 and #7 (dotted line) can reduce
the number of the critical links to only one.
Limitations
1 <= n <= 10 000; 1<= m <= 100 000; 1 <= xi, yi <= n; xi ≠
yi.
Input
The first line contains two space-delimited integer numbers n
(the number of servers) and m (the number of communication links). The following m lines describe the communication links. Each
line contains two space-delimited integers xi and yi,
which define the IDs of servers connected by link number i. Servers are identified with natural
numbers ranging from 1 to n.
Output
The output file should contain a single line with space-delimited integers x
and y, the IDs of servers to be connected by the new
link.
Example
Input
|
Output
|
|
7 7
1 2
2 3
2 4
2 6
3 4
4 5
6 7
|
1 7
|
Input
|
Output
|
|
5 6
1 2
2 3
3 1
4 3
4 5
5 4
|
3 4
|
All Rybinsk-2012 problems (in PDF)
