시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 71 31 20 83.333%

문제

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

예를 들어, 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번까지의 문제들로 구성된 문제집을 민규에게 준다. ( xy )
  • 2 x y : x번 문제를 풀기 위해선 y번 문제를 먼저 풀어야 한다는 관계를 표에서 지운다. 삭제되는 관계는 표에 존재하는 관계만 주어진다.
  • 3 x y : x번 문제를 풀기 위해선 y번 문제를 먼저 풀어야 한다는 관계를 표에 추가한다. 생성되는 관계는 표에 존재하지 않는 관계만 주어진다.

모순된 상황이 발생하는 입력은 주어지지 않는다.

출력

1 x y 의 입력이 들어왔을 때, 민규가 현재 x번부터 y번까지의 문제들로 구성된 문제집을 전부 풀 수 있으면 "YES", 그렇지 않다면 "NO"를 출력하라.

제한

  • 1 ≤ a, b, x, yN

서브태스크 1 (100점)

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

서브태스크 2 (20점)

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

서브태스크 3 (20점)

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

예제 입력 1

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

예제 출력 1

YES
YES
NO
YES
YES
NO

예제 입력 2

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

예제 출력 2

NO
YES
YES
NO
YES

예제 입력 3

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

예제 출력 3

NO
YES
NO

힌트

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

채점

  • 예제는 채점하지 않는다.