Around the World

Over the years, FJ has made a huge number of farmer friends all around the world. Since he hasn't visited 'Farmer Ted' from England and 'Boer Harms' from Holland for a while, he'd like to visit them.

He knows the longitude of the farm where each of his worldwide friends lives. A longitude is an integer angle from 0 to 359 that gives the farm's location on the Earth. The Earth is treated as a circle instead of the more complex spherical shape. Except at the obvious discontinuity, longitudes increase when you travel clockwise around the circle.

FJ plans to fly to visit his $N$ friends, where $1 \le N \le 5000$ and the farms are numbered 1 to $N$. He knows the schedules for $M$ bidirectional flights between farms, where $1 \le M \le 25000$. Airplanes always travel along the shortest path on the Earth's surface, which is the shortest arc of the circle.

There is always a unique shortest path between two directly connected farms. No pair of antipodal farms (exactly opposite each other on the circle) is ever directly connected.

Each flight travels either clockwise or counterclockwise around the Earth. For example, a flight from longitude 30 to longitude 35 is clockwise, and so is a flight from longitude 350 to longitude 10. A flight from longitude 350 to longitude 200 follows the shortest path counterclockwise.

FJ would like to make a trip around the world, visiting some of his friends along the way. Find out whether this is possible and, if so, the minimum number of flights needed. He starts and ends at his best friend's farm, the one listed first in the input. To make sure he actually circles the Earth, the clockwise distance he travels must differ from the counterclockwise distance he travels.

The first line has two space-separated integers, $N$ and $M$.

Lines 2 to $N+1$ each contain one integer, the longitude of the $i$-th farm. Line 2 gives the location of his best friend's farm.

Lines $N+2$ to $N+M+1$ each contain two integers, the indices of two farms connected by a flight.

Print one integer, the minimum number of flights FJ needs to make a trip around the world. Each move from one farm to another counts as one flight. If such a trip is impossible, print -1.