시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 256 MB93128724131.669%

문제

지금으로부터 527년이 지난 서기 2544년, 항성 간 이동이 가능해진 인류는 태양계가 아닌 새로운 보금자리를 찾아 기술의 집약체인 CTP(Cho Technology Planet, 초 기술 행성)를 건설한다. 인공지능이 관리하는 CTP 안에서는 자연재해도 전쟁도 없었으며 많은 사람이 행복을 누리며 살아나갔다.

CTP에는 N개의 도시가 있는데 각각의 도시들은 1번부터 N번까지 고유한 번호를 가지고 있으며 각 도시들끼리는 매우 빠른 속도로 이동할 수 있는 튜브로 연결되어 있다. 단 튜브는 매우 빠른 속도로 이동해야 하기 때문에 한 방향으로만 이동을 할 수 있다. 즉 A도시에서 B도시로 이동하는 튜브가 있다고 해서 B도시에서 A도시로 이동하는 튜브가 항상 존재하는 것은 아니다. 또한 튜브 안에서는 매우 빠른 속도로 이동이 가능하기 때문에 두 도시가 아무리 멀리 떨어져 있어도 이동하는 시간은 무시할만큼 적게 든다.

모든 사람들의 유토피아 CTP는 어느 날 우주급 빌런 재유니스의 침공으로 건설 이래 최대 위기에 직면한다. 재유니스는 N개의 도시 중 한 도시에 CTP를 한 번에 파괴할 수 있는 위력의 반물질 폭탄을 설치하고 사라진다. CTP를 구하기 위해서는 반물질 폭탄을 N번 도시에 있는 항성 간 이동장치를 통해 블랙홀로 보내야 한다. 가장 이상적인 방법은 반물질 폭탄이 있는 도시에서 폭탄을 N번 도시로 보내면 되지만 폭탄은 일반 사람이 들기에 너무 무겁기에 1번 도시에 있는 슈퍼히어로 미노만이 들고 이동할 수 있다.

튜브의 이동속도는 매우 빠르기 때문에 미노가 1번 도시에서 반물질 폭탄이 있는 도시로 이동한 다음에 폭탄을 들고 다시 N번 도시로 이동할 수만 있다면 CTP를 구할 수 있다. 이동하는 과정에서 똑같은 튜브를 다시 사용할 수 있고 방문했던 도시를 또다시 방문할 수도 있다. 또한 이동경로의 길이 제한은 없다.

과연 슈퍼히어로 미노는 위기에 빠진 CTP를 구할 수 있을까? 입력으로는 T개의 시나리오가 주어진다. 시나리오마다 재유니스가 반물질 폭탄을 설치한 도시의 번호가 주어진다. 각각의 시나리오에 대해 슈퍼히어로 미노가 CTP를 지킬 수 있는지 알아보는 프로그램을 작성하자.

입력

첫 번째 줄에 N(3≤N≤100,000)과 M(1≤M≤1,000,000)이 주어진다. N은 CTP에 존재하는 도시의 개수를 의미하고 M은 CTP에 존재하는 튜브의 개수를 의미한다. 다음 M개의 줄에 걸쳐 X, Y(1≤X, Y≤N)가 주어지는데 X에서 Y로 이동할 수 있는 튜브가 있다는 뜻이다. 다음 줄에는 시나리오의 개수 T(1≤T≤100,000)가 주어진다. 다음 T개의 줄에 차례대로 C(2≤C≤N-1)가 주어지는데 이는 우주급 빌런 재유니스가 반물질 폭탄을 설치한 도시의 번호를 의미한다. 입/출력의 양이 많으므로 속도가 빠른 입/출력 함수를 사용하는것을 권장한다.

출력

T개의 줄에 걸쳐 CTP를 지킬 수 있는지 결과를 출력한다. 만약 CTP를 구할 방법이 없다면 “Destroyed the CTP”를 출력하고 슈퍼히어로 미노가 CTP를 구할 수 있다면 “Defend the CTP”를 출력한다. 모든 출력은 쌍따옴표를 제외하고 출력한다.

예제 입력 1

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

예제 출력 1

Defend the CTP
Defend the CTP
Destroyed the CTP

힌트

아래 그림은 N이 6인 CTP의 서로 다른 두 시나리오를 보여준다.

그림 (a)는 5번 도시에 반물질 폭탄이 설치된 시나리오다. 슈퍼히어로 미노는 1번 도시에서 빨간색으로 표시된 튜브를 따라 5번 도시로 이동한 뒤 폭탄을 가지고 6번 도시로 이동하면 CTP를 구할 수 있다. 그림 (b)는 2번 도시에 반물질 폭탄이 설치된 경우다. 이 경우는 빨간색으로 표시된 튜브를 따라 2번 도시로 이동할 수 있지만 2번 도시에서 6번 도시로 이동할 수 없기 때문에 CTP는 빌런 재유니스에 의해 파괴된다.