4306: 「WC2017」排序

牛牛最近学习了排序的相关知识，他对排序算法的运行效率产生了浓厚的兴趣并对此展开了一系列的研究。为了优化排序的运行时间，牛牛找到了来参加冬令营的你，希望你帮助他设计一台计算机进行排序。 这台计算机的设计方法如下： - 需要进行排序的序列存储在大小为 $n$ 的数组 $Q$ 中。 - 进行计算的最小单元是**比较器**，一个比较器可以用一个三元组 $(i,j,t)$ 表示，其中，$i ,j ,t$ 均为**正整数**，其中 $i,j$ 均在 $[1,n]$ 内且 $i < j$。它的功能是在时刻 $t$ 比较 $Q_i$ 与 $Q_j$ 的大小，若 $Q_i>Q_j$，就交换 $Q_i$ 与 $Q_j$中的值，否则什么也不做。 - 若要让计算机正常运行，则需要任意两个比较器之间不能发生冲突。两个比较器 $(A,B,T_1)$ 与 $(C,D,T_2)$ 会发生冲突**当且仅当** $A$、$B$、$C$、$D$ 中有两个相等的数且 $T_1 = T_2$。例如：比较器 $(1,3,1)$ 和 $(2,4,1)$ 不会发生冲突，而比较器 $(1,2,3)$ 和比较器 $(2,3,3)$ 会发生冲突。 在运行时，这台计算机中的每个比较器都会按照预先设定好的参数在指定的时间进行相应的操作。这台计算机运行时需要消耗的时间为所有的比较器中参数 $t$ 的最大值 $M$，该值越小意味着运行时间越短。 牛牛发现，现实中的许多数据具有自己的特性。在设计计算机时往往需要考虑到这些特性，并针对性地进行设计才能达到好的效果。 为了检验你设计的计算机，牛牛提供了 $8$ 个**测试点**共 $100$ 组**测试数据**，每个测试数据包含 $K$ 组测试数据，即 $K$ 个长度为 $n$ 的排列 $P$。请你为每组**测试数据**设计一台运行时间不超过 $m$ 的计算机，使得对于任意 $i \in [1,K]$，这台计算机能对 $P_i$ 排序。

由于输出过大，LOJ 上无法提交，因此本题改为**传统题**测评。 为了方便你区分不同的子任务，每个输入文件第一行为一个整数，表示当前测试点的编号。 第二行一个整数 $T\ (1 \leq T \leq 100)$ 表示这个测试点中的测试数据组数，同时也表示这个测试点的分值。在所有数据中，$\sum T=100$。 每组数据第一行三个整数 $K,n,m\ (1 \leq n \leq 10^5,1 \leq K,m \leq 10^4)$，意义在上文中已经说明。 接下来 $K$ 行每行 $n$ 个整数，描述一个 $1$ 到 $n$ 的排列。 **数据保证有解。**

对于每组测试数据，第一行输出一个整数 $\text{num}\ (1 \leq \text{num} \leq 10^6)$ 表示你设计的计算机中比较器个数。 接下来 $\text{num}$ 行，每行三个整数 $u,v,t\ (1 \leq u

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

7
1 2 1
3 4 1
2 3 2
4 5 2
1 2 3
3 4 3
2 3 4