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
© 2015 HUST ACMICPC TEAM. All Right Reserved.