During a science festival at the Byteotian University, $n$ different lectures are offered, numbered from $1$ to $n$. Each lecture lasts for a certain continuous time interval. The student Bajtazar would like to choose a set of lectures to attend. The lectures chosen by Bajtazar must take place at different times.

For Bajtazar, all offered lectures are equally interesting. However, he prefers to be prepared for any kind of random event. He would like to choose the lectures in such a way that if one of them (chosen arbitrarily) is cancelled, he can pick one more from the remaining lectures that will not conflict with his other remaining lectures from the original choice. Help him choose the largest possible number of lectures that satisfy these conditions.

Formally, if Bajtazar decides to choose $k$ pairwise distinct and non-conflicting lectures $u_1, \dots, u_k$ ($1 \le u_i \le n$), then for each $i = 1, \dots, k$, there must exist a lecture $v_i \in \{1, \dots, n\}$ such that $v_i \notin \{u_1, \dots, u_k\}$ and the lectures $u_1, \dots, u_{i-1}, v_i, u_{i+1}, \dots, u_k$ do not conflict with each other. Two lectures do not conflict if one of them starts exactly when the other ends, or later. Bajtazar wants to maximize the number $k$ of such selected lectures.

Input

The first line of the input contains a single integer $n$ ($n \ge 2$) denoting the total number of lectures. Each of the next $n$ lines contains the description of one lecture. The $i$-th of these lines contains two integers $a_i, b_i$ ($1 \le a_i < b_i \le 10^9$) denoting the start time and end time of the $i$-th lecture. Lecture $i$ and lecture $j$ do not conflict if $b_i \le a_j$ or $b_j \le a_i$.

Output

The first line of the output should contain the maximum possible number of lectures $k$ satisfying Bajtazar's requirements. The next $k$ lines should each contain two integers $u_i$ and $v_i$ in the range from $1$ to $n$, where $u_i$ is the index of a lecture chosen by Bajtazar, and $v_i$ is the index of the backup lecture for the lecture with index $u_i$. These pairs can be printed in any order. The numbers $v_1, \dots, v_k$ do not have to be pairwise distinct.

Examples

Input 1

8
1 5
3 10
4 8
9 12
11 16
14 15
20 22
15 21

Output 1

3
1 3
4 6
8 7

Note

Bajtazar decided to choose lectures with indices $u_1 = 1, u_2 = 4$ and $u_3 = 8$, taking place in the time intervals $[1, 5], [9, 12]$ and $[15, 21]$ respectively. These lectures do not conflict with each other. Furthermore: The first backup lecture, $v_1 = 3$, takes place in the time interval $[4, 8]$. This lecture does not conflict with the lectures taking place in the time intervals $[9, 12]$ and $[15, 21]$. The second backup lecture, $v_2 = 6$, takes place in the time interval $[14, 15]$. This lecture does not conflict with the lectures taking place in the time intervals $[1, 5]$ and $[15, 21]$. * The third backup lecture, $v_3 = 7$, takes place in the time interval $[20, 22]$. This lecture does not conflict with the lectures taking place in the time intervals $[1, 5]$ and $[9, 12]$.

Test cases

Test 0 is the example above. Additionally: 1ocen: $n = 100$, $i$-th lecture is $[i, i + 1]$; 2ocen: $n = 500\,000$, $i$-th lecture is $[i, i + 100]$.

Scoring

If only the first line of the output is correct, your program will receive 50% of the points for the test case. If the first line differs by 1 from the optimal value (but the selection of backup lectures is correct), your program will receive 15% of the points for the test case.