AT_arc191_d [ARC191D] Moving Pieces on Graph

頂点に $ 1 $ から $ N $ の番号が、辺に $ 1 $ から $ M $ の番号が付いた $ N $ 頂点 $ M $ 辺の単純連結無向グラフが与えられます。辺 $ i $ は頂点 $ u_i $ と頂点 $ v_i $ を双方向に結んでいます。 はじめ、コマ A が頂点 $ S $ に、コマ B が頂点 $ T $ にあります。ここで、 $ S,T $ は入力として与えられます。 あなたは以下の操作を好きな順序で好きな回数行うことができます。 - コマ A かコマ B のどちらかを選び、そのコマを今の頂点から辺で結ばれた頂点に移動させる。ただし、操作後にコマ A とコマ B が同じ頂点に来るような操作はできない。 あなたの目的はコマ A が頂点 $ T $ に、コマ B が頂点 $ S $ にある状態にすることです。 あなたが目的を達成することができるか判定し、目的を達成することができる場合は必要な操作回数の最小値を求めてください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ M $ $ S $ $ T $ $ u_1 $ $ v_1 $ $ u_2 $ $ v_2 $ $ \vdots $ $ u_M $ $ v_M $

目的を達成することができない場合は $ -1 $ を出力せよ。 目的を達成することができる場合は必要な操作回数の最小値を出力せよ。

### Sample Explanation 1 例えば以下のように操作することで、 $ 3 $ 回の操作で目的を達成することができます。 - コマ A を頂点 $ 2 $ に移動させる。 - コマ A は頂点 $ 2 $ に、コマ B は頂点 $ 4 $ にある。 - コマ B を頂点 $ 3 $ に移動させる。 - コマ A は頂点 $ 2 $ に、コマ B は頂点 $ 3 $ にある。 - コマ A を頂点 $ 4 $ に移動させる。 - コマ A は頂点 $ 4 $ に、コマ B は頂点 $ 3 $ にある。 $ 3 $ 回未満の操作で目的を達成することはできないので、 $ 3 $ を出力してください。 ### Sample Explanation 2 どのように操作しても目的を達成することはできません。 ### Constraints - $ 2\le N\le 2\times 10^5 $ - $ \displaystyle N-1\le M\le \min\left(\frac{N(N-1)}2,2\times 10^5 \right) $ - $ 1\le u_i < v_i\le N $ - 与えられるグラフは単純かつ連結 - $ 1\le S,T\le N $ - $ S\neq T $ - 入力される値は全て整数