Xayahh-Rakann at Moloco (Easy)

Moloco is an IT company, but a few of its employees have been running forbidden experiments on two kinds of unstable dark matter. They named the two kinds Xayahh-Rakann after an old legend about a couple who cannot be separated.

The employees produced $n$ units of unstable dark matter. Each unit sits in its own jar, and the jars are labeled 1 through $n$.

After many experiments they found that certain pairs of jars must not be placed far apart. If such a pair is separated, the matter becomes unstable enough to explode and wipe out the planet. Those pairs are called inseparable pairs, and the employees identified $m$ of them. Every other pair is safe at any distance.

A renovation is scheduled for the building that currently stores the jars. The employees will keep exactly $k$ jars in the basement, which the renovation does not touch, and move the other $n-k$ jars to a new office far from that building. If the two jars of an inseparable pair end up in different buildings, they explode.

Decide whether the jars can be split into a group of size $k$ and a group of size $n-k$ safely.

The first line contains three integers $n$, $m$, and $k$. ($1 \le n \le 20$, $1 \le k \le 10$, $1 \le m \le 100$)

Each of the next $m$ lines contains the labels of the two jars that form one inseparable pair. The two integers on a line are different and lie between 1 and $n$. Line $i+1$ describes the $i$th inseparable pair. The same pair may be given more than once, and $k$ may be larger than $n$.

Print SAFE on the first line if the jars can be split safely into a group of $k$ jars and a group of $n-k$ jars. Otherwise print DOOMED.