追記

• 8/21 15:47: テストケースの修正、及び想定解の修正を行いました。

AC報酬: $25$ ラテコイン

Story

🌋

matcharate君は火山が活発な惑星 "VolNo" に到着しました。
この惑星は年中火山が活動をしており、ずっと火山活動による隕石が降り積もるといった、なんとも熱い星です。

今、この惑星は危機に瀕しています。それは、とても巨大な隕石が降り注ぐ危険性があったのです。それにより親友のMagenrate君の街が消えてしまいそうになっているのです。
matcharate君は虫の知らせを聞き、急いで助けに行こうと思ったのです。

この惑星の火山監視局 "VolNo-Attention" によると、どの街に巨大隕石が降りかかってくるか予測できます。
この予測をもとにmatcharate君は、あと何分後にその街が通れなくなるか計算することにしました。

問題

$N$ 個の街と $M$ 本の道からなる王国があります。街にはそれぞれ $1,2,...,N$ と番号づけられており、$i\ (1\le i\le M)$ 本目の道を使うことで街 $A_i,B_i$ を行き来することができます。

今から次のアクシデントが $1$ 分おきに $1$ 回、全体で $Q$ 回だけ発生します。

• 街 $q_j$ に隕石が落下し、街 $q_j$ が通れなくなる。これにより頂点 $q_j$ とつながれた道は全て封鎖され、その道を使うことはできなくなる

すべてのアクシデントが終わった後、街 $S$ から道をたどって街 $T$ にたどり着くことは可能ですか？
可能でないならば、たどり着くことが初めて不可能になるのはイベントが起こり始めて何分後の時点か求めてください。

入力

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

制約

• $4\le N\le 10^4$
• $1\le M\le \min(\frac{N(N-1)}{2},10^4)$
• $1\le S,T\le N$
• $S\ne T$
• $1\le A_i\lt B_i\le N$
• $i\ne j\Rightarrow (A_i,B_i)\ne (A_j,B_j)$
• $0\le Q\le 10^3$
• $1\le q_j\le N\ (1\le j\le Q)$
• $q_j\ne S$
• $q_j\ne T$

出力

次にしたがって出力せよ。

• すべてのイベントが終わってもたどり着くことができるなら Reachable を出力せよ。
  不可能ならば、何分後に初めてたどり着けなくなるか、その分数 $t\ (0\le t\le Q)$ を出力せよ。
  ただし、イベントが始まる前の時点でたどり着くのが不可能ならば $t=0$ とする。

入出力例

8 9 1 8
1 2
1 3
1 4
2 5
3 4
4 6
4 7
5 6
7 8
4
6
5
4
3

3

$3$ 分後の時点で街 $4,5,6$ が通れなくなります。このときどうやっても街 $8$ にたどり着くことはできません。よって答えは $3$ となります。

5 3 1 5
1 3
3 4
3 5
0

Reachable

一回もアクシデントが発生しないこともあります。

5 2 1 5
1 3
3 4
0

0

最初からたどり着けないこともあります。

追記: $q_j$ が重複していることがあるケースに注意してください。