Moloco의 Xayahh-Rakann (Hard)

Moloco는 IT 회사지만, 몇몇 직원이 금지된 실험을 저질렀다. 실험에 쓴 것은 불안정한 암흑 물질 두 종류였고, 직원들은 결코 떨어질 수 없는 연인의 옛 전설을 따서 이 물질에 Xayahh-Rakann이라는 이름을 붙였다.

직원들이 만들어 낸 불안정한 암흑 물질은 $n$개이고, 하나씩 따로 항아리에 담겨 있다. 항아리에는 $1, 2, \dots, n$번이 붙어 있다.

실험을 여러 번 거친 끝에, 어떤 Xayahh-Rakann 쌍은 서로 멀리 떨어뜨리면 안 된다는 사실이 드러났다. 떨어뜨리면 불안정해져 폭발하고 행성 전체가 사라진다. 이런 항아리 쌍을 분리 불가 쌍이라 부르고, 직원들은 그런 쌍을 $m$개 찾아냈다. 나머지 쌍은 아무리 멀리 떨어뜨려도 안전하다.

하필 지금 항아리를 보관하는 건물에 리모델링이 예정되어 있다. 직원들은 리모델링 대상이 아닌 지하실에 항아리 $k$개를 남기고, 나머지 $n-k$개는 멀리 떨어진 새 사무실로 옮기기로 했다. 문제는 분리 불가 쌍이 서로 다른 건물에 놓이면 폭발해 행성을 날려 버린다는 점이다.

항아리를 $k$개짜리 무리와 $n-k$개짜리 무리로 안전하게 나눌 수 있는지 판정하라.

첫째 줄에 정수 $n$, $m$, $k$가 주어진다. ($1 \le n \le 1000$, $1 \le k \le 1000$, $1 \le m \le 1000000$) $k$가 $n$보다 클 수도 있다.

다음 $m$개 줄에는 분리 불가 쌍이 한 줄에 하나씩 주어진다. 한 줄의 두 정수는 서로 다르고 $1$ 이상 $n$ 이하이다. $i+1$번째 줄이 $i$번째 분리 불가 쌍을 나타낸다. 같은 쌍이 순서만 바뀌어 여러 번 주어질 수도 있다.

항아리를 $k$개와 $n-k$개로 안전하게 나눌 수 있으면 첫째 줄에 SAFE를, 그렇지 않으면 DOOMED를 출력한다.