409987: GYM103886 N Shopping Groups

At the Supermarket, there are $$$2n$$$ brands of cereal arranged in a row.

There are $$$n$$$ regular customers of the Supermarket. The $$$i$$$-th customer likes all brands in the range $$$[l_i, r_i]$$$.

Two customers will compete with each other for cereal if their cereal ranges intersect, and neither range is contained in the other. Formally, customers $$$i$$$ and $$$j$$$ will compete with each other if one of the following holds:

• $$$l_i < l_j < r_i < r_j$$$
• $$$l_j < l_i < r_j < r_i$$$

The Supermarket is open on Mondays and Wednesdays. Determine if there is a way to partition the customers into Monday shoppers and Wednesday shoppers so that there is no cereal competition on any day.

The first line contains an integer $$$n$$$, the number of people ($$$1 \le n \le 10^5$$$).

The next $$$n$$$ lines contain two integers, $$$l_i$$$ and $$$r_i$$$ ($$$1 \le l_i < r_i \le 2n$$$).

It is guaranteed that each integer from $$$1$$$ to $$$2n$$$ appears exactly once in the endpoints of the segments.

If no partition satisfying the conditions above exists, output -1.

Otherwise, on the first line, output two integers, $$$x$$$ and $$$y$$$  — the number of Monday shoppers and Wednesday shoppers respectively.

On the second line, output $$$x$$$ integers, the indices of the Monday shoppers.

On the third line, output $$$y$$$ integers, the indices of the Wednesday shoppers.

Each integer from $$$1$$$ to $$$n$$$ should appear exactly once.

5
7 10
5 8
3 9
1 6
2 4

3 2
1 4 5 
2 3 

7
13 14
7 10
3 12
4 8
2 6
5 9
1 11

-1

In the first test, shoppers $$$1$$$, $$$4$$$, and $$$5$$$ are assigned to Monday. This is valid because:

• Shopper $$$1$$$ does not compete with shopper $$$4$$$ because their ranges do not intersect.
• Shopper $$$1$$$ does not compete with shopper $$$5$$$ because their ranges do not intersect.
• Shopper $$$5$$$ does not compete with shopper $$$4$$$ because shopper $$$5$$$'s range is completely contained in shopper $$$4$$$'s range.

Similarly, shoppers $$$2$$$ and $$$3$$$ are assigned to Wednesday, which is valid because:

• Shopper $$$2$$$ does not compete with shopper $$$3$$$ because shopper $$$2$$$'s range is completely contained in shopper $$$3$$$'s range.

Problem Credits: Thomas Liu