102894: [Atcoder]ABC289 E - Swap Places

Problem Statement

There is a simple undirected graph with $N$ vertices numbered $1$ through $N$ and $M$ edges numbered $1$ through $M$. Edge $i$ connects vertex $u_i$ and vertex $v_i$.
Every vertex is painted either red or blue. The color of vertex $i$ is represented by $C_i$; vertex $i$ is painted red if $C_i$ is $0$ and blue if $C_i$ is $1$.

Now, Takahashi is on vertex $1$ and Aoki is on vertex $N$.
They may repeat the following move zero or more times.

• Each of the two simultaneously moves to a vertex adjacent to the current vertex.
  Here, the vertices that Takahashi and Aoki move to must have different colors.

By repeating the move above, can Takahashi and Aoki simultaneously end up on vertices $N$ and $1$, respectively?
If it is possible, find the minimum number of moves required. If it is impossible, print -1.

You are given $T$ at the beginning of the input. Solve the problem for $T$ test cases.

Constraints

• $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$
• The graph given in the input is simple.
• All values in the input are integers.
• The sum of $N$ over all test cases does not exceed $2000$.
• The sum of $M$ over all test cases does not exceed $2000$.

Input

The input is given from Standard Input in the following format, where $\text{test}_i$ denotes the $i$-th test case:

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

Each test case is given in the following format:

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

Output

Print $T$ lines. The $i$-th line should contain the answer to the $i$-th test case.
For each test case, print the minimum number of moves required for Takahashi and Aoki to simultaneously end up in vertices $N$ and $1$, respectively, if it is possible, and -1 otherwise.

Sample Input 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

Sample Output 1

3
-1
3

For the $1$-st test case, Takahashi and Aoki can achieve the objective by making the following $3$ moves, which is the minimum number:

• Takahashi moves to vertex $3$, and Aoki moves to vertex $2$.
• Takahashi moves to vertex $2$, and Aoki moves to vertex $3$.
• Takahashi moves to vertex $4$, and Aoki moves to vertex $1$.

Note that in the $1$-st move, it is disallowed that both Takahashi and Aoki move to vertex $2$ (because the colors of vertices that Takahashi and Aoki move to must be different.)

For the $2$-nd case, no matter how they move, they cannot achieve the objective.

问题描述

有一个简单的无向图，有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

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

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

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

对于第2个测试用例，无论他们如何移动，都无法实现目标。