문제
고담 시에 조커가 새로운 사악한 계획과 함께 돌아왔다!
고담 시에는 N개의 교차로와 M개의 양방향 도로가 있다.
두 교차로를 직접 잇는 도로는 최대 한 개이다.
조커의 사악한 계획에는 홀수 사이클이 필요하다.
홀수 사이클이란 교차로 S와 짝수 k에 대해 다음 조건을 만족하는 수열 S, s_1, ... , s_k, S를 말한다.
-S와 s_1을 잇는 도로가 존재한다.
-s_i와 s_{i+1}을 잇는 도로가 존재한다. (i = 1, ... , k-1)
-s_k와 S를 잇는 도로가 존재한다.
하지만, 경찰들은 고담 시의 도로들을 통제하고 있다.
구체적으로, i일에는 l_i번에서 r_i번 사이의 도로들을 모두 봉쇄하며 이 도로들은 조커의 계획에 사용될 수 없다.
조커는 경찰에 유능한 스파이를 심어 두었고, 1일에서 Q일 사이의 통제 계획을 모두 알아내었다.
이제 조커의 유능한 부하인 당신의 차례이다.
1일부터 Q일 사이의 모든 날짜에 대해 그 날 계획을 실행할 홀수 사이클이 존재하는지 판단하는 프로그램을 작성하라.
입력
첫 줄에 N, M, Q가 주어진다.
다음 M개의 줄에 1번 도로부터 순서대로 도로가 연결하는 양 끝 교차로의 번호가 주어진다.
다음 Q개의 줄에 l_i와 r_i가 순서대로 한 줄에 한 쌍씩 주어진다. (i = 1, ... , Q)
i일에 l_i번에서 r_i번 사이의 도로들이 모두 봉쇄된다는 의미이다.
1 <= N, M, Q <= 200000
두 교차로를 직접 잇는 도로는 최대 한 개이다.
도로의 양 끝점은 다른 교차로이다.
l_i <= r_i (i = 1, ... , Q)
출력
i번째 줄에는 i일의 계획을 실행할 수 있는지를 “YES”, “NO”로 출력하여 총 Q줄을 출력하라.
예제1
682
13
15
16
25
26
34
35
56
48
47
NO
YES