Cargo Delivery
There are cities numbered from to connected by bidirectional roads. It's possible to travel from city to city . There is at most one road between any pair of cities and each road connects two different cities.
Initially, all roads are brand new, so their brokenness is . Every time a truck passes through a road, the brokenness of this road increases by one after the truck passes it.
However, things are not that bad. You are allowed to do the following times: choose a single road and repair it. Every time a road is repaired, its brokenness decreased by . A single road can be repaired multiple times.
Finally, the brokenness of a truck is defined as the maximum brokenness of a road it passes through, measured at the time it was passing that road.
You are a manager of the transport department in the Big Company, so obviously, you don't want the trucks to get broken too much. What's the minimum possible brokenness of a truck among all trucks driving from city to city ?
Complete the function minimumBrokenness
which takes in four integers , , and and returns the minimum possible brokenness of a truck among all trucks driving from city to city . You need to take the information about roads from the sample input.
Input Format
The first line contains four space-separated integers , , and .
The of the following lines contains two space-separated integers and , denoting that there is a road between cities and .
Constraints
Output Format
Print a single integer denoting the minimum possible brokenness of a truck among all trucks driving from city to city ?
Sample Input 0
5 5 2 1
0 1
1 2
1 3
2 4
3 4
Sample Output 0
0
Explanation 0
For the first truck, the route is for first truck.
The road between and is then repaired.
For the second truck, the route is .
Sample Input 1
7 8 2 0
0 1
0 2
1 3
2 3
3 4
3 5
4 6
5 6
Sample Output 1
0
Explanation 1
For the first truck, the route is .
For the second truck, the route is .
Sample Input 2
3 2 5 2
0 1
1 2
Sample Output 2
3
Explanation 2
For every truck, the route is . After the first truck, both roads are repaired.
Sample Input 3
4 4 10 0
0 1
1 3
0 2
2 3
Sample Output 3
4
Explanation 3
For the first trucks, the route is .
For the second trucks, the route is .
xxxxxxxxxx
with Ada.Text_IO, Ada.Integer_Text_IO;
use Ada;
procedure Solution is
-- Enter your code here. Read input from STDIN. Print output to STDOUT
end Solution