Giải bài trực tuyến Học viện Công nghệ Bưu chính Viễn Thông

Bob đang trong kì nghỉ hè tại bờ biển. Thật không may, các khách sạn gần bờ biển đã hết phòng và anh phải ở trong trung tâm thành phố. Anh đã thuê hẳn một chiếc xe máy để có thể vi vu khắp thành phố biển này. Đêm nay, địa điểm mà anh muốn tới không phải là bãi biển như thường ngày, mà là tháp truyền hình cao nhất của thành phố.

Hệ thống giao thông trong thành phố khá phức tạp. Có N nút giao thông và M con đường một chiều nối giữa các điểm giao thông. Khách sạn của Bob nằm gần nút giao thông thứ nhất, còn tháp truyền hình ở ngay gần nút giao thông thứ N. Đi đường buổi tối nên Bob rất muốn tránh các khúc cua, anh chỉ muốn giữ ga và phóng đều trên đường. Vì vậy, Bob muốn chọn cho mình một hành trình sao cho góc cua lớn nhất trong hành trình là nhỏ nhất. Tuy nhiên, anh cũng không muốn quãng đường đi quá dài, vì xe của anh chỉ đủ xăng để đi được tối đa khoảng cách bằng D.

Các bạn  hãy giúp Bob chọn ra hành trình tối ưu, và tính góc cua lớn nhất trong hành trình tối ưu này.

Input

Dòng đầu tiên gồm 3 số nguyên N, M, D lần lượt là số nút giao thông, số đường một chiều và khoảng cách lớn nhất mà Bob mong muốn. (N <= 200, M <= N*(N-1)/2, D <= 10^6).

N dòng tiếp theo, mỗi dòng gồm 2 số nguyên x_i, y_i (giá trị tuyệt đối nhỏ hơn 10^5), là tọa độ của các nút giao thông.

M dòng tiếp, mỗi dòng gồm 2 số nguyên u, v, cho biết có con đường một chiều nối từ nút giao thông u đến nút giao thông v.

Input đảm bảo luôn có ít nhất một tuyến đường đi từ nút 1 tới N.

Output

Với mỗi test, in ra đáp số của bài toán với độ chính xác 10^-6. Nếu Bob không thể tới được đích, hãy in ra “Impossible”.

Example

Test 1:

Input:

5 6 500
-100 0
-100 100
0 200
100 100
100 0
1 2
1 3
2 3
3 4
3 5
4 5

Output:

90.00000000

Giải thích test 1: Hành trình tối ưu là 1-2-3-4-5. Góc cua lớn nhất là tại nút 3 bằng 180-90 = 90 độ.

Test 2:

Input:

5 6 450
-100 0
-100 100
0 200
100 100
100 0
1 2
1 3
2 3
3 4
3 5
4 5

Output:

126.86989765

Test 3:

Input:

5 12 440
-100 0
-100 100
0 200
100 100
100 0
1 2
1 3
3 1
2 3
3 2
3 4
4 3
3 5
5 3
4 5
5 4
5 1

Output:

Impossible