Select Meetings with Specified Compatibility

Given a list of n planned meeting events where each event is represented by its start and finish times, and an even integer m. It is guaranteed that n and m are even. Your task is to choose exactly \(\frac{n}{2}\) events from the list such that the maximum number of mutually compatible (i.e. non-overlapping) events among the chosen ones is exactly \(\frac{m}{2}\).

Two events \((s_1,t_1)\) and \((s_2,t_2)\) are considered compatible if \(t_1 \le s_2\) or \(t_2 \le s_1\). The maximum compatible set size in a given set of events can be determined by first sorting the events by their finish times and then selecting events greedily.

If there exists such a selection, output the 1-indexed indices of the chosen events in increasing order (all on one line, separated by a space). Otherwise, output -1.

inputFormat

The input begins with a line containing two space-separated even integers n and m.

Then follow n lines, each containing two space-separated integers \(s\) and \(t\) (\(s < t\)), representing the start and finish times of each meeting event.

outputFormat

If there is a valid selection, output a single line containing the indices (1-indexed) of the chosen meetings in increasing order, separated by single spaces. If no valid selection exists, output -1.

sample

4 2
1 3
2 5
4 6
7 8

1 2