Bảo tồn động vật
Một khu bảo tồn động vật có $n$ địa điểm và có $m$ đường đi hai chiều nối các địa điểm đó. Địa điểm thứ $i$ có nhiệt độ là $h_i$, giữa hai địa điểm bất kì có nhiều nhất một con đường đi nối chúng.
Người ta muốn di chuyển một loài động vật quý hiếm từ địa điểm $s$ tới địa điểm $t$, tuy nhiên nếu chênh lệch nhiệt độ giữa hai địa điểm liên tiếp là quá cao thì loài động vật này rất có thể bị chết.
Hãy chỉ ra một hành trình mà độ chênh lệch nhiệt độ lớn nhất giữa hai địa điểm liên tiếp bất kì trên đường đi là cực tiểu.
Dữ liệu
- Dòng đầu tiên chứa xâu kí tự $S \ (|S| \le 10^5)$;
- Dòng đầu chứa 4 số nguyên $n,m,s,t \ (2\le n \le 10^5; 1\le m \le 2\times 10^5; 1\le s,t\le n)$;
- Dòng thứ hai chứa $n$ số nguyên dương $h_i \ (0\le h_i \le 10^5)$l
- $m$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $u,v \ (1\le u,v \le n)$ cho biết hai địa điểm $u,v$ có đường đi nối chúng.
Kết quả
- Một dòng duy nhất là độ chênh lệch nhỏ nhất tìm được. Nếu không có đường đi ghi ra -1.
Chấm điểm
50; $n\le 1000$. 50; Không có giới hạn gì thêm.
Ví dụ
Ví dụ 1
input
7 11 1 4
20 22 29 30 24 27 26
1 2
1 3
1 4
2 4
2 5
3 4
3 6
4 5
4 6
5 7
6 7
output
2
Comments