P9834 [USACO05OPEN] Around the world G

In recent years, Farmer John has made many friends around the world who also run farms. Since he has not visited Ted the farmer in the UK and Boor the farmer in the Netherlands for a while, he wants to go and visit them. He knows the longitude of each friend’s farm (an integer from $0$ to $359$). We treat the Earth as a circle, and longitudes increase clockwise along this circle. Farmer John plans to travel by plane to visit his $n$ friends (numbered from $1$ to $n$). He knows there are $m$ bidirectional flight routes between these farms. The plane always flies along the shortest path on the surface (that is, the shorter arc on the circle). Every route between two farms must be along the shortest arc. It is guaranteed that if two farms are at opposite ends of a diameter, then there will not be a direct route connecting them. Therefore, any single trip can be described as either clockwise or counterclockwise. For example, going from longitude $30$ to longitude $35$ is clockwise; going from longitude $350$ to longitude $10$ is also clockwise; while going from longitude $350$ to longitude $200$ is counterclockwise. To look cool, Farmer John decides to make a round-the-world trip by passing through some of his friends’ farms. He wants to know whether this is possible, and if it is, the minimum number of flights needed. He wants to start and end this trip at his best friend’s farm (the first one in the input). To ensure this is a round-the-world journey, when the trip ends, the total clockwise distance traveled must not be equal to the total counterclockwise distance traveled.

The first line contains two integers $n$ and $m$, separated by spaces. Lines $2$ to $n+1$: line $i+1$ contains one integer, the longitude of farm $i$. The second line is the address of his best friend. Lines $n+2$ to $n+m+1$: line $i+n+1$ contains two integers, indicating that there is a route between these two farms.

Output one integer: the minimum number of flights Farmer John must take to complete the round-the-world trip. Each time Farmer John travels from one farm to another counts as one flight. If it is impossible to make a round-the-world trip, output `-1`.

For $100\%$ of the testdata, $1 \leq n \leq 5 \times 10^3$ and $1 \leq m \leq 2.5 \times 10^4$. Translated by ChatGPT 5