#P18551. Colorful Graph 3

Colorful Graph 3

Colorful Graph 3

再次深入研究量子色动力学的复杂理论后,Little Cyan Fish 对色荷的概念产生了浓厚兴趣。为了检验你对这一理论的理解,他提出了下面的任务。

给定整数 nn 和 kk 个非负整数 c1,c2,…,ckc_1,c_2,\ldots,c_k,请构造一张有 nn 个顶点的无向图,使其满足:

  • 每条边有一种颜色 wiw_i,颜色是区间 [1,k][1,k] 中的整数。
  • 对所有 1≤i,j≤n1\le i,j\le n 以及所有 1≤t≤k1\le t\le k,都存在一条连接顶点 ii 与 jj 的路径,使得这条路径上颜色为 tt 的边的数量不超过 ctc_t。对于不同的 tt,所选的路径可以不同。
  • 在满足上述条件的所有图中,边数最少。

保证至少存在一种可行构造。

输入格式

第一行包含整数 TT(1≤T≤5×1041\le T\le5\times10^4),表示测试用例数。

对于每个测试用例:

第一行包含两个整数 n,kn,k(2≤n,k≤1052\le n,k\le10^5)。

第二行包含 kk 个整数 c1,c2,…,ckc_1,c_2,\ldots,c_k(0≤ci≤n0\le c_i\le n)。

保证至少存在一种可行构造。所有测试用例的 nn 之和不超过 10510^5,且 kk 之和也不超过 10510^5;这两个总限制分别成立。

输出格式

对于每个测试用例,先单独输出一行整数 mm,表示构造的图的边数。

接下来输出 mm 行,第 ii 行包含三个整数 ui,vi,wiu_i,v_i,w_i(1≤ui,vi≤n1\le u_i,v_i\le n,1≤wi≤k1\le w_i\le k),表示顶点 uiu_i 与 viv_i 之间有一条颜色为 wiw_i 的无向边。

输出任意满足要求且边数最少的图即可。

原样例

3
4 2
1 1
2 2
0 0
5 2
3 1
4
1 2 1
2 3 2
3 4 2
4 1 2
2
1 2 1
1 2 2
4
1 2 1
2 3 2
3 4 1
3 5 1

原样例第二个测试用例中,两条边的端点相同、颜色不同;这种输出是允许的。