Defend the CTP!!!

지금으로부터 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 \le N \le 100\,000$)과 튜브의 개수 $M$($1 \le M \le 1\,000\,000$)이 주어진다.

다음 $M$개의 줄에는 각각 두 정수 $X$, $Y$($1 \le X, Y \le N$)가 주어진다. $X$번 도시에서 $Y$번 도시로 이동하는 튜브가 있다는 뜻이다.

다음 줄에 시나리오의 개수 $T$($1 \le T \le 100\,000$)가 주어진다. 이어지는 $T$개의 줄에는 차례대로 재유니스가 반물질 폭탄을 설치한 도시의 번호 $C$($2 \le C \le N-1$)가 주어진다.

입출력의 양이 많으므로 빠른 입출력 방법을 사용하기를 권장한다.

시나리오마다 한 줄씩, 총 $T$개의 줄에 결과를 출력한다. 미노가 CTP를 구할 수 있으면 Defend the CTP를, 구할 방법이 없으면 Destroyed the CTP를 출력한다. 따옴표는 출력하지 않는다.

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

그림 (a)는 5번 도시에 폭탄이 설치된 시나리오다. 미노는 1번 도시에서 빨간색으로 표시된 튜브를 따라 5번 도시로 간 뒤, 폭탄을 들고 6번 도시로 이동해서 CTP를 구한다. 그림 (b)는 2번 도시에 폭탄이 설치된 경우다. 빨간색으로 표시된 튜브를 따라 2번 도시까지는 갈 수 있지만 2번 도시에서 6번 도시로 갈 수 없으므로, CTP는 빌런 재유니스에게 파괴된다.