题目描述

这些年，农夫约翰在国际上交了一大批开农场的朋友．由于他有一段时间没有去见过英国的农夫泰德和荷兰的农夫波尔，所以他想去访问他们, 他知道每个朋友的农场的经度．

经度（从$\red{0}$到$\red{359}$）是一种角度描述农场在地球上位置的方法，我们把地球看成一个圆，正如我们所熟知的，经度在地球上沿着顺时针方向增长, 农夫约翰打算乘 飞机去访问他的$\red{N(1≤}$$\red{N≤}$$\red{5000)}$个朋友（用$\red{1}$到$\red{N}$来表示）．

他知道在这些农场之间有$\red{M(1≤}$$\red{M≤}$$\red{25000)}$条双向的航线，当然飞机总是沿着地面上最短的路径飞行的（就是圆上的最短弧长）．两个农场之间的航线一 定是最短的，也就是说如果育两个农场在直径两端，那么他们之间一定不存在航线．

所以任何一次航行都可以被描述成顺时针或是逆时针的．比如说，经度$\red{30}$到经度$\red{35}$是顺时针的，经度$\red{350}$到经度$\red{10}$也是顺时针的，而经度$\red{350}$到经度$\red{200}$是逆时针的．

农夫约翰为了耍酷，决定要经过几个朋友的农场做到环球旅行，他想知道这是否可能，如果可能最少要乘几次飞机．

他想在他最好的朋友（也就是列表中的第一个）的农场上开始和完成这次旅行．为了保证这是一次环球航行，回到终点时，顺时针经过的路程不能等于逆时针经过的路程．

输入格式

第$\red{1}$行：两个用空格隔开的整数$\red{N}$和$\red{M.}$

第$\red{2}$到$\red{N+1}$行：

第$\red{i+l}$行有一个整数，表示第$\red{i}$个农场的经度．第$\red{2}$行是他的最好的朋友的地址．

第$\red{N+2}$过程$\red{N+M+I}$行：第$\red{i+N+1}$行有两个整数，表示这两个农场之间有航线．

输出格式

一个整数即农夫约翰至少要乘几次飞机才能完成环球旅行．

每次农夫约翰从一个农场前往另一个农场算作乘一次飞机．如果不可能做到环球旅行则输出$\red{-1.}$

样例

输入样例

3 3
0
120
240
1 2
2 3
1 3

输出样例

3

提示

输入详细信息：

农民约翰有三个朋友，分别在$\red{0}$、$\red{120}$和$\red{240}$经度三次飞行：$\red{0<->120}$、$\red{120<->240}$和$\red{0<->240}$。旅程必须开始并 在经度$\red{0}$处结束。

输出详细信息：

建省必须访问所有$\red{3}$个朋友，使全世界旅行。