Đề bài: Vòng quanh thế giới

Qua nhiều năm, FJ đã có rất nhiều bạn là những người nông dân trên khắp thế giới. FJ muốn đến thăm tất cả họ. Anh ta biết kinh độ của mỗi trang trại nơi các người bạn của mình cư trú. Kinh độ này là một góc (một số nguyên trong khoảng từ ~ 0 ~ đến ~ 359 ~) mô tả vị trí của trang trại trên Trái Đất, mà ta sẽ xem như một vòng tròn thay vì biểu diễn hình cầu phức tạp.

FJ có kế hoạch di chuyển bằng máy bay để thăm ~ n ~ người bạn của mình (với các trang trại được đánh số từ ~ 1 ~ đến ~ n ~). Anh ta biết lịch trình của ~ m ~ chuyến bay hai chiều kết nối giữa các trang trại. Máy bay luôn di chuyển theo đường ngắn nhất trên bề mặt Trái Đất (tức là trên cung tròn ngắn nhất của vòng tròn).

FJ muốn biết liệu anh có thể thực hiện một chuyến đi vòng quanh thế giới, ghé thăm tất cả ~ n ~ người bạn của mình trên đường đi hay không và nếu có, số lượng chuyến bay ít nhất mà anh cần thực hiện để hoàn thành chuyến đi đó là bao nhiêu.

Input

• Dòng 1: Hai số nguyên cách nhau bởi dấu cách ~ n ~ và ~ m ~ (~ 1 \leq n \leq 5000 ~, ~ 1 \leq m \leq 25000 ~).
• Dòng 2 đến ~ n+1 ~: Dòng ~ i+1 ~ chứa một số nguyên: kinh độ của trang trại thứ ~ i ~.
• Dòng ~ n+2 ~ đến ~ n+m+1 ~: Mỗi dòng chứa hai số nguyên, biểu thị chỉ số của hai trang trại được kết nối bởi một chuyến bay.

Output

• Một số nguyên duy nhất biểu thị số chuyến bay tối thiểu mà FJ cần thực hiện để hoàn thành chuyến đi vòng quanh thế giới. Nếu không thể thực hiện chuyến đi, in ra số -1.

Ví dụ

Input

3 3
0
120
240
1 2
2 3
1 3

Output

3