1230 - beautiful
Time Limit : 3 Second
Memory Limit : 128 MB
Submission: 151
Solved: 44
- Description
- Timy is visiting a beautiful park. There are M rivers and N lakes(marked 1-N), any two lakes are connected by at most one river. He knows that the ith river had to have water flowed with speed in the range [li,ri] to make the park beautiful . The staff will pour water in one lake (lake marked 1) and only one lake (lake marked N) connected to the outside from which the water will flow away. To save water , Timy wants to know what's the minimal speed for the staff to pour water in order to make the park beautiful .
- Input
- The input contains several test cases.
For each test case Two positive integer numbers N (1 <= N <= 60) and M (0 < M <= N^2) have been written in the first line - number of lakes and rivers.
There are M lines follows: each line contains four integer numbers fi, ti, li, ri (fi!=ti , 0 < fi,ti <= N, 0 <= li <= ri < 10000); the numbers are separated by space indicate the ith river flow from fi to ti and the range of speed is [li,ri].
- Output
- Write one integer number for each test case - it ought to be the minimal speed of add water.
If it is impossible to make the park beautiful, write "Impossible". - sample input
-
4 4 1 2 0 2 2 4 1 1 1 3 2 2 3 4 0 3 4 4 1 2 0 1 2 4 2 2 1 3 3 3 3 4 0 2
- sample output
-
3 Impossible
- hint
- source
- Wu Shaoliang