Moloco의 Xayahh-Rakann (쉬움)

Moloco는 IT 회사지만, 일부 직원이 불안정한 암흑 물질 두 종류를 다루는 금지된 실험을 몰래 해 왔다. 이 직원들은 서로 떨어질 수 없는 연인이 나오는 오래된 전설에서 이름을 따 두 물질을 Xayahh-Rakann이라고 불렀다.

직원들이 만들어 낸 불안정한 암흑 물질은 모두 $n$ 단위이고, 각 단위는 1번부터 $n$번까지 번호가 붙은 통에 하나씩 담겨 있다.

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

통을 보관하던 건물에 리모델링이 예정되어 있다. 직원들은 리모델링 대상이 아닌 지하실에 통 정확히 $k$개를 남기고, 나머지 $n-k$개는 이 건물에서 멀리 떨어진 새 사무실로 옮기기로 했다. 문제는 분리 불가 쌍을 이루는 두 통이 서로 다른 건물에 놓이면 폭발한다는 점이다.

통을 크기 $k$인 무리와 크기 $n-k$인 무리로 안전하게 나눌 수 있는지 판정하라.

첫째 줄에 정수 $n$, $m$, $k$가 주어진다. ($1 \le n \le 20$, $1 \le k \le 10$, $1 \le m \le 100$)

다음 $m$개 줄에는 분리 불가 쌍을 이루는 두 통의 번호가 한 줄에 하나씩 주어진다. 한 줄에 있는 두 정수는 서로 다르고, 1 이상 $n$ 이하이다. $i+1$번째 줄은 $i$번째 분리 불가 쌍을 나타낸다. 같은 쌍이 두 번 이상 주어지기도 하고, $k$가 $n$보다 클 수도 있다.

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