Swap Places

题目描述

有一个无向简单图，包含编号为 $1$ 到 $N$ 的 $N$ 个顶点和编号为 $1$ 到 $M$ 的 $M$ 条边。边 $i$ 连接顶点 $u_i$ 和顶点 $v_i$。
每个顶点被涂成红色或蓝色。顶点 $i$ 的颜色由 $C_i$ 表示；若 $C_i$ 为 $0$ 则顶点 $i$ 为红色，若 $C_i$ 为 $1$ 则为蓝色。 现在，Takahashi 在顶点 $1$，Aoki 在顶点 $N$。
他们可以重复以下动作零次或多次。

两人同时各自移动到与当前顶点相邻的某个顶点。
此处，Takahashi 与 Aoki 移动到的两个顶点的颜色必须不同。

通过重复上述移动，Takahashi 和 Aoki 能否同时最终分别到达顶点 $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$ 个测试用例的答案。
对于每个测试用例，若 Takahashi 和 Aoki 可以同时分别到达顶点 $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 \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$ 个测试用例，Takahashi 和 Aoki 可以通过下面的 $3$ 次移动实现目标，且这是最少的：

Takahashi 移到顶点 $3$，Aoki 移到顶点 $2$。 Takahashi 移到顶点 $2$，Aoki 移到顶点 $3$。 Takahashi 移到顶点 $4$，Aoki 移到顶点 $1$。

注意在第 $1$ 次移动中，不允许两人都移动到顶点 $2$（因为 Takahashi 与 Aoki 移动到的顶点颜色必须不同）。 对于第 $2$ 个测试用例，无论如何移动，他们都不能实现目标。

标签: AtCoder|abc289E

来源

AtCoder|abc289E