← 返回题目列表

AtCoder · abc289_e

H. 交换位置

中文机器翻译题面 查看原题

分数: 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-第一种情况,无论他们如何行动,都无法达到目的。