시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 512 MB54333081.081%

문제

가톨릭대학교 학생인 쿠기는 졸업을 앞두고 여행을 가기로 결심했다. 꼼꼼한 성격인 쿠기는 여행을 가기 전에 여행계획을 미리 세우려 한다.

우선 쿠기는 가고 싶은 관광지를 모두 골라 여행지도를 그려봤다. 여행지도는 1부터 N까지의 서로 다른 번호를 가진 N개의 관광지가 있으며, 서로 다른 두 관광지를 오갈 수 있는 M개의 길들로 이루어져 있다. 이때, 모든 관광지는 여러 번 방문이 가능하다.

쿠기는 여행예산이 이미 정해져 있기 때문에 아쉽지만 여행지도에서 관광지를 하나씩 제외해보며 여행계획을 세우려 한다. 만약, 어떤 관광지를 제외했다면, 제외한 관광지와 연결된 모든 길도 여행지도상에서 제외가 된다. 또한, 제외된 관광지와 길은 여행지도에서 영구적으로 제외가 된다.

쿠기가 생각하는 이상적인 여행계획은 여행지도에 반드시 하나 이상의 관광지가 존재하고 임의의 관광지에서 다른 어떤 관광지도 모두 도달할 수 있어야 한다. 쿠기를 도와 여행지도에서 관광지를 계속해서 하나씩 제외했을 때 이상적인 여행계획이 되는지 확인해보자.

입력

첫번째 줄에는 여행지도에 있는 관광지의 수 N(1 ≤ N ≤ 200,000)와 두 관광지 사이를 연결하는 길의 수 M(1 ≤ M ≤ min(N×(N-1)/2, 200,000))가 주어진다.

다음 M개의 줄에는 쿠기가 그린 여행지도에서 각각의 길이 연결하는 두 관광지의 번호가 주어진다. 단, 길은 중복해서 주어지지 않는다.

그 다음 N개의 줄에 제외할 관광지 리스트가 순서대로 주어진다.

출력

첫번째 줄에는 관광지를 단 하나도 제외하지 않았을 때 이상적인 여행계획이 되는지 확인한다.

그 다음 줄부터는 입력에서 주어지는 제외할 관광지 리스트 중 i번째 관광지를 제외했을 때 이상적인 여행계획이 되는지 확인한다. 

여행계획을 확인했을 때 이상적인 여행계획이라면 "CONNECT"아니면 "DISCONNECT"를 출력한다.

예제 입력 1

5 4
5 4
4 3
3 2
2 1
4
5
1
2
3

예제 출력 1

CONNECT
DISCONNECT
CONNECT
CONNECT
CONNECT
DISCONNECT

예제에서 주어진 처음 상태의 모습이며, 이상적인 여행계획이 됨을 알 수 있다.

4를 제외한 후  모습이다. 이상적인 여행계획이 될 수 없다.

5를 제외한 후 모습이다. 이상적인 여행계획이 된다.

1을 제외한 후 모습이다. 이상적인 여행계획이 된다.

2를 제외한 후 모습이다. 이상적인 여행계획이 된다.

3을 제외한다면 관광지가 하나도 존재하지 않는다. 이상적인 여행계획이 될 수 없다.