AT_abc289_e [ABC289E] Swap Places

题目描述

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

此外，每个顶点都被涂成红色或蓝色之一。顶点 $i$ 的颜色用 $C_i$ 表示，若 $C_i=0$，则顶点 $i$ 被涂成红色，若 $C_i=1$，则被涂成蓝色。

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

两人可以重复进行如下操作 $0$ 次或多次：

• 两人同时移动到当前所在顶点相邻的某一个顶点。 但要求高桥君移动到的顶点颜色与青木君移动到的顶点颜色不同。

通过重复上述操作，能否让高桥君到达顶点 $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$。

输入输出样例 #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 \leq T \leq 1000$
• $2 \leq N \leq 2000$
• $1 \leq M \leq \min\left(\frac{N(N-1)}{2},\ 2000\right)$
• $C_i \in \{0, 1\}$
• $1 \leq u_i, v_i \leq N$
• 输入给出的图是简单图
• 输入的所有值均为整数
• 所有测试用例中 $N$ 的总和不超过 $2000$
• 所有测试用例中 $M$ 的总和不超过 $2000$

样例解释 1

对于第 1 个测试用例，高桥君和青木君可以按如下方式行动，在 $3$ 次操作内达到目标状态，且这是最小次数。

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

注意，在第 $1$ 次移动时，两人不能都移动到顶点 $2$。（因为高桥君和青木君移动到的顶点颜色必须不同。）

对于第 2 个测试用例，无论两人如何行动，都无法达到目标状态。

由 ChatGPT 4.1 翻译