고담 시에 조커가 새로운 사악한 계획과 함께 돌아왔다!

고담 시에는 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일 사이의 모든 날짜에 대해 그 날 계획을 실행할 홀수 사이클이 존재하는지 판단하는 프로그램을 작성하라.

조커 timer 2초 memory 256MB

조커 2초 256MB