Burning Love

[A few minutes later]

Sensei, Wakamo, the Fox of Calamity, has escaped from the Corrections Bureau and is heading to Schale, where you are. We in the Public Safety Bureau intend to reach Schale as quickly as possible to protect you, and arrest Wakamo immediately if we find her on the way.

For ease of command, we will represent the city as $N$ districts and $M$ roads.

• The districts (vertices) are numbered $1$ through $N$.

  • Wakamo is initially in district $X$.
  • The Public Safety Bureau is initially in district $Y$.
  • Schale is in district $Z$.

• The roads (edges) are numbered $1$ through $M$.

  • Each road can be traveled in both directions.
  • Every road takes the same amount of time to traverse.
  • The Public Safety Bureau has blocked road $K$, so Wakamo cannot use road $K$.

We in the Public Safety Bureau will search for Wakamo as we travel, in order to arrest her!

• The Public Safety Bureau travels from district $Y$ to district $Z$ only along shortest paths. Here, a shortest path is a path with the minimum travel time among all possible paths.

• We search along every possible shortest path. In other words, every district that belongs to at least one shortest path from $Y$ to $Z$ is searched.

  • When the Public Safety Bureau enters a district $v$, it begins searching; when it leaves district $$, the search there ends.

However, Wakamo will also move so as to evade us.

• Wakamo, too, travels from district $X$ to district $Z$ only along shortest paths.
• Wakamo knows the real-time locations of the Public Safety Bureau as well as which road is blocked. Therefore, among all shortest paths from $X$ to $Z$, she chooses a route that avoids arrest whenever possible.

Given the importance and confidentiality of the operation, we will use code phrases. If you determine that the Public Safety Bureau can arrest Wakamo, or that she cannot reach Schale under any circumstances, please reply with GIVE ME CHOCO. Conversely, if you determine that Wakamo can reach Schale first without being arrested and reinforcements are needed, please reply with Burning Love!

The second line contains $X$, $Y$, and $Z$, separated by spaces. $(X \neq Y; Y \neq Z; Z \neq X)$

The next $M$ lines, starting with the third line, each contain $a$ and $b$, separated by a space. The $i$-th of these lines means that road $i$ connects districts $a$ and $b$. No road is given more than once. $(1 \le i \le M$; $a \neq b$; $1 \le a, b \le N)$

It is guaranteed that district $Z$ is reachable from district $Y$.

It is guaranteed that district $Z$ would be reachable from district $X$ if Wakamo were allowed to use road $K$.

Time limit

1000 ms

Memory limit

1024 MB

Checker

CUSTOM