問題にチャレンジして、ユーザー同士で解答を教え合ったり、コードを公開してみよう!
多重辺・自己ループのない無向グラフを構成する 1 〜 N の番号がつけられた頂点とそれらを結ぶ M 本の辺の情報と頂点番号 X, Y が与えられるので、頂点 X から 頂点 Y までの距離を出力してください。
また、頂点 X から頂点 Y までの経路が存在しない場合はそのことを指摘してください。
なお、辺の重みは全て 1 であるものとし、グラフの 2 頂点 X, Y 間の距離とは、頂点 X から頂点 Y までを最短経路で移動したときに通る辺の数のことを指すものとします。
N M X Y
a_1 b_1
...
a_M b_M
頂点 X から 頂点 Y までの距離を出力してください。
ただし、頂点 X から 頂点 Y まで到達することができない場合は -1 を出力してください。
すべてのテストケースにおいて、以下の条件をみたします。
・1 ≦ N ≦ 100,000
・1 ≦ M ≦ min(N*(N-1)/2, 100,000)
・1 ≦ X ≦ N
・1 ≦ Y ≦ N
・X ≠ Y
・1 ≦ a_i, b_i ≦ N (1 ≦ i ≦ M)
・a_i ≠ b_i (1 ≦ i ≦ M)
5 6 1 5
1 2
2 3
1 4
2 4
2 5
5 3
2
3 1 1 3
1 2
-1