У вас є простий неорієнтований граф з \(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