题目描述

一棵有根树$^*$ $T$ 的权值定义为：

其中 $d_u$ 为 $u$ 节点与根节点的最短路径边数，$a_u$ 表示节点的权值。

给定 $n$ 个节点和一个正整数 $m$，每个节点都有一个正整数权值 $a_i$。

现在需要你构造一棵 $m$ 叉树$^{\dagger}$ $T$，满足以下条件：

• 所有权值非 $0$ 的节点互为兄弟关系，即不存在节点对 $(i, j)$，其中 $i \ne j$，且 $a_i,a_j \ne 0$，满足 $i$ 是 $j$ 的祖先$^{\ddagger}$，或 $j$ 是 $i$ 的祖先$^{\ddagger}$。

• 树的权值 $f(T)$ 在所有满足上一个条件的 $m$ 叉树的权值中最小。

由于仅使用给定的 $n$ 个节点显然无法满足，因此你可以添加最多 $n$ 个权值为 $0$ 的节点，新添加的节点编号从 $n + 1$ 开始，依次增加。

$^*$一颗包含 $n$ 个节点的树是指一个具有 $n$ 个节点、$n-1$ 条边的无向连通图。有根树是在树中指定一个特殊的顶点作为根的树。

$^{\dagger}$$m$ 叉树指的是每个节点最多有 $m$ 个子节点的有根树。

$^{\ddagger}$节点 $u$ 的祖先指所有满足以下条件的顶点 $v$：$v \ne u$，并且从根节点到 $u$ 的最短路径经过 $v$。

输入描述

有多组测试用例。

第一行包含一个正整数 $t$（$1\le t\le 5$），表示测试用例组数。

对每组测试用例：

第一行包含两个正整数 $n$，$m$（$2\le m\le n \le 10^5$），分别表示节点个数、树的叉数。

第二行包含 $n$ 个正整数 $a_1, a_2, \dots, a_n$（$1\le a_i \le 10^9$）。

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

输出描述

对每组测试用例：

第一行输出三个正整数 $f(T),k,s$，分别表示树的权值，添加的权值为 $0$ 的节点个数，根节点编号。

接下来输出 $n + k - 1$ 行，每行包含两个正整数 $u, v$ 表示节点 $u$ 和 $v$ 之间有一条边。

若有多种合法方案，输出任意一种即可。

样例

1
5 3
1 2 3 4 5

21 2 6
6 4
6 5
6 7
7 1
7 2
7 3

数据范围

共有 $30$ 组测试点。

对于前 $5$ 组测试点 $n$ 之和不超过 $10$。

对于第 $6$ 到 $15$ 组测试点 $n$ 之和不超过 $10^4$。

对于第 $16$ 到 $30$ 组测试点 $n$ 之和不超过 $10^5$。