题面翻译

给定一个 $n$ 个点 $m$ 条边的无向图，满足 $1\le n,m\le 2\times 10^3$。

每个点有一个点权，值可以为 $0$ 或 $1$。

两个人分别在点 $1$ 和 $n$，每次他们同时向自己这个结点的任意一个邻居移动，任意时刻，他们所在的结点的权值不得相同。最后要使得他们互相交换位置。

请求出最小次数，如果无解，输出 $-1$。

输入格式

本题有多组测试数据。第一行先输入 $T$ 代表测试数据组数。

每一组测试数据先输入两个整数 $N$ 与 $M$。

接下来一行输入 $N$ 个空格隔开的整数分别代表 $C_1,C_2,\cdots,C_N$ 代表每个点的点权。

接下来 $M$ 行每行输入两个空格隔开的整数代表 $U_i,V_i$ 代表图中的一条无向边。

输出格式

输出 $T$ 行。 第 $i$ 行应包含第 $i$ 组测试数据的答案。

对于每个测试用例，打印两个人交换位置的最小步数，若不可能交换打印 -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

3
-1
3

提示

数据范围

• $1 \leq T \leq 1000$
• $2 \leq N \leq 2000$
• $1 \leq M \leq \min(\frac{N(N-1)}{2}, 2000)$
• $C_i \in \lbrace 0, 1 \rbrace$
• $1 \leq u_i, v_i \leq N$
• 输入中给出的图是简单图。
• 输入中的所有值都是整数。
• 所有测试用例中 $N$ 的总和不超过 $2000$ 。
• 所有测试用例中 $M$ 的总和不超过 $2000$ 。

样例 1 解释

对于第 $1$ 组测试数据，高桥和青木可以通过下出 $3$ 步来实现目标，这是最少的步数：

• 高桥下到顶点 $3$ ，青木下到顶点 $2$ 。
• 高桥下到顶点 $2$ ，青木下到顶点 $3$ 。
• 高桥移至顶点 $4$ ，青木移至顶点 $1$ 。

注意在 $1$ 这步棋中，不允许高桥和青木同时下到顶点 $2$ （因为高桥和青木所下顶点的颜色必须不同）。

对于第 $2$ 组测试数据，无论他们如何移动，都无法实现目标。