G. Graph Problem
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output

There is a classic graph theory problem: given an undirected graph, find the largest subset of vertices such that the vertices form a clique. A clique is defined as a subset of vertices such that every two distinct vertices are adjacent in the given graph.

However, constructing the graph is troublesome. Now, for the $$$N$$$ vertices in the graph, we assign to the $$$i$$$-th vertex an interval $$$[l, r]$$$, representing a circular interval $$$[l, r]$$$.

What is a circular interval? Suppose the entire circle has a size of $$$2N$$$, which we can represent as coordinates $$$0$$$ to $$$2N-1$$$. A circular interval $$$[l, r]$$$ covers the coordinates: $$$$$$ \begin{cases} l\sim r & \text{if }l \lt r \\ 0\sim r\ \cup\ l\sim 2N-1 & \text{if } l \gt r \end{cases} $$$$$$

where $$$0\leq l, r \lt 2N, l\neq r$$$.

Given these intervals, we let there be an edge between any two vertices if and only if their intervals overlap at some coordinate.

Find any maximum clique.

Input

The first line of input contains a positive integer $$$N$$$, representing the number of intervals.

The next $$$N$$$ lines each contain two integers $$$l_i, r_i$$$, representing the coordinates of the interval for the $$$i$$$-th vertex. The intervals are numbered from $$$0$$$ to $$$N-1$$$.

  • $$$1\leq N\leq 2000$$$
  • $$$0\leq l_i, r_i \lt 2N$$$
  • It is guaranteed that all given coordinates are distinct.
Output

Output a single integer $$$k$$$ in the first line, representing the size of the maximum clique.

In the second line, output $$$k$$$ integers $$$c_0, c_1, \ldots, c_{k-1}$$$ separated by single spaces, where $$$c_i$$$ represents the index of the intervals included in the maximum clique.

If there are multiple valid solutions, output any one of them.

Examples
Input
3
0 3
2 5
4 1
Output
3
0 1 2
Input
5
0 6
9 1
3 4
5 8
2 7
Output
3
0 3 4