D - Moving Pieces on Graph Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 700 点

問題文

頂点に 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 にある状態にすることです。

あなたが目的を達成することができるか判定し、目的を達成することができる場合は必要な操作回数の最小値を求めてください。

制約

  • 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
  • 入力される値は全て整数

入力

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

N M S T
u_1 v_1
u_2 v_2
\vdots
u_M v_M

出力

目的を達成することができない場合は -1 を出力せよ。

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

入力例 1

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

出力例 1

3

例えば以下のように操作することで、 3 回の操作で目的を達成することができます。

  • コマ A を頂点 2 に移動させる。
    • コマ A は頂点 2 に、コマ B は頂点 4 にある。
  • コマ B を頂点 3 に移動させる。
    • コマ A は頂点 2 に、コマ B は頂点 3 にある。
  • コマ A を頂点 4 に移動させる。
    • コマ A は頂点 4 に、コマ B は頂点 3 にある。

3 回未満の操作で目的を達成することはできないので、 3 を出力してください。

入力例 2

2 1 1 2
1 2

出力例 2

-1

どのように操作しても目的を達成することはできません。

入力例 3

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

出力例 3

4

Score : 700 points

Problem Statement

You are given a simple connected undirected graph with N vertices and M edges, where the vertices are numbered 1 to N and the edges are numbered 1 to M. Edge i connects vertex u_i and vertex v_i in both directions.

Initially, there is a piece A on vertex S and a piece B on vertex T. Here, S and T are given as input.

You may perform the following operation any number of times in any order:

  • Choose either piece A or piece B, and move it from its current vertex to an adjacent vertex via an edge. However, you cannot make a move that results in both pieces ending up on the same vertex.

Your goal is to reach the state in which piece A is on vertex T and piece B is on vertex S.

Determine whether this is possible, and if it is, find the minimum number of operations required to achieve it.

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
  • The given graph is simple and connected.
  • 1 \le S, T \le N
  • S \neq T
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

N M S T
u_1 v_1
u_2 v_2
\vdots
u_M v_M

Output

If it is impossible to achieve the goal, print -1.

If it is possible, print the minimum number of operations required.

Sample Input 1

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

Sample Output 1

3

For example, the following sequence of operations completes the goal in three moves:

  1. Move piece A to vertex 2.
    • Piece A is on vertex 2, piece B is on vertex 4.
  2. Move piece B to vertex 3.
    • Piece A is on vertex 2, piece B is on vertex 3.
  3. Move piece A to vertex 4.
    • Piece A is on vertex 4, piece B is on vertex 3.

It is impossible to complete the goal in fewer than three moves, so print 3.

Sample Input 2

2 1 1 2
1 2

Sample Output 2

-1

No matter how you move the pieces, you cannot achieve the goal.

Sample Input 3

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

Sample Output 3

4