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를 회신 부탁드리겠습니다!

두 번째 줄에는 $X$, $Y$, $Z$가 공백으로 구분되어 주어진다. $(X \neq Y; Y \neq Z; Z \neq X)$

세 번째 줄부터 $M$개의 줄에 걸쳐 $a$, $b$가 공백으로 주어진다. 이는 $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