当前没有测试数据。

E - 交换位置

分数：$500$ 分

问题描述

给定一个有 $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。

input1
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

output1
3
-1
3

对于第 $1$ 个测试用例，高桥和青木可以通过以下 $3$ 步达到目标，这是最小移动次数：

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

需要注意的是在第 $1$ 步中，不允许高桥和青木同时移动到节点 $2$（因为高桥和青木移动到的节点的颜色必须不同）。

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