학생들 | cho.sh

IOI 대학교는 학생들을 이름이 아니라 시험 등수로 부르는 삭막한 경쟁 사회이다. 대학교에는 $N$ 명의 학생이 있으며, 각 $0 \le i \le N-1$ 에 대해 $i$ 번 학생은 중간고사에서 $i+1$ 등을 한 학생이다.

학생들은 기말고사를 대비하기 위해 자체적으로 멘토링 그룹을 꾸렸다. 각 멘토링 그룹은 두 정수 $0 \le L \le R \le N-1$ 로 나타낼 수 있는데, 번호가 $L$ 이상 $R$ 이하인 학생들을 제외한 모든 학생이 이 그룹에 속해 있다는 의미이다.

어느 날 아침, IOI 대학교의 모든 학생들에게 "멘토링 그룹이 1개 이상 존재한다" 라는 메일이 발송되었다. 이를 1일차 아침이라고 할 때, $d \ge 1$ 일차 저녁부터는 다음과 같은 상황이 진행된다.

어떤 학생이 $d$ 일차 아침 이후에 자신을 배제한 멘토링 그룹이 존재한다는 사실을 추론하였다. 학생은 불공평함을 느끼고, $d$ 일차 저녁이 끝나기 전에 민원을 접수한다. 민원이 접수되면, $d+1$ 일차 아침이 오기 전 모든 멘토링 그룹의 활동이 종료된다.
어떤 학생도 자신을 배제한 멘토링 그룹이 존재한다는 사실을 추론하지 못하였다. 민원이 접수되지 않고, $d+1$ 일차 아침에도 멘토링 그룹 활동이 지속된다. 이를 통해 모든 학생은 "아무도 $d$ 일차에 민원을 접수하지 않았다" 라는 공통적인 정보를 인지한다.

이외에 학생들은 어떤 방식으로든 서로의 정보를 공유하지 않는다. 즉, 자신이 속한 멘토링 그룹과 각 그룹의 구성원, 민원 접수 여부만 알 수 있다. 학생은 자신이 가진 정보로 추론할 수 있는 명제를 항상 추론하며, 자신의 가진 정보에서 틀릴 가능성이 있는 명제를 추론하지 않는다.

당신은 IOI 대학교의 모든 학생과 친한 외부인으로, 모든 멘토링 그룹과 그 구성원을 알고 있다. $M$ 개의 모든 멘토링 그룹에 대한 정보가 주어질 때, 민원이 접수되는 날짜 $k$ 와, $k$ 일차에 민원을 접수하는 학생의 번호를 모두 구하는 프로그램을 작성하여라. 영원히 민원이 접수되지 않는 경우에는 $-1$ 을 반환하면 된다.

그룹의 수 $M$ , 각 그룹의 구성원, 전체 문제 및 부분 문제의 제한, 모든 그룹이 특정 범위의 번호를 갖는 학생들을 제외한 꼴이라는 사실 등 모든 멘토링 그룹에 대한 정보는 오직 외부인인 여러분만 알 수 있고, 각 학생은 전혀 알지 못하는 정보임에 유의하라.