交换位置

题目描述

有一个具有 $N$ 个顶点(编号为 $1$ 到 $N$)和 $M$ 条边(编号为 $1$ 到 $M$)的简单无向图。第 $i$ 条边连接顶点 $u_i$ 和顶点 $v_i$。

每个顶点被涂成红色或蓝色。顶点 $i$ 的颜色用 $C_i$ 表示;若 $C_i$ 为 $0$,则顶点 $i$ 为红色,若 $C_i$ 为 $1$,则为蓝色。

现在,高桥君在顶点 $1$,青木君在顶点 $N$。

他们可以重复以下移动零次或多次。

两人同时移动到各自当前顶点的一个相邻顶点。

此时,高桥君和青木君移动到的顶点的颜色必须不同。

通过重复上述移动,高桥君和青木君能否同时分别到达顶点 $N$ 和顶点 $1$?

如果可以,求所需的最少移动次数。如果不可能,输出 -1。

输入开头给出 $T$。请解决 $T$ 个测试用例。

输入格式

输入按以下格式从标准输入给出,其中 $\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。

样例

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 个测试用例,高桥君和青木君可以通过以下 $3$ 次移动达成目标,这也是最少的移动次数:

高桥君移动到顶点 $3$,青木君移动到顶点 $2$。

高桥君移动到顶点 $2$,青木君移动到顶点 $3$。

高桥君移动到顶点 $4$,青木君移动到顶点 $1$。

注意在第 1 次移动中,不允许高桥君和青木君都移动到顶点 $2$(因为两人移动到的顶点的颜色必须不同)。

对于第 2 个测试用例,无论他们如何移动,都无法达成目标。

数据范围

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