문제
강을 사이에 두고 북쪽과 남쪽에 2개의 고속도로가 있다. 하나는 1번 지점에서 N번 지점까지 동쪽으로 가는 일방통행 도로이고, 나머지 하나는 2N번 지점에서 N+1번 지점까지 서쪽으로 가는 일방통행 도로이다. (그림 참조)
명절이 되어 고속도로에 사고가 빈번히 일어나는데, 사고가 난 곳은 수습을 해야 하기 때문에 길을 막아야 한다.
막힌 길이 많아지면 통행이 불편해지므로 정부는 북쪽 지점과 남쪽 지점을 잇는 양방향 다리를 짓기 시작했다. 공사는 간단하게 진행해야 하므로 두 다리는 서로 교차하거나 같은 지점에서 끝나지 않게 하려고 한다.
고속도로에 여러 변화가 생길 때, 한 지점에서 다른 지점까지 갈 수 있는지 구하는 프로그램을 작성하여라.
입력
첫 번째 줄에는 강 북쪽에 있는 지역의 수 N과 명령의 수 M이 주어진다. (1 ≤ N ≤ 10^9, 1 ≤ M ≤ 200,000)
두 번째 줄부터 M개의 줄에는 다음과 같은 형식으로 명령이 주어진다.
A G1 G2 : G1번 지점과 G2번 지점을 연결하는 다리를 짓는다. 두 지점은 서로 다른 고속도로 위에 있다.
B G1 G2 : G1번 지점과 G2번 지점 사이에서 사고가 나서 길을 막는다. 두 지점은 같은 고속도로에 있으며, 이웃한 위치에 있다.
Q G1 G2 : G1번 지점에서 G2번 지점으로 갈 수 있는지 물어본다.
처음에는 다리가 하나도 설치되어 있지 않으며, 막힌 길도 없다.
출력
Q G1 G2 명령에 대하여, 갈 수 있으면 'DA'를, 그렇지 않으면 'NE'를 출력한다.
예제 #1
5 6
A 4 9
Q 1 7
B 3 2
Q 1 7
A 1 8
Q 1 7
DA
NE
DA
예제 #2
6 10
A 3 7
A 4 10
Q 1 11
A 12 5
Q 2 11
B 10 11
Q 2 10
Q 9 6
B 1 2
Q 1 2
NE
DA
DA
DA
NE
출처
COI 2014 3번 MOSTOVI
로그인해야 코드를 작성할 수 있어요.