P7562 [JOISC 2021] Event Hopping 2 (Event Hopping 2) (Day4)

**If you cannot download the testdata on Luogu, you can download all data [here](https://www.ioi-jp.org/camp/2021/2021-sp-tasks/day4/event2-data.zip).**

There will be $n$ events in IOI Park. These events are numbered from $1$ to $n$. Event $i$ is held from time $L_i+10^{-1}$ to time $R_i-10^{-1}$. The testdata guarantees that $L_i$ and $R_i$ are integers. JOI wants to attend exactly $k$ events. However, JOI cannot join or leave an event in the middle. **The travel time between two event venues is ignored.** JOI prefers events with smaller indices. More precisely, the indices of the $k$ events attended by JOI are $a_1,\cdots,a_k$, where $1 \le a_1 < \cdots < a_k \le n$. The sequence $(a_1, \cdots, a_k)$ is lexicographically smaller than $(b_1, \cdots, b_k)$ if and only if there exists $j\ (1 \le j \le k)$ such that for all $l$ in the interval $[1,j-1]$, we have $a_l=b_l$, and $a_j

The first line contains two positive integers $n,k$. Lines $2$ to $n + 1$ each contain two positive integers $L_i, R_i$.

If JOI can attend $k$ events: - Output $k$ lines. - Suppose the indices of the $k$ events attended by JOI are $a_1, a_2, \cdots, a_k\ (1\le a_1 < \cdots < a_k \le n）$. You need to output $a_j\ (1\le j \le k)$ on line $j$. Note that the sequence $(a_1, \cdots, a_k)$ must be the **lexicographically smallest**. If JOI cannot attend $k$ events, output $\texttt{-1}$.

#### Explanation for Sample #1 There are $2$ ways to attend exactly $4$ events. - Attend $1, 3, 4, 5$. - Attend $2, 3, 4, 5$. The sequence $(1,3,4,5)$ is lexicographically smaller than $(2, 3, 4, 5)$, so output $1, 3, 4, 5$. #### Explanation for Sample #2 No matter how you choose, it is impossible to attend exactly $3$ events, so output $\tt -1$. #### Explanation for Sample #3 This sample satisfies the conditions of all Subtasks. #### Constraints and Notes **Due to Luogu limitations, this problem will not be judged on the first $1\sim 20$ test points of each Subtask.** **This problem uses Subtask scoring.** | Subtask | Percentage of Score | $n$ | $L_i$ | | :----: | :----: | :----: | :----:| | $1$ | $7\%$ | / | $L_i \le L_{i+1}\ (1 \le i \le n − 1)$ | | $2$ | $1\%$ | $\le20$ | / | | $3$ | $31\%$ | $\le 3 \times 10^3$ | / | | $4$ | $61\%$ | / | / | **Note: a slash indicates no special restriction.** For $100\%$ of the data: - $1\le n\le 10^5$. - $1 \le k \le n$. - $1\le L_i < R_i \le 10^9 (1\le i \le n)$. #### Notes This problem is translated from [The 20th Japanese Olympiad in Informatics 2020/2021 Spring Training Camp -](https://www.ioi-jp.org/camp/2021/2021-sp-tasks/index.html) [Contest 4 -](https://www.ioi-jp.org/camp/2021/2021-sp-tasks/day4/2021-sp-d4-notice.pdf) [Task 1 Japanese statement](https://www.ioi-jp.org/camp/2021/2021-sp-tasks/day4/event2.pdf). Translated by ChatGPT 5