「Nuko」と呼ばれるユニークで謎めいた種が、世界の辺境にある諸島に生息しています。この諸島は $N$ 個の島（$0$ から $N - 1$ まで番号付けされている）とそれらを結ぶ $M$ 本の橋でモデル化できます。各橋 $i$ は、$0 \leq i \leq M - 1$ について、2つの島 $U[i]$ と $V[i]$ を双方向に結んでいます。どの島からどの島へも到達可能です。各橋は異なる2つの島を結んでおり、同じ2つの島を結ぶ橋は複数存在しません。

古代、Nukoは島 $0$ にのみ生息していました。しかし、長い年月を経て、Nukoはすべての島に広がりました。Nukoの集団がある橋を渡って新しい島へ移動するたびに、彼らは進化し、前の島とは異なる亜種になります。具体的には、島 $j$（$0 \leq j \leq N - 1$）にいるNukoの亜種 $s_j$ は、島 $0$ から島 $j$ に到達するために渡らなければならない橋の最小数と等しくなります。例えば、島 $0$ にいるNukoの亜種は $0$ です。

あなたは、橋を使って島 $A$ から島 $B$ へ旅をする旅行者です。$A \neq B$ であることが保証されています。ある島にいるとき、あなたは必然的にそこに住むNukoの亜種に遭遇します。各亜種には独自の習慣があり、異なる習慣に適応することは厄介であるため、あなたの目標は、遭遇するNukoの亜種の種類数を最小化するような経路を選択することです。

島 $A$ から島 $B$ へ移動する際に遭遇するNukoの亜種の種類数の最小値を求めてください。

実装の詳細

以下のプロシージャを実装してください。

int min_distinct(int N, int M, int A, int B, std::vector<int> U, std::vector<int> V)

• $N$: 島々の数。
• $M$: 橋の数。
• $A$: 旅の出発点。
• $B$: 旅の終着点。
• $U, V$: 橋を表す長さ $M$ の配列。
• このプロシージャは、遭遇するNukoの亜種の種類数の最小値を返す必要があります。

制約

• $2 \le N \le 5\,000\,000$
• $1 \le M \le 5\,000\,000$
• $0 \le A, B \le N - 1$
• $A \neq B$
• $0 \le U[i], V[i] \le N - 1$ （すべての $0 \leq i \leq M - 1$ について）
• $U[i] \neq V[i]$ （すべての $0 \leq i \leq M - 1$ について）
• $(U[i], V[i]) \neq (U[j], V[j])$ かつ $(U[i], V[i]) \neq (V[j], U[j])$ （すべての $i \neq j$ について）
• どの島からどの島へも到達可能であることが保証されている。

小課題

1. (4点) $A = 0$, $N \le 100\,000$, $M \le 100\,000$
2. (4点) $M = N - 1$, $N \le 100\,000$, $M \le 100\,000$
3. (6点) $N \le 300$, $M \le 300$
4. (8点) $N \le 4\,000$, $M \le 4\,000$
5. (22点) $N \le 4\,000$, $M \le 1\,000\,000$
6. (14点) $N \le 100\,000$, $M \le 100\,000$
7. (5点) $N \le 300\,000$, $M \le 300\,000$
8. (5点) $N \le 500\,000$, $M \le 500\,000$
9. (32点) 追加の制約なし

注記: 小課題9については、グレーダーのみで制限時間4500msのうち1500msを消費することが保証されています。

入出力例

入力 1

min_distinct(5, 5, 2, 4, [0, 1, 2, 3, 4], [1, 2, 3, 4, 0])

出力 1

2

注記

島々は以下のように図示でき、異なる網掛けが異なるNukoの亜種を表しています。

The islands can be illustrated as below, with different shading representing different Nuko subspecies.

例1において、最適な経路は $2-3-4$ です。遭遇するNukoの亜種は $1$ と $2$ です。したがって、この呼び出しは $2$ を返す必要があります。

入力 2

min_distinct(8, 9, 4, 7, [0, 0, 0, 1, 1, 2, 2, 6, 7], [1, 2, 3, 4, 5, 5, 6, 3, 3])

出力 2

2

注記

島々は以下のように図示でき、異なる網掛けが異なるNukoの亜種を表しています。

The islands can be illustrated as below, with different shading representing different Nuko subspecies.

例2において、最適な経路は $4-1-5-2-6-3-7$ です。遭遇するNukoの亜種は $1$ と $2$ です。したがって、この呼び出しは $2$ を返す必要があります。

入力 3

min_distinct(15, 17, 3, 7,
              [0, 1, 2, 3, 4, 13, 12, 12, 11, 10, 10, 9, 8, 7, 6, 8, 0],
              [1, 2, 3, 4, 13, 12, 1, 11, 10, 9, 5, 8, 7, 6, 5, 14, 14])

出力 3

3

注記

例3において、島 $3$ から島 $7$ へ移動する際に遭遇するNukoの亜種の種類数の最小値は $3$ です。したがって、この呼び出しは $3$ を返す必要があります。

サンプルグレーダー

入力形式:

N M A B
U[0] V[0]
U[1] V[1]
...
U[M - 1] V[M - 1]

出力形式:

min_distinct の戻り値を表す整数。