问题描述

有一个简单无向图，有 $N$ 个顶点，顶点从 $1$ 到 $N$ 编号，有 $M$ 条边，边从 $1$ 到 $M$ 编号。第 $i$ 条边连接了顶点 $u_i$ 和顶点 $v_i$。
每个顶点都被涂成红色或蓝色。顶点 $i$ 的颜色用 $C_i$ 表示；如果 $C_i$ 为 $0$，则顶点 $i$ 被涂成红色，如果 $C_i$ 为 $1$，则顶点 $i$ 被涂成蓝色。

现在，高桥站在顶点 $1$，青木站在顶点 $N$。
他们可以重复以下移动零次或多次：

• 他们同时移动到当前顶点相邻的顶点。
  这里，高桥和青木移动到的顶点的颜色必须不同。

通过重复上述移动，高桥和青木能否同时站在顶点 $N$ 和顶点 $1$ 上？
如果可能，找出所需的最小移动次数。如果不可能，输出 -1。

输入开头给定了 $T$。解决这个问题需要对 $T$ 个测试用例分别进行求解。

约束条件

• $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$。

输入

输入以以下格式从标准输入给出，其中 $\\text{test}_i$ 表示第 $i$ 个测试用例：

$T$ $\\text{test}_1$ $\\text{test}_2$ $\\vdots$ $\\text{test}_T$

每个测试用例以以下格式给出：

$N$ $M$ $C_1$ $C_2$ $\dots$ $C_N$ $u_1$ $v_1$ $u_2$ $v_2$ $\vdots$ $u_M$ $v_M$

输出

输出共 $T$ 行。第 $i$ 行应该包含第 $i$ 个测试用例的答案。
对于每个测试用例，如果可能，输出高桥和青木同时到达顶点 $N$ 和顶点 $1$ 所需的最小移动次数；如果不可能，输出 -1。

示例输入 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

示例输出 1

3
-1
3

对于第一个测试用例，高桥和青木可以通过以下 $3$ 步达到目标，这是最少的步数：

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

注意，在第一步中，高桥和青木都不能移动到顶点 $2$（因为高桥和青木移动到的顶点的颜色必须不同）。

对于第二个测试用例，无论他们如何移动，都无法达到目标。