分数: 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
例如,以下操作序列可在三步内完成目标:
- 将棋子 A 移动到顶点 2.
- A 块位于顶点 2,块 B 位于顶点 4.
- 将块 B 移动到顶点 3.
- A 块位于顶点 2,块 B 位于顶点 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