Burning Love

先生、災厄の狐ワカモが矯正局を脱走し、先生のいらっしゃるシャーレへ向かっています。私たち生活安全局はできるだけ早くシャーレへ向かって先生をお守りし、移動中にワカモを発見したら直ちに逮捕するつもりです。

指揮を取りやすくするため、街を $N$ 個の区域と $M$ 本の道路で表すことにします。

• 区域（頂点）には $1$ から $N$ までの番号が付いています。

  • ワカモは最初、区域 $X$ にいます。
  • 生活安全局は最初、区域 $Y$ にいます。
  • シャーレは区域 $Z$ にあります。

• 道路（辺）には $1$ から $M$ までの番号が付いています。

  • 道路は双方向に移動できます。
  • どの道路も通過にかかる時間は同じです。
  • 道路 $K$ は生活安全局が封鎖しているため、ワカモは道路 $K$ を通れません。

私たち生活安全局はワカモを逮捕するため、移動と捜索を同時に行います！

• 生活安全局は区域 $Y$ から区域 $Z$ へ、最短経路だけを通って移動します。最短経路とは、通行可能な経路のうち移動時間が最小の経路です。

• 考えられるすべての最短経路を捜索します。つまり、$Y$ から $Z$ への最短経路の少なくとも一つに含まれる区域は、すべて捜索対象です。

  • 生活安全局がある区域 $v$ に入ると捜索を開始し、その区域 $v$ を離れると捜索を終了します。

ただし、ワカモも私たちを避けて移動するはずです。

• ワカモも区域 $X$ から区域 $Z$ へ、最短経路だけを通って移動します。
• ワカモは生活安全局の現在位置も、封鎖した道路の位置も把握しています。そのため、$X$ から $Z$ へのすべての最短経路の中から、可能な限り逮捕を避けられる経路を選びます。

作戦の重要性と機密性を考慮し、暗号文を使用します。私たち生活安全局がワカモを逮捕できる、またはワカモがどうしてもシャーレに到達できないと判断された場合は、GIVE ME CHOCO と返信してください。反対に、ワカモが逮捕されずに先にシャーレへ到着でき、増援が必要だと判断された場合は、Burning Love と返信をお願いします！

2 行目に $X$, $Y$, $Z$ が空白区切りで与えられる。$(X \neq Y; Y \neq Z; Z \neq X)$

3 行目からの $M$ 行には、それぞれ $a$, $b$ が空白区切りで与えられる。このうち $i$ 行目は、道路 $i$ が区域 $a$ と区域 $b$ を結ぶことを表す。同じ道路が $2$ 回以上与えられることはない。$(1 \le i \le M$; $a \neq b$; $1 \le a, b \le N)$

区域 $Y$ から区域 $Z$ には必ず到達できる。

ワカモが道路 $K$ を通れると仮定すれば、区域 $X$ から区域 $Z$ には必ず到達できる。

実行時間制限

1000 ms

メモリ制限

1024 MB

チェッカー

CUSTOM