AT_arc191_d [ARC191D] Moving Pieces on Graph

给定一个包含 $N$ 个顶点和 $M$ 条边的简单连通无向图。顶点编号为 $1$ 至 $N$，边编号为 $1$ 至 $M$。边 $i$ 双向连接顶点 $u_i$ 和顶点 $v_i$。 初始时，棋子 A 位于顶点 $S$，棋子 B 位于顶点 $T$（$S$ 和 $T$ 由输入给出）。 你可以按任意顺序执行以下操作任意次： - 选择棋子 A 或棋子 B，将其移动到当前顶点通过边直接连接的另一个顶点。**操作后，棋子 A 和 B 不能处于同一顶点**。 你的目标是将棋子 A 移动到顶点 $T$，同时将棋子 B 移动到顶点 $S$。 请判断是否可以达成目标。若可以，输出所需的最小操作次数；否则输出 $-1$。

输入通过标准输入给出，格式如下： > $N$ $M$ $S$ $T$ > $u_1$ $v_1$ > $u_2$ $v_2$ > $\vdots$ > $u_M$ $v_M$

若无法达成目标，输出 $-1$；否则输出所需的最小操作次数。

### 约束条件 - $2 \leq N \leq 2 \times 10^5$ - $N-1 \leq M \leq \min\left(\dfrac{N(N-1)}{2}, 2 \times 10^5\right)$ - $1 \leq u_i < v_i \leq N$ - 给定的图是简单且连通的 - $1 \leq S, T \leq N$ - $S \neq T$ - 输入均为整数 ### 样例解释 1 例如，通过以下操作可在 $3$ 次操作内达成目标： 1. 将棋子 A 移动到顶点 $2$（此时 A 在顶点 $2$，B 在顶点 $4$）。 2. 将棋子 B 移动到顶点 $3$（此时 A 在顶点 $2$，B 在顶点 $3$）。 3. 将棋子 A 移动到顶点 $4$（此时 A 在顶点 $4$，B 在顶点 $3$）。 由于无法在少于 $3$ 次操作内完成目标，因此输出 $3$。 ### 样例解释 2 无论以何种方式操作，均无法达成目标。 翻译由 DeepSeek R1 完成