Output: Standard Output
Time Limit: 2 Seconds
It is the year 95 ACM (After the Crash of Microsoft). After
many years of peace, a war has broken out. Your nation, the
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.
The input file contains several test cases. The data for each case begins with a line containing the following two integers:
Next few lines consists of pairs of integers. Each pair (x,y) indicates the presence of a bidirectional railway line connecting railway stations x and y. This sequence is terminated by a line containing two minus 1 as shown in the sample input.
Input is terminated by a case where the value of n=m=0. This case should not be processed.
8 4 0 4 1 2 2 3 2 4 3 5 3 6 3 7 6 7 -1 -1 0 0 |
2 3 3 3 4 2 0 1 |
Problemsetter:
Paul Shelly