# Asakura's Chase

The following problem is adapted from the LCC Placement Challenge, question 9. Details on output formats and test cases for Brilliant are given at the bottom of the challenge.

Ryoko Asakura has used her space-warping powers to turn a classroom into a battlefield. For some reason, things no longer follow the rules of Euclidean geometry; you can walk between two desks and possibly end up at the other end of the room! Kyon has been caught in this pocket dimension, and needs to stall while he waits for help to arrive. If Asakura is moving to catch Kyon, while Kyon runs away, will he be able to evade her indefinitely?

More formally, you are given a graph $$G$$. The starting positions on the graph,$$K_{(yon)}$$ and $$A_{(sakura)}$$ will be decided by the players at the start. $$A$$ chooses her starting desk, followed by $$K$$. Starting with $$A$$ and alternating each round, the active player may choose to move from a desk to any connected desk on $$G$$. $$G$$ is assumed to be reflexive--that is to say, a player may choose to stay at a desk instead of moving. Assuming that $$K$$ plays optimally, is there a finite series of moves that allows $$A$$ to catch $$K$$?

## Input

The first line will contain two integers, $$N$$ and $$M$$, the number of nodes and edges respectively. $$M$$ lines will follow.

Each following line will contain two integers, $$u, v$$, indicating an edge $$uv$$ on $$G$$.

$$1 \le N \le 1000$$

$$1 \le M \le N(N+1)/2$$

$$1 \le u, v \le N$$

## Output

If a finite series of moves exists that allow Asakura to catch up to Kyon ($$A = K$$ under optimal play for $$K$$), print

Kyon is doomed!


Otherwise, print

Safe!


## Sample Input 1

6 6
1 2
2 3
3 4
4 5
5 6
6 1


## Sample Input 2

7 7
1 3
2 3
3 4
4 7
7 5
5 6
6 7


## Output for Sample Input 1

Safe!


## Output for Sample Input 2

Kyon is doomed!


## Explanation for Sample Input 1

Here is what the classroom looks like:

img

Asakura might choose to start at desk 1. Kyon then chooses any desk other than 6 or 2 (say, 3). On her first turn, Asakura moves to desk 2. Kyon responds by moving to desk 4. In this way, he can continue to move to evade Asakura indefinitely.

## Explanation for Sample Input 2

Here is what the classroom looks like:

img

Asakura might choose to start at desk 4. Kyon then chooses any desk, say 5. On her first turn, Asakura moves to desk 7. Kyon can choose to stay still or move to desk 6. Either way, Asakura catches him next turn.

For our purposes, we will consider the set of 11 test cases here. Each test case is given consecutively, without any separation from the others, subject to the input format described above. Note that the first two cases are the samples. Your answer will be the number of cases in which Kyon is captured by Asakura.

×