Mass Hysteria (Hearthstone)

$\color{white}{\text{You are sus}}$

Franklin is plotting a Christmas attack where he casts the spell Mass Hysteria on a village of elves.

There are $n$ elves numbered $1$ to $n$, where elf $i$ has a health value of $h_i$ and an attack value of $a_i$. Initially, $h_i=a_i$ for all $i$, and all $a_i$ are distinct. Elf $i$ is alive if and only if its health is positive (i.e., $h_i \gt 0$).

When Franklin casts Mass Hysteria, the following process is repeated:

• Choose a pair of distinct living elves $x$ and $y$ ($h_x,h_y \gt 0$) such that elf $x$ has not attacked before. If no such pair exists, terminate the process.
• Then, elf $x$ attacks elf $y$, decreasing $h_y$ by $a_x$. Additionally, due to recoil, $h_x$ is decreased by $a_y$. Note that $a_x$ and $a_y$ remain unchanged.

The process will repeat until it is impossible to choose a valid pair of elves. It can be shown that Mass Hysteria terminates after at most $n$ iterations.

Given an integer $m$, construct a valid sequence of attacks such that exactly $m$ elves are alive when the process ends; or determine that no such sequence exists.

群体恐慌（《炉石传说》）

$\color{white}{\text{你很可疑}}$

富兰克林正策划一场圣诞袭击，他将对一群精灵施放法术“群体恐慌”。

共有 $n$ 个精灵，编号为 $1$ 到 $n$，其中精灵 $i$ 的生命值为 $h_i$，攻击力为 $a_i$。初始时，对所有 $i$ 均有 $h_i = a_i$，且所有 $a_i$ 互不相同。当且仅当精灵 $i$ 的生命值为正（即 $h_i > 0$）时，该精灵存活。

当富兰克林施放“群体恐慌”时，以下过程将被重复执行：

• 选择一对不同的存活精灵 $x$ 和 $y$（即 $h_x, h_y > 0$），且精灵 $x$ 尚未发动过攻击。若不存在这样的精灵对，则终止该过程。
• 接着，精灵 $x$ 攻击精灵 $y$，使 $h_y$ 减少 $a_x$；同时，由于反冲伤害，$h_x$ 也减少 $a_y$。注意：$a_x$ 和 $a_y$ 的值始终保持不变。

该过程将持续进行，直至无法选出满足条件的精灵对为止。可以证明，“群体恐慌”至多经过 $n$ 轮迭代后必然终止。

给定一个整数 $m$，请构造一个合法的攻击序列，使得过程结束时恰好有 $m$ 个精灵存活；或者判断不存在这样的序列。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.

The first line of each test case contains two integers $n$ and $m$ ($2\le n\le 2\cdot 10^5, 0\le m\le n$) — the number of elves in the village and the number of elves to be left alive.

The second line contains $n$ integers $a_1,a_2,\ldots,a_n$ ($1\le a_i\le 10^9$) — the initial attack and health values of the elves.

It is guaranteed that all $a_i$ are distinct.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2\cdot 10 ^ 5$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 10^4$）。随后是各测试用例的描述。

每个测试用例的第一行包含两个整数 $n$ 和 $m$（$2\le n\le 2\cdot 10^5,\ 0\le m\le n$）—— 分别表示村庄中精灵的数量以及需保留存活的精灵数量。

第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$（$1\le a_i\le 10^9$）—— 表示各精灵初始的攻击力与生命值。

保证所有 $a_i$ 互不相同。

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

For each test case, if it is impossible for exactly $m$ elves to remain alive, print $-1$.

Otherwise, output a valid sequence of attacks as follows:

• On the first line, output an integer $k$ ($0\le k\le n$) — the number of iterations in Mass Hysteria.
• Then $k$ lines follow, the $i$-th line containing two integers $x_i$ and $y_i$ ($1\leq x_i,y_i\leq n$, $x_i\neq y_i$), indicating that elf $x_i$ attacks elf $y_i$ in the $i$-th iteration.

The sequence must satisfy all of the following conditions:

• Immediately before the $i$-th iteration, both elves $x_i$ and $y_i$ are alive and elf $x_i$ has not attacked in any previous iteration.
• After the $k$-th iteration, exactly $m$ elves are alive and there does not exist a pair of distinct living elves $x$ and $y$ such that elf $x$ has not attacked before.

If there are multiple answers, you may output any of them. Any valid sequence satisfying the above conditions will be accepted.

对于每个测试用例，若不可能恰好有 $m$ 个精灵存活，则输出 $-1$。

否则，按如下格式输出一个合法的攻击序列：

• 第一行输出一个整数 $k$（$0\le k\le n$）——表示“群体恐慌”（Mass Hysteria）的迭代次数；
• 接下来 $k$ 行，第 $i$ 行包含两个整数 $x_i$ 和 $y_i$（$1\leq x_i,y_i\leq n$，且 $x_i\neq y_i$），表示在第 $i$ 次迭代中，精灵 $x_i$ 攻击精灵 $y_i$。

该序列必须满足以下所有条件：

• 在第 $i$ 次迭代开始前，精灵 $x_i$ 和 $y_i$ 均存活，且精灵 $x_i$ 在此前所有迭代中均未发动过攻击；
• 在第 $k$ 次迭代结束后，恰好有 $m$ 个精灵存活，且不存在一对互异的存活精灵 $x$ 和 $y$，使得精灵 $x$ 在此之前从未发动过攻击。

若存在多个合法答案，可输出任意一个。任何满足上述条件的合法序列均可被接受。

In the first test case, one possible sequence of attacks is shown below:

$x$

$y$

Health values after attack

Elves that have attacked

0

—

—

$[1, 4, 2, 3]$

$[]$

1

$3$

$1$

$[-1, 4, 1, 3]$

$[3]$

2

$2$

$4$

$[-1, 1, 1, -1]$

$[2, 3]$

After $2$ iterations, only elves $2$ and $3$ are alive. Since both of them have already attacked, no further valid attack is possible, and Mass Hysteria terminates.

In the second test case, the only possible choices for $(x,y)$ in the first iteration are $(1,2)$ or $(2,1)$. In either case, elf $1$ ends up with $-1$ health, so it is impossible for both elves to remain alive at the end. Note that Mass Hysteria will last at least one iteration as there exists a valid $(x,y)$ for the first iteration.

In the sixth test case, only elf $3$ is alive after all attacks. Even though elf $3$ has not attacked before, Mass Hysteria terminates since there is no other elf it can attack.

在第一个测试用例中，一种可能的攻击序列如下所示：

$x$

$y$

攻击后的生命值

已发动攻击的精灵

0

—

—

$[1, 4, 2, 3]$

$[]$

1

$3$

$1$

$[-1, 4, 1, 3]$

$[3]$

2

$2$

$4$

$[-1, 1, 1, -1]$

$[2, 3]$

经过 $2$ 轮迭代后，仅剩精灵 $2$ 和 $3$ 存活。由于它们均已发动过攻击，因此不再存在合法的攻击操作，“群体恐慌”（Mass Hysteria）终止。

在第二个测试用例中，第一轮迭代中 $(x,y)$ 的唯一可能选择为 $(1,2)$ 或 $(2,1)$。无论哪种情况，精灵 $1$ 的生命值最终均为 $-1$，因此不可能使两个精灵在最后均存活。注意，“群体恐慌”至少持续一轮，因为第一轮迭代中存在合法的 $(x,y)$。

在第六个测试用例中，所有攻击结束后仅剩精灵 $3$ 存活。尽管精灵 $3$ 尚未发动过攻击，但由于不存在其他可攻击的精灵，“群体恐慌”仍会终止。