题目描述

有一张包含 $N$ 个顶点和 $M$ 条边的简单无向图，顶点编号为 $1$ 到 $N$。每个顶点被涂成红色或蓝色，$C_i=0$ 表示红色，$C_i=1$ 表示蓝色。

开始时，高桥在顶点 $1$，青木在顶点 $N$。每次操作中，两人必须同时移动到各自当前顶点的某个相邻顶点，并且两人移动后所在顶点的颜色必须不同。

请判断能否经过若干次操作，使高桥到达顶点 $N$，同时青木到达顶点 $1$。若可以，求最少操作次数；否则输出 $-1$。

输入格式

第一行输入测试用例数 $T$。每组数据第一行输入 $N,M$，第二行输入 $N$ 个颜色 $C_i$，接下来 $M$ 行输入无向边 $u_i,v_i$。

输出格式

对每组数据输出一行一个整数，表示最少操作次数；无法实现时输出 $-1$。

数据范围与约定

$1\le T$；每组 $2\le N\le2000$，图为简单无向图，所有测试用例的规模满足题目时限要求。

可见测试数据

输入数据 1

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

输出数据 1

-1

输入数据 2

1
2 1
1 1
1 2

输出数据 2

-1

输入数据 3

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

输出数据 3

-1