17230번 - 문제집 만들기 서브태스크

민규는 요즘 알고리즘 과외를 받고 있다. 민규에게는 매우 무서운 과외 선생님 준표가 있는데, 준표는 민규에게 매일 문제집을 한 권씩 만들어주려고 한다. 준표가 생각하기에 몇몇 문제는 민규가 처음부터 풀기엔 너무 어렵기 때문에 문제 간의 관계를 정리하여 표로 남겨두고자 한다.

예를 들어, 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

• 1 ≤ N, Q ≤ 1,000
• 1 ≤ M ≤ min(N×(N-1)/2, 1,000)
• w = 1

• 1 ≤ N, Q ≤ 100,000
• 1 ≤ M ≤ min(N×(N-1)/2, 100,000)
• w = 1

• 1 ≤ N, Q ≤ 100,000
• 1 ≤ M ≤ min(N×(N-1)/2, 100,000)
• 1 ≤ w ≤ 3

예제2, 3은 서브태스크1, 2에서는 나오지 않는다.