Global Journey

Farmer John has many friends around the globe who run farms. He wishes to embark on a round‐trip journey by airplane to visit some of his n friends (numbered from 1 to n), starting and ending at his best friend’s farm (node 1).

Each farm has an associated longitude (an integer from 0 to 359). We imagine the Earth as a circle with longitudes increasing in the clockwise direction. There are m bidirectional flights between these farms. Each flight connects two farms along the shortest path on the circle. That is, for a flight from a farm at longitude L_a to a farm at longitude L_b, define:

\( \text{diff} = (L_b - L_a + 360) \mod 360 \).

The flight chooses the shorter arc. In particular:

• If \(\text{diff} \le 180\), the airplane flies in the clockwise direction covering a distance of \(\text{diff}\) and the complementary anticlockwise distance is \(360-\text{diff}\). The net distance difference is \(\text{cw} - \text{anticw} = 2\cdot\text{diff} - 360\), which is negative because \(\text{diff} < 180\).
• If \(\text{diff} > 180\), then the airplane flies in the anticlockwise direction covering a distance of \(360-\text{diff}\) and the clockwise distance becomes \(\text{diff}\). The net difference is \(\text{cw} - \text{anticw} = 360-2\cdot(360-\text{diff}) = 360 - 2\cdot\text{diff}\), which is positive.

Note: It is guaranteed that if two farms lie exactly on opposite ends of the circle (i.e. their chord would subtend a 180° arc), they will not be directly connected by a flight.

Farmer John defines this journey as a "global journey" if, when he returns to his starting farm (farm 1), the total distance traveled in the clockwise direction is different from the total distance traveled in the anticlockwise direction (i.e. the sum of the net differences is not zero). He wants to know if such a journey is possible by taking a sequence of flights and, if so, what is the minimum number of flights he needs.

Task: Given the farms’ longitudes and the available flights, determine the minimum number of flights required for Farmer John to complete a global journey starting and ending at farm 1. If no such journey exists, output -1.

Mathematical Formulation:

For a flight from a to b, let

[ d(a,b)=\begin{cases} 2\cdot((L_b - L_a + 360) \mod 360)-360, & \text{if }(L_b - L_a + 360) \mod 360 \le 180,\ 360-2\cdot((L_b - L_a + 360) \mod 360), & \text{if }(L_b - L_a + 360) \mod 360 > 180. \end{cases} ]

Find the shortest cycle (in terms of number of flights) starting and ending at node 1 such that the overall sum \(\sum d(a,b) \neq 0\).

inputFormat

The input consists of:

1. The first line contains two integers n and m (\(1 \le n \le 100\), \(0 \le m \le 1000\)), representing the number of farms and the number of flights, respectively.
2. The second line contains n integers \(L_1, L_2, \ldots, L_n\) where each \(L_i\) (0 \(\le L_i \le 359\)) is the longitude of the \(i^{th}\) farm.
3. Each of the next m lines contains two integers u and v (1 \(\le u, v \le n\), u \(\ne\) v) indicating that there is a bidirectional flight between farms u and v.

It is guaranteed that if two farms are diametrically opposite, they will not be directly connected by a flight.

outputFormat

Output a single integer representing the minimum number of flights required for a global journey starting and ending at farm 1 such that the total clockwise distance is not equal to the total anticlockwise distance. If no such journey exists, output -1.

sample

3 3
10 20 350
1 2
2 3
3 1

3