Background

Problem Description

There are $n$ bananas. The $i$-th banana can be simplified as a positive integer pair $(a_i,k_i)$, where $2\le k_i\le 10$.

Initially, there are $n$ piles of bananas, and the $i$-th pile contains only the $i$-th banana.

Each time, you may choose two different piles to merge. During a merge, the sizes of bananas will be reduced.

Specifically, if the $i$-th banana participates in a merge, then its size $a_i$ becomes $\frac{1}{k_i}$ of its original value.

Participates in a merge: before merging, it is in one of the two piles being merged.

You want to merge all bananas into one pile. Since bigger bananas are better, you need to make the sum of all $a_i$ after all operations as large as possible.

Considering that finding the optimal solution may be difficult, you only need to get as close to the standard answer as possible. See the Scoring section for details.

To prevent you from outputting a random number, you also need to output a plan. See the Output Format section for details.

Input Format

The first line contains one positive integer $n$.

The next $n$ lines each contain two positive integers $a_i,k_i$.

Output Format

Output $n-1$ lines. Each line contains two numbers $x,y$, meaning to merge pile $x$ and pile $y$.

For the $i$-th merge, denote the newly formed pile as pile $n+i$. The two original piles (pile $x$ and pile $y$) will henceforth be considered nonexistent, so you are not allowed to use $x$ and $y$ in later merges. Otherwise, you will get zero points.

3
1 10
27 3
32 2

1 2
4 3

Hint

Sample Explanation

For the sample, the given output corresponds to ending with $a=(0.01,3,16)$, and the sum of $a_i$ is $19.01$.

Also, if you output the following, then it ends with $a=(0.01,9,8)$, and the sum of $a_i$ is $17.01$, which can get $4$ points.

1 3
2 4

Scoring

For each test point, scoring is done as follows:

• If your output is invalid, you get $0$ points.
• Otherwise, let $f$ be the sum of $a_i$ after all operations for your output plan, and let $ans$ be the sum of $a_i$ after all operations for the standard answer’s plan. Your score is $s=\lfloor \max\{0,10-\log_{10} \max\{1,\frac{ans-f}{\epsilon}\}\}\rfloor$ points, where $\epsilon=10^{-5}$.

Constraints

This problem has $10$ test points, each worth $10$ points.

For all data, it is guaranteed that $3\le n\le 10^5$, $1\le a_i\le 10^5$, and $2\le k_i\le 10$.

Translated by ChatGPT 5