Submissions will no longer be placed on the leaderboard. You may still attempt this problem for practice.

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 .

image

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 .

image

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.

image

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 .

image

Line: 1 Col: 1
  1. Challenge Walkthrough
    Let's walk through this sample challenge and explore the features of the code editor.1 of 6
  2. Review the problem statement
    Each challenge has a problem statement that includes sample inputs and outputs. Some challenges include additional information to help you out.2 of 6
  3. Choose a language
    Select the language you wish to use to solve this challenge.3 of 6
  4. Enter your code
    Code your solution in our custom editor or code in your own environment and upload your solution as a file.4 of 6
  5. Test your code
    You can compile your code and test it for errors and accuracy before submitting.5 of 6
  6. Submit to see results
    When you're ready, submit your solution! Remember, you can go back and refine your code anytime.6 of 6
  1. Check your score