Longest Airline Travel Route

Given an undirected graph representing an airline map, where each vertex is a city and each edge is a direct flight between two cities, and no two cities share the same longitude, find a travel route that satisfies the following conditions and visits the maximum number of distinct cities:

1. The route starts at the westernmost city, then flies east‐wards (i.e. always moving to a city with a larger longitude) to reach the easternmost city, and then flies west‐wards (i.e. always moving to a city with a smaller longitude) back to the starting city.
2. Other than the starting city, no city is visited more than once.

If we denote the route by a sequence of cities, the goal is to maximize the number of cities in the route. In other words, if the route is represented as a cycle where the start and end city are the same, and the flight directions satisfy

[ \text{if } v_0, v_1, ..., v_k \text{ is the route, then } ; v_0 \to v_1 \to \cdots \to v_i \text{ with } L(v_0) < L(v_1) < \cdots < L(v_i) \text{ and } v_i \to v_{i+1} \to \cdots \to v_k \text{ with } L(v_i) > L(v_{i+1}) > \cdots > L(v_k = v_0), ]

find the maximum possible number of distinct cities visited. If no valid route exists, output -1.

inputFormat

The first line contains two integers n and m (n is the number of cities and m is the number of flights). The second line contains n space-separated integers representing the longitudes of the cities. It is guaranteed that no two longitudes are the same. The following m lines each contain two integers u and v (1-indexed) indicating that there is a direct flight between cities u and v.

outputFormat

Output a single integer: the maximum number of distinct cities that can be visited on a valid route. If no such route exists, output -1.

sample

6 6
10 20 30 40 50 60
1 2
2 3
3 6
6 5
5 4
4 1

6