题目背景

小 Q 想在课上给女朋友传纸条，由于两人距离较远，纸条需经由同学代传。为了减少秘密泄露的风险，小 Q 希望经过的中间人数量越少越好。

题目描述

给定 $N$ 个人（编号 $1$ 到 $N$）之间的 $M$ 对双向朋友关系。小 Q 的编号为 $A$，其女朋友的编号为 $B$。

请计算：在所有可行的传递路径中，最少需要经过多少个中间人？

• 若 $A$ 与 $B$ 直接相邻，则中间人为 $0$；
• 若无法传达，则输出 $-1$。

输入格式

第一行包含两个整数 $N, M$，表示人数和朋友关系数。

第二行包含两个整数 $A, B$，表示起点和终点编号。

接下来 $M$ 行，每行两个整数 $u, v$，表示 $u$ 和 $v$ 之间可以传递纸条。

数据范围： $2 \leq N \leq 10^5$，$0 \leq M \leq \min \left\{ 10^5, \frac{N(N-1)}{2} \right\}$，$1 \leq A, B, u, v \leq N$。

输出格式

一个整数，表示最少的中间人数量。若不可达输出 $-1$。

样例

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

1

样例解释

从 1 到 5 的路径有：

• $1 \rightarrow 2 \rightarrow 3 \rightarrow 5$：中间人为 2, 3，共 2 人。
• $1 \rightarrow 4 \rightarrow 5$：中间人为 4，共 1 人。 最少中间人数为 1。by软工25王凯龙