Benson's Airplane Flight

Rabbit Benson is ready to start his airplane! There are \( n \) flying zones numbered from \( 1 \) to \( n \). Due to the terrain, when entering zone \( i \), the airplane's altitude must be at least \( a_i \), and it is guaranteed that \( a_1 = a_n = 0 \).

There are also \( m \) bidirectional flight routes. The \( j\)-th flight route connects zones \( u_j \) and \( v_j \), meaning that Benson can fly directly between these two zones. It is known that by using these direct routes, any two zones are mutually reachable.

Benson starts at zone \( 1 \) with an altitude of \( 0 \) and wishes to land at zone \( n \) (also at altitude \( 0 \)). Every minute, he can choose to either fly along one flight route or stay in the same zone. At the same time, he must adjust the airplane's altitude by exactly \( +1 \), \( 0 \), or \( -1 \). Note that upon arriving at any zone \( i \), the new altitude must be at least \( a_i \).

Your task is to determine the minimum time (in minutes) required for Benson to travel from zone \( 1 \) with altitude \( 0 \) to zone \( n \) with altitude \( 0 \). If it is impossible, output -1.

inputFormat

The first line contains two integers \( n \) and \( m \) representing the number of zones and the number of flight routes.

The second line contains \( n \) integers \( a_1, a_2, \dots, a_n \) where \( a_i \) is the minimum altitude required in zone \( i \) (with \( a_1 = a_n = 0 \)).

Each of the following \( m \) lines contains two integers \( u_j \) and \( v_j \) indicating that there is a direct bidirectional flight route between zones \( u_j \) and \( v_j \).

outputFormat

Output a single integer representing the minimum number of minutes required for Benson to reach zone \( n \) at altitude \( 0 \) from zone \( 1 \) at altitude \( 0 \). If it is impossible, output -1.

sample

3 2
0 1 0
1 2
2 3

2