시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 512 MB | 148 | 53 | 35 | 37.634% |
민규는 요즘 알고리즘 과외를 받고 있다. 민규에게는 매우 무서운 과외 선생님 준표가 있는데, 준표는 민규에게 매일 문제집을 한 권씩 만들어주려고 한다. 준표가 생각하기에 몇몇 문제는 민규가 처음부터 풀기엔 너무 어렵기 때문에 문제 간의 관계를 정리하여 표로 남겨두고자 한다.
예를 들어, 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번까지의 문제들로 구성된 문제집을 전부 풀 수 있으면 "YES"
, 그렇지 않다면 "NO"
를 출력하라.
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
YES YES NO YES YES NO
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
NO YES YES NO YES
5 1 5 4 1 1 4 4 2 4 1 1 4 4 3 4 1 1 4 4
NO YES NO
예제2, 3은 서브태스크1, 2에서는 나오지 않는다.
University > 아주대학교 > 2019 아주대학교 프로그래밍 경시대회 APC > Div.1 G번