Joker
시간 제한2초메모리 제한256 MB
간선 번호가 l부터 r까지인 간선을 뺀 나머지 간선만으로 홀수 길이 사이클이 있는지 각 질의마다 판단합니다.
문제
Joker가 또 다른 악한 계획을 실행하려고 고담 시로 돌아온다. 고담 시에는 N개의 교차로(1번부터 N번까지 번호가 매겨짐)와 M개의 도로(1번부터 M번까지 번호가 매겨짐)가 있다. 각 도로는 서로 다른 두 교차로를 잇고, 두 교차로를 직접 잇는 도로는 최대 하나다.
계획을 위해 Joker는 홀수 개의 도로를 사용해 사이클을 만들어야 한다. 즉, 교차로 S와 짝수 양의 정수 k에 대해 다음 조건을 만족하는 교차로 수열 S, s1, ..., sk, S가 있어야 한다.
(a) S와 s1을 잇는 도로가 있다. (b) sk와 S를 잇는 도로가 있다. (c) 각 i = 2, ..., k에 대해 s(i-1)과 si를 잇는 도로가 있다.
경찰이 고담 시의 도로를 통제한다. i번째 날에 경찰은 번호 j가 li 이상 ri 이하인 도로를 감시한다. 감시되는 도로는 Joker의 계획에 포함될 수 없다. Joker는 경찰 내부에 간첩을 두고 있어서 날마다 어떤 도로가 감시되는지 전해 듣는다. 주어진 여러 날에 대해, Joker가 계획을 실행할 수 있는지 알고 싶다. 어느 날 계획을 실행하려면 감시되지 않는 도로만으로 이루어진 홀수 개의 도로 사이클이 있어야 한다.
입력
첫 줄에 세 정수 N, M, Q(1 ≤ N, M, Q ≤ 200000)가 주어진다. 각각 교차로의 수, 도로의 수, 날짜의 수다. 이어지는 M개 줄의 j번째 줄에는 도로 j가 잇는 두 교차로 번호 u, v(u ≠ v)가 주어진다. 이어지는 Q개 줄에는 정수 li와 ri가 주어지며, 이는 그날 번호 j가 li 이상 ri 이하인 도로가 감시됨을 뜻한다.
출력
Q개 줄을 출력한다. i번째 줄에는 i번째 날에 Joker가 계획을 실행할 수 있으면 "YES", 없으면 "NO"를 출력한다.
힌트
그림 1.