N. Shopping Groups
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

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 \lt l_j \lt r_i \lt r_j$$$
  • $$$l_j \lt l_i \lt r_j \lt 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.

Input

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 \lt r_i \le 2n$$$).

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

Output

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.

Examples
Input
5
7 10
5 8
3 9
1 6
2 4
Output
3 2
1 4 5 
2 3
Input
7
13 14
7 10
3 12
4 8
2 6
5 9
1 11
Output
-1
Note

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