У вас є простий неорієнтований граф з $n$ вершинами, пронумерованими від $1$ до $n$, і $m$ ребрами, пронумерованими від $1$ до $m$. Ребро $i$ з'єднує вершини $u_i$ та $v_i$.

Кожна вершина пофарбована або в червоний, або в синій колір. Колір вершини $i$ представлений $c_i$; вершина $i$ пофарбована в червоний, якщо $c_i=0$, і в синій, якщо $c_i=1$.

Зараз Сергійко знаходиться на вершині $1$, а Женька - на вершині $n$. Вони можуть повторювати наступний хід нуль або більше разів.

Кожен з них одночасно переходить до вершини, суміжної з поточною вершиною. При цьому вершини, до яких переміщуються Сергійко та Женька, повинні мати різні кольори.

Повторюючи цей хід, чи можуть Сергійко та Женька одночасно опинитися на вершинах $n$ та $1$ відповідно?

Якщо це можливо, знайдіть мінімальну кількість ходів, необхідних для цього. Якщо це неможливо, надрукуйте $-1$.

На початку вхідних даних вам дано $t$. Розв'яжіть задачу для $t$ тестових випадків.

Input Specification

У першому рядку розміщене число $t$ ($1\le t\le 1000$) - кількість тестів.

У першому рядку кожного тесту задано два числа $n$ ($1\le n\le 2000$) та $m$ ($1\le m\le min(\frac{n(n-1)}{2},2000)$) - кількість вершин та ребер.

У другому рядку задано $n$ чисел $c_i$ ($c_i\in \{0,1\}$).

У наступних $m$ рядках задано по два числа $u_i$ та $v_i$ ($1\le u_i,v_i\le n$) - номери вершин, які з'єднує $i$-те ребро.

Output Specification

Для кожного тесту виведіть довжину найкоротшого маршруту або $-1$, якщо його немає.

Sample Input 1

3
4 4
0 1 0 1
1 2
2 3
1 3
2 4
3 3
0 1 0
1 2
2 3
1 3
6 6
0 0 1 1 0 1
1 2
2 6
3 6
4 6
4 5
2 4

Sample Output 1

3
-1
3