Problem G: Doves and bombs

It is the year 95 ACM (After the Crash of Microsoft). After many years of peace, a war has broken out. Your nation, the island of Evergreen Macros And Confusing Shortcuts (EMACS), is defending itself against the railway empire ruled by Visually Impaired Machinists (VIM).

In the days leading up to the outbreak of war, your government devoted a great deal of resources toward gathering intelligence on VIM. It discovered the following:

Based on this information, the government of EMACS has come up with a plan to disrupt the activities of the evil empire. They will send bomber planes to bomb the railway stations, thus hampering communications in the empire. This will necessitate to acquire many carrier pigeons by the empire, distracting it from its deadly wartime activities.

Unfortunately, your government spent so much money on gathering intelligence that it has a very limited amount left to build bombs. As a result, it can bomb only one target. You have been charged with the task of determining the best candidate railway stations in the empire to bomb, based on their "pigeon value". The "pigeon value" of a station is the minimum number of pigeons that after bombing this station, will be required to broadcast a message from the empire central command to all non-bombed stations. The location of the empire central command is unknown but we know that it is not located at a railway station. This implies, that when the central command needs to send a message to some non-bombed station they have to use at least one pigeon and then the message can be further transmitted by the railway.

Your program should read input from file named pigeons.dat There will be one test case in each input file. The data for each case begins with a line containing the following two integers:

The rest of the input consists of pairs of integers. Each pair (x,y) indicates the presence of a bidirectional railway line connecting railway stations x and y.

The output should give m most desirable railway stations to bomb. There should be exactly m lines, each with two integers separated by a single space. The first integer on each line will be the number of a railway station, and the second will be the "pigeon value" of the station. This list should be sorted, first by "pigeon value", in descending order, and within the same "pigeon value" by railway station numbers, in ascending order.

Sample Input

8 4
0 4
1 2
2 3
2 4
3 5
3 6
3 7
6 7

Output for sample input

2 3
3 3
4 2
0 1

Paul Shelley