题目 A：职场体验 (Job Shadowing)

题目描述

Anathi 和 Beatrice 在 Caspian 公司进行职场体验。不幸的是，他们在白天走散了，现在想尽快找到对方分享所学。

Caspian 公司的办公室由 $N$ 个房间组成（编号 $1$ 到 $N$），房间之间由 $M$ 条走廊连接。Anathi 最初在房间 $A$，Beatrice 最初在房间 $B$。已知办公室的布局，请确定他们应该在哪个房间会合，以使两人中到达时间较长的那个人所花的时间最短。两人从一个房间走到相邻房间都需要 1 分钟。

输入格式

• 第一行包含四个整数：$N$ ($1 \le N \le 10^4$)，$M$ ($0 \le M \le \frac{N(N-1)}{2}$)，$A$ 和 $B$ ($1 \le A, B \le N$)。
• 接下来 $M$ 行，每行包含两个整数 $p_i$ 和 $q_i$ ($1 \le p_i, q_i \le N$)，表示房间 $p_i$ 和 $q_i$ 之间有一条走廊。
• 保证没有自环和重边。

输出格式

• 输出一个整数，表示他们应该会合的房间编号。
• 如果有多个房间都能实现最短时间，输出编号最小的那个。
• 如果两人无法会合，输出 -1。

样例

输入 1

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

输出 1

1

输入 2

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

输出 2

3