006 - Encount

問題

$N \ $頂点$ \ M \ $辺のグラフがあります。$i \ (1 \leq i \leq M) \ $番目の辺は頂点$ \ a_i \ $と頂点$ \ b_i \ $を双方向に結びます。

このゲームでは、$2 \ $人のプレイヤーがそれぞれ異なる頂点に駒を置きスタートします。
ターン毎に$ \ 2 \ $人は隣接する頂点に駒を同時に動かします。駒を動かさないことはできません。

$2 \ $人の駒が同じ頂点にたどり着いた時点でゲームは終了します。

山本君と山田君がそれぞれ頂点$ \ X \ $と頂点$ \ Y \ $に駒を置いてゲームを開始します。互いが出来るだけ早くゲームが終わるように駒を動かしたとき、このゲームは最短で何ターンで終了するでしょうか？
ただし、$2 \ $人がどのように駒を動かしてもゲームが終了しない場合は$ \ -1 \ $を出力してください。

入力

入力は以下の形式で標準入力から与えられる

$N \ M \ X \ Y$
$a_1 \ b_1$
$a_2 \ b_2$
$\vdots$
$a_M \ b_M$

出力

ゲームが終わるのにかかる最小のターン数を出力せよ。ただし、$2 \ $人がどのように駒を動かしても永遠にゲームが終了しない場合は$ \ -1 \ $を出力せよ。
出力の末尾には改行を入れること。

制約

• $2 \leq N \leq 2 \times 10^5$
• $1 \leq M \leq \min(2 \times 10^5, \frac{N \times (N - 1)}{2})$
• $1 \leq a_i,b_i \leq N$
• $1 \leq X,Y \leq N$
• $X \neq Y$
• 与えられるグラフは連結かつ単純である
• 入力は全て整数である

入出力例

入力例1

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

出力例1

2

$1 \ $ターン目では、山本君は頂点$ \ 2 \ $に、山田君は頂点$ \ 3 \ $に駒を動かします。
$2 \ $ターン目には$ \ 2 \ $人とも頂点$ \ 4 \ $に駒を動かすことでゲームは終了します。
$1 \ $ターン以内に終わらせることはできないため$ \ 2 \ $を出力します。

入力例2

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

出力例2

-1