← 返回题目列表

AtCoder · arc191_d

D. 在图表上移动棋子

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

分数: 700 点

问题陈述

给你一个简单的连通无向图 N 顶点和 M 边,其中顶点编号 1 to N 且边缘已编号 1 to M。边缘 i 连接顶点 u_i 和顶点 v_i 两个方向。

最初,顶点有一块 A S 和顶点上的一块 B T。在这里, S 和 T 作为输入给出。

您可以按任意顺序执行以下操作任意次数:

  • 选择块 A 或块 B,并通过边将其从当前顶点移动到相邻顶点。但是,您无法进行导致两个棋子最终位于同一顶点的移动。

你的目标是达到 A 块位于顶点的状态 T 且 B 块位于顶点 S.

确定这是否可能,如果可能,则找到实现它所需的最少操作数。

约束

  • 2 \le N \le 2\times 10^5
  • \displaystyle N-1 \le M \le \min\left(\frac{N(N-1)}{2},\,2\times 10^5\right)
  • 1 \le u_i < v_i \le N
  • 给定的图很简单且连通。
  • 1 \le S, T \le N
  • S \neq T
  • 所有输入值均为整数。

输入

输入由标准输入按以下格式给出:

N M S T
u_1 v_1
u_2 v_2
\vdots
u_M v_M

输出

如果无法实现目标,则打印 -1.

如果可能,请打印所需的最少操作数。


示例输入 1

4 4 3 4
2 4
1 4
3 4
2 3

示例输出 1

3

例如,以下操作序列可在三步内完成目标:

  1. 将棋子 A 移动到顶点 2.
    • A 块位于顶点 2,块 B 位于顶点 4.
  2. 将块 B 移动到顶点 3.
    • A 块位于顶点 2,块 B 位于顶点 3.
  3. 将棋子 A 移动到顶点 4.
    • A 块位于顶点 4,块 B 位于顶点 3.

不可能在少于三步的时间内完成目标,所以打印 3.


示例输入 2

2 1 1 2
1 2

示例输出 2

-1

无论你如何移动棋子,你都无法达到目标。


示例输入 3

5 6 3 5
1 2
2 3
1 5
2 4
1 3
2 5

示例输出 3

4