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 \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 翻译