문제집 만들기
시간 제한2초메모리 제한512 MB
N개 문제 사이의 선후 관계를 간선 삽입과 삭제로 유지하면서, x번부터 y번까지의 문제가 이루는 부분 그래프가 비순환인지 판정한다.
문제
민규는 요즘 알고리즘 과외를 받고 있다. 민규의 과외 선생님 준표는 매일 민규에게 문제집을 한 권씩 만들어주려고 한다. 준표는 몇몇 문제가 민규가 처음부터 풀기에는 너무 어렵다고 생각하기 때문에 문제 사이의 관계를 표로 정리해 남겨두려고 한다.
예를 들어 a번 문제를 풀기 위해 b번 문제를 먼저 풀어야 한다면 a b로 적는다. 문제집을 만드는 중간에 생각이 바뀌면 준표는 표를 수정할 수 있으며, a번 문제를 풀기 위해 b번 문제를 풀어야 하는 동시에 b번 문제를 풀기 위해 a번 문제를 풀어야 하는 모순된 상황이 생기지 않도록 주의하며 표를 작성한다.
준표는 x번부터 y번까지의 문제로 문제집을 만들었을 때 민규가 처음부터 끝까지 문제집을 전부 풀 수 있는지 알고 싶다. 하지만 준표는 APC 준비로 너무 바빠서 이 작업을 할 시간이 없다. 바쁜 준표를 위해 프로그램을 작성해 주자.
입력
첫 번째 줄에 문제의 수 N, 문제 사이의 관계의 수 M, 작업 횟수 Q가 주어진다.
두 번째 줄부터 M+1번째 줄까지 두 정수 a b가 주어진다. 이는 a번 문제를 풀기 위해 b번 문제를 먼저 풀어야 한다는 관계를 표에 추가한다는 뜻이다. 같은 관계는 중복해서 주어지지 않는다.
M+2번째 줄부터 Q개의 줄에 걸쳐 아래 세 종류의 입력이 w, x, y 순으로 주어진다.
- 1 x y : x번부터 y번까지의 문제로 구성된 문제집을 민규에게 준다. (x ≤ y)
- 2 x y : x번 문제를 풀기 위해 y번 문제를 먼저 풀어야 한다는 관계를 표에서 지운다. 지우는 관계는 표에 있는 관계만 주어진다.
- 3 x y : x번 문제를 풀기 위해 y번 문제를 먼저 풀어야 한다는 관계를 표에 추가한다. 추가하는 관계는 표에 없는 관계만 주어진다.
모순된 상황이 발생하는 입력은 주어지지 않는다.
출력
1 x y 형태의 입력이 들어왔을 때, 민규가 현재 x번부터 y번까지의 문제로 구성된 문제집을 전부 풀 수 있으면 "YES", 그렇지 않으면 "NO"를 출력하라.
제한
- 1 ≤ a, b, x, y ≤ N
힌트
예제 2와 3은 서브태스크 1과 2에서는 나오지 않는다.