Xayahh-Rakann at Moloco (Hard)

Moloco is an IT company, but a few of its employees ran forbidden experiments on two kinds of unstable dark matter. They named the pair Xayahh-Rakann after an old legend about a couple who could never be apart.

The employees produced $n$ units of unstable dark matter, and each unit sits in its own jar. The jars are labeled $1, 2, \dots, n$.

After many experiments they learned that some pairs of Xayahh-Rakann must not be kept far apart. A pair that is separated becomes unstable, explodes, and wipes out the whole planet. Such a pair of jars is called an inseparable pair, and the employees found $m$ of them. Every other pair of jars is safe at any distance.

The building that stores the jars right now is scheduled for renovation. The employees decided to leave exactly $k$ jars in the basement, which the renovation does not touch, and to move the other $n-k$ jars to a new office far away. The catch is that an inseparable pair placed in two different buildings explodes and takes the planet with it.

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

The first line contains three integers $n$, $m$, and $k$ ($1 \le n \le 1000$, $1 \le k \le 1000$, $1 \le m \le 1000000$). Note that $k$ can be larger than $n$.

Each of the next $m$ lines contains two integers that describe one inseparable pair of jars. 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 can appear more than once, with the two numbers in either order.

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