#P18551. Colorful Graph 3
Colorful Graph 3
Colorful Graph 3
再次深入研究量子色动力学的复杂理论后,Little Cyan Fish 对色荷的概念产生了浓厚兴趣。为了检验你对这一理论的理解,他提出了下面的任务。
给定整数 和 个非负整数 ,请构造一张有 个顶点的无向图,使其满足:
- 每条边有一种颜色 ,颜色是区间 中的整数。
- 对所有 以及所有 ,都存在一条连接顶点 与 的路径,使得这条路径上颜色为 的边的数量不超过 。对于不同的 ,所选的路径可以不同。
- 在满足上述条件的所有图中,边数最少。
保证至少存在一种可行构造。
输入格式
第一行包含整数 (),表示测试用例数。
对于每个测试用例:
第一行包含两个整数 ()。
第二行包含 个整数 ()。
保证至少存在一种可行构造。所有测试用例的 之和不超过 ,且 之和也不超过 ;这两个总限制分别成立。
输出格式
对于每个测试用例,先单独输出一行整数 ,表示构造的图的边数。
接下来输出 行,第 行包含三个整数 (,),表示顶点 与 之间有一条颜色为 的无向边。
输出任意满足要求且边数最少的图即可。
原样例
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
原样例第二个测试用例中,两条边的端点相同、颜色不同;这种输出是允许的。