세계 일주

FJ는 지금까지 전 세계에 아주 많은 농부 친구를 사귀었습니다. 한동안 영국의 'Farmer Ted'와 네덜란드의 'Boer Harms'를 찾아가지 못했기 때문에 그들을 방문하려고 합니다.

그는 친구마다 사는 농장의 경도를 알고 있습니다. 경도는 지구상에서 농장의 위치를 나타내는 0부터 359까지의 정수 각도입니다. 지구는 복잡한 구면이 아니라 원으로 봅니다. 명백한 불연속점을 제외하면 원을 따라 시계 방향으로 가면 경도가 증가합니다.

FJ는 비행기로 $N$명의 친구를 방문하려고 합니다. 여기서 $1 \le N \le 5000$이고, 농장은 1번부터 $N$번까지 번호가 붙어 있습니다. 농장 사이에는 양방향 항공편이 $M$개 있으며, 그 시간표를 알고 있습니다. 여기서 $1 \le M \le 25000$입니다. 비행기는 항상 지구 표면의 최단 경로, 즉 원의 최단 호를 따라 이동합니다.

직접 연결된 두 농장 사이에는 최단 경로가 하나뿐입니다. 대척점(원 위에서 정확히 반대편에 있는 농장 쌍)끼리는 직접 연결되지 않습니다.

각 항공편은 지구를 시계 방향 또는 반시계 방향으로 이동합니다. 예를 들어 경도 30에서 35로 가는 항공편은 시계 방향이고, 350에서 10으로 가는 항공편도 시계 방향입니다. 반면 350에서 200으로 가는 항공편은 최단 경로인 반시계 방향으로 갑니다.

FJ는 가는 길에 친구들을 방문하면서 세계 일주를 하고 싶어 합니다. 가능한지 알아보고, 가능하다면 필요한 항공편 수의 최솟값을 구하세요. 출발지와 도착지는 입력에서 가장 먼저 나오는 가장 친한 친구의 농장입니다. 실제로 지구를 한 바퀴 돌도록, 그가 이동한 시계 방향 거리와 반시계 방향 거리는 서로 달라야 합니다.

첫 줄에 공백으로 구분된 정수 $N$과 $M$이 주어집니다.

둘째 줄부터 $N+1$번째 줄까지 각 줄에 $i$번째 농장의 경도가 정수 하나로 주어집니다. 둘째 줄은 가장 친한 친구의 농장 위치입니다.

$N+2$번째 줄부터 $N+M+1$번째 줄까지 각 줄에 항공편으로 연결된 두 농장의 번호가 주어집니다.

FJ가 세계 일주를 하는 데 필요한 항공편 수의 최솟값을 정수 하나로 출력합니다. 한 농장에서 다른 농장으로 이동할 때마다 항공편 1회로 셉니다. 그런 여행이 불가능하면 -1을 출력합니다.