다리
시간 제한1초메모리 제한256 MB
북쪽은 동쪽으로 남쪽은 서쪽으로 이동하는 일방통행 도로에 서로 교차하지 않는 다리를 추가하고 일부 도로를 폐쇄한 뒤 두 마을 사이 도달 가능 여부를 묻습니다.
문제
강을 사이에 두고 북쪽과 남쪽에 각각 개의 마을이 있다. 북쪽 마을은 부터 , 남쪽은 부터 까지 번호가 붙는다. 같은 강변에서 동쪽에 있는 마을일수록 번호가 크다.
북쪽 강변에는 각 마을(마을 제외)에서 바로 동쪽 이웃으로 가는 일방통행 도로가 있다. 남쪽 강변에는 각 마을(마을 제외)에서 바로 서쪽 이웃으로 가는 일방통행 도로가 있다.
도로는 안전상의 이유로 영구 폐쇄될 수 있다. 강을 가로지르는 다리는 반대편 두 마을을 양방향으로 연결하며, 한 번 지으면 무너지지 않는다. 다리는 서로 교차하지 않으며, 각 마을은 반대편과 최대 한 개의 다리로만 연결된다.
초기에는 모든 도로가 열려 있고 다리는 없다. 이후 개의 사건이 시간 순으로 주어진다.
A G1 G2: 마을 과 사이에 다리를 건설한다.B G1 G2: 마을 과 사이의 일방통행 도로를 폐쇄한다.Q G1 G2: 현재 도로와 다리만으로 에서 로 갈 수 있는지 묻는다.
입력
첫 줄에 ()과 ()이 주어진다.
다음 줄에 사건이 주어진다. 각 사건의 마을 번호 , 는 이며 서로 다르다. 폐쇄되는 도로는 그 시점까지 통행 가능했고, 건설되는 다리는 그 시점까지 존재하지 않았다.
출력
각 Q 사건에 대해, 에서 로 갈 수 있으면 DA, 없으면 NE를 입력 순서대로 한 줄에 하나씩 출력한다.