問題文

naka9 君は素晴らしい景観で有名な TSG 王国へ旅行する計画を組んでいます。

TSG 王国には地点 1 から地点 $N$ の地点とそれらを繋ぐ $M$ 本の道路があり、 $i$ 番目の道路は相異なる地点 $a_i$ と地点 $b_i$ を双方向に繋いでいます。 地点間を直接繫ぐ道路は高々 1 本しかありません。

また、各地点 $i$ はこれら $N$ 地点の中で $H_i$ 番目に標高が低いです。 ここで、 $H_i$ は相異なります。

naka9 君は地点 1 から地点 $N$ までハイキングをしようと考えていますが、 何度も登り降りしたくありません。

そこで、ある地点まで登り、ある地点から下りであるような経路、 つまり、地点 $v_1(=1),v_2,\dots,v_K(=N)$ を順に歩くとして、ある $1\leq j\leq K$ について $H_{v_1},\dots,H_{v_j}$ は単調増加、 $H_{v_j},\dots,H_{v_K}$ は単調減少になるような経路を探したいです。

このような条件を満たす経路の中で、最も長い経路の長さを出力してください。 ただし、条件を満たす経路が存在しない場合はその旨を出力してください。

入力

$N\ M$
$H_1\ H_2\ \cdots\ H_N$
$a_1\ b_1$
$\vdots$
$a_M\ b_M$

• $2\leq N\leq 10^5$
• $1\leq M\leq \min(10^5,\frac{N(N-1)}{2})$
• $1\leq H_i\leq N \quad (1\leq i\leq N)$
• $i\neq j$ のとき $H_i\neq H_j$
• $1\leq a_i<b_i\leq N\quad(1\leq i\leq M)$
• $i\neq j$ のとき $(a_i,b_i)\neq(a_j,b_j)$
• 入力は全て整数

出力

条件を満たす経路の長さを出力してください。ただし、そのような経路が存在しない場合には -1 を出力してください。また、最後に改行してください。

サンプル

3 2
1 3 2
1 2
2 3

3

3 2
2 1 3
1 2
2 3

-1

10 20
1 9 5 4 7 3 8 6 10 2
7 9
1 2
3 10
1 10
6 8
7 8
1 3
4 6
4 8
1 6
3 6
7 10
5 10
2 6
1 9
9 10
2 4
8 10
3 5
5 7

10

4 4
2 3 4 1
1 2
2 3
3 4
1 4

6

4 2
1 2 3 4
1 2
3 4

-1