分数: 500 点
问题陈述
有一个简单的无向图 N 顶点编号 1 通过 N 和 M 边编号 1 通过 M。 边缘 i 连接顶点 u_i 和顶点 v_i.
每个顶点都涂成红色或蓝色。 顶点颜色 i 表示为 C_i;顶点 i 被漆成红色,如果 C_i is 0 和蓝色如果 C_i is 1.
现在,高桥位于顶点 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- 第一个测试用例。
对于每个测试用例,打印 Takahashi 和 Aoki 同时到达顶点所需的最小移动次数 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-st 测试用例,Takahashi 和 Aoki 可以通过以下方式实现目标 3 移动,这是最小数量:
- 高桥移动到顶点 3,青木移动到顶点 2.
- 高桥移动到顶点 2,青木移动到顶点 3.
- 高桥移动到顶点 4,青木移动到顶点 1.
请注意,在 1-st 移动,不允许高桥和青木都移动到顶点 2 (因为高桥和青木移动到的顶点颜色一定不同。)
对于 2-第一种情况,无论他们如何行动,都无法达到目的。