CF1733C.Parity Shuffle Sorting

You are given an array $a$ with $n$ non-negative integers. You can apply the following operation on it.

• Choose two indices $l$ and $r$ ($1 \le l \lt r \le n$).
• If $a_l + a_r$ is odd, do $a_r := a_l$. If $a_l + a_r$ is even, do $a_l := a_r$.

Find any sequence of at most $n$ operations that makes $a$ non-decreasing. It can be proven that it is always possible. Note that you do not have to minimize the number of operations.

An array $a_1, a_2, \ldots, a_n$ is non-decreasing if and only if $a_1 \le a_2 \le \ldots \le a_n$.

给你一个包含 $n$ 个非负整数的数组 $a$。你可以对它执行以下操作：

• 选择两个下标 $l$ 和 $r$（满足 $1 \le l \lt r \le n$）；
• 若 $a_l + a_r$ 为奇数，则令 $a_r := a_l$；若 $a_l + a_r$ 为偶数，则令 $a_l := a_r$。

请找出任意一个至多包含 $n$ 次操作的操作序列，使得数组 $a$ 变为非递减序列。可以证明这样的序列总是存在的。注意：你无需最小化操作次数。

数组 $a_1, a_2, \ldots, a_n$ 是非递减的，当且仅当 $a_1 \le a_2 \le \ldots \le a_n$。

The first line contains one integer $t$ ($1 \le t \le 10^5$) — the number of test cases.

Each test case consists of two lines. The first line of each test case contains one integer $n$ ($1 \le n \le 10^5$) — the length of the array.

The second line of each test case contains $n$ integers $a_1, a_2, \ldots, a_n$ ($0 \le a_i \le 10^9$) — the array itself.

It is guaranteed that the sum of $n$ over all test cases doesn't exceed $10^5$.

第一行包含一个整数 $t$（$1 \le t \le 10^5$）—— 测试用例的数量。

每个测试用例由两行组成。每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 10^5$）—— 数组的长度。

每个测试用例的第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$0 \le a_i \le 10^9$）—— 数组本身。

保证所有测试用例的 $n$ 之和不超过 $10^5$。

For each test case, print one integer $m$ ($0 \le m \le n$), the number of operations, in the first line.

Then print $m$ lines. Each line must contain two integers $l_i, r_i$, which are the indices you chose in the $i$-th operation ($1 \le l_i \lt r_i \le n$).

If there are multiple solutions, print any of them.

对于每个测试用例，在第一行输出一个整数 $m$（$0 \le m \le n$），表示操作次数。

然后输出 $m$ 行。每行必须包含两个整数 $l_i, r_i$，表示第 $i$ 次操作中所选择的下标（$1 \le l_i \lt r_i \le n$）。

若存在多种解法，输出任意一种即可。

In the second test case, $a$ changes like this:

• Select indices $3$ and $4$. $a_3 + a_4 = 3$ is odd, so do $a_4 := a_3$. $a = [1, 1000000000, 3, 3, 5]$ now.
• Select indices $1$ and $2$. $a_1 + a_2 = 1000000001$ is odd, so do $a_2 := a_1$. $a = [1, 1, 3, 3, 5]$ now, and it is non-decreasing.

In the first and third test cases, $a$ is already non-decreasing.

在第二个测试用例中，数组 $a$ 的变化过程如下：

• 选择下标 $3$ 和 $4$。由于 $a_3 + a_4 = 3$ 是奇数，执行操作 $a_4 := a_3$。此时 $a = [1, 1000000000, 3, 3, 5]$。
• 选择下标 $1$ 和 $2$。由于 $a_1 + a_2 = 1000000001$ 是奇数，执行操作 $a_2 := a_1$。此时 $a = [1, 1, 3, 3, 5]$，已变为非递减序列。

在第一个和第三个测试用例中，数组 $a$ 本身已经是非递减的。