# KOITST 23 Students

https://www.acmicpc.net/problem/27607

SUS (Singapore University of Singapore) is a competitive university where students are given an $id$ number from $0$ to $N-1$, where $0$ is the best student and $N-1$ is the worst.

To prepare for the final exam, students formed mentoring groups on their own. Each mentoring group can be represented by two integers $L$ and $R$ ($0 \le L \le R \le N-1$). It consists of:

- students with $id < L$ **and**
- students with $id > R$

Let $S_i$ be the set of mentoring groups that student $i$ is part of. Initially, each student $i$ does not know of mentoring groups not in $S_i$.

In the morning of day $d=1$, all students at SUS received an email stating "There is at least one mentoring group". Now, they are worried that there are some mentoring groups that exclude them.

Following this, the behaviour of each student is as follows:

- During day $d$, student $i$ knows the following two pieces of information:
- There is at least one mentoring group
- No other student as lodged a complaint up to day $d-1$
- Knowing the above two pieces of information, if student $i$ can deduce with absolute certainty that there must be at least one mentoring group that excludes them, they will lodge a complaint in the evening of day $d$.
- If no complaints are lodged by the end of day $d$, all mentoring groups continue on day $d+1$.

All students follow the above behaviour, and know all other students also follow the same behaviour. Other than that, the students do not communicate any other information with one another.

Given information about all $M$ mentoring groups, determine the first day $k$ when a complaint is lodged. Additionally, determine the list of students who lodged complaints on day $k$. If no complaints are lodged indefinitely, return $-1$.

## Implementation

You are required to implement the following function:

pair<int, vector<int>> complaint(int N, vector<int> L, vector<int> R)

$L, R$: Integer arrays of size $M$. For all $0 \le i \le M - 1$, the $i$th mentoring group consists only of students whose numbers are less than $L[i]$ or greater than $R[i]$.

This function should return a pair consisting of an integer $k$ and an array $V$ of integers with a size not exceeding $N$. $k$ represents the date on which the complaint is received, and $V$ contains the numbers of students who filed complaints on the $k$th day in increasing order. If a complaint is never received, $k$ should be $-1$ and $V$ should be an empty array.

None of the source code submitted should execute input/output functions.

## Constraints

* $1 \le N \le 250,000$
* $1 \le M \le 250,000$
* For all $0 \le i \le M - 1$, $0 \le L[i] \le R[i] \le N - 1$

## Subtasks

* Subtask 1 (12 points): $N, M \le 10$
* Subtask 2 (6 points): For all $0 \le i \le M - 1$, $L[i] = R[i]$.
* Subtask 3 (15 points): $N, M \le 2,500$
* Subtask 4 (10 points): For all $0 \le i, j \le M - 1$, if $L[i] < L[j]$, then $R[i] < L[j]$ or $R[j] \le R[i]$
* Subtask 5 (18 points): For all $0 \le i \le M - 2$, $L[i] < L[i+1]$ and $R[i] < R[i+1]$.
* Subtask 6 (39 points): No additional constraints.

## Examples

### Example 1:

Consider the case where $N = 6$, $M = 3$, $L = [1, 2, 3]$, and $R = [4, 5, 3]$.

The grader will call the function as follows:

complaint(6, [1, 2, 3], [4, 5, 3])

The solid lines in the figure below represent the members included in each mentoring group.


Student $3$ is excluded from all mentoring groups. Since they know there is at least one mentoring group on day $1$, they can immediately deduce they are excluded from some mentoring group. Other students do not file complaints on the first day, so the function should return the pair $(1, [3])$.

### Example 2:

Consider the case where $N = 10$, $M = 4$, $L = [1, 4, 8, 2]$, and $R = [4, 7, 9, 6]$.

The grader will call the function as follows:

complaint(10, [1, 4, 8, 2], [4, 7, 9, 6])

The solid lines in the figure below represent the members included in each mentoring group.

The function should return the pair $(2, [4, 8, 9])$, as on the second day, students $4$, $8$, and $9$ file complaints.

### Example 3:

Consider the case where $N = 5$, $M = 1$, $L = [0]$, and $R = [4]$.

The grader will call the function as follows:

complaint(5, [0], [4])

The solid lines in the figure below represent the members included in each mentoring group. This mentoring group does not include any students (no one knows why this mentoring group exists).


The function should return the pair $(1, [0, 1, 2, 3, 4])$.