학생들

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$일차에 민원을 접수하지 않았다"는 공통된 사실을 알게 된다.

이 밖에 학생들은 서로 정보를 주고받지 않는다. 각 학생은 자신이 속한 멘토링 그룹, 각 그룹의 구성원, 민원 접수 여부만 알 수 있다. 학생은 자신이 가진 정보로 논리적으로 추론할 수 있는 결론을 항상 도출하고, 가진 정보로 틀릴 수 있는 결론은 도출하지 않는다.

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

그룹의 수 $M$, 각 그룹의 구성원, 전체 문제와 부분 문제의 제한, 모든 그룹이 특정 범위의 번호를 가진 학생들을 제외한 꼴이라는 사실은 모두 외부인인 당신만 알고 있는 정보이며, 어떤 학생도 이를 전혀 알지 못한다.

• $1 \le N \le 250\,000$
• $1 \le M \le 250\,000$
• 모든 $0 \le i \le M - 1$에 대해 $0 \le L[i] \le R[i] \le N-1$