Fast Transportation

Time Limit: 2000/1000MS (Java/Others) Memory Limit: 128000/64000KB (Java/Others)

Problem Description

I’m working for a huge transportation company, and this month we get a job that deliver K important medicinal machines from city S to city T. Since the machines is so large that for each machine we should use a whole truck to carry it.

We live in a country contains N cities and M bidirectional roads, each road cost one day to passed. And your boss wants you, the best programmer, to find a plan which can deliver all machines in fewest days.

However with the unknown reasons, we can just use each road only once a day.

Sometimes a truck can choose not to go but wait at a city.

A city can hold any truck each day.

Input

There are multiple test cases.

In each test case, the first line contains five integers N, M, K, S and T.
Next M lines each line contains two integers a, b, indicating a road connected the city a and city b.
There is at most one road in any two cities, and no road connected one city to itself.

2 ≤ N ≤ 10, 1 ≤ M ≤ 20

1 ≤ K ≤ 50, 1 ≤ S, T ≤ N, S != T

Output

For each test, please output an integer indicating the fewest days to deliver all machine to the destination.

Sample Input

6 7 4 1 6
1 2
2 3
3 5
5 6
1 4
4 6
4 3

Sample Output

4

Hint

The road can be traveled in both directions, but remember that each day only one truck can travel through it, in particular, two trucks cannot simultaneously travel the same road in opposite directions

Source

dut200901102

Manager

Information
Solved Number53
Submit Number245
Problem Tags
flows
graphs
No tag edit access
温馨提示:AC后可以编辑标签哦. ^-^
Login
LoginCancel