题目描述

从前有两个人叫陆仁甲和陆仁乙，他们去搭地铁。

陆仁甲要从循礼门出发去广埠屯，而陆仁乙要从广埠屯出发去循礼门。

作为地铁的脑残粉，陆仁甲和陆仁乙很清楚武汉地铁收费的规则。

武汉地铁 $2$ 号线是一条直线，一共 $m$ 个地铁站，依次编号为 $1,\cdots,m$。

搭乘地铁需要刷一种叫武汉通的公交卡。进站时刷一次，出站时刷一次，在出站时会根据起始站和终点站之间的距离给武汉通扣费。即，如果设 $cost(i, j)$ 表示从编号为 $i$ 的地铁站进，从编号为 $j$ 的地铁站出的代价，则：

$$cost(i,j)=|i-j|$$

机智的陆仁甲和陆仁乙发现，乘车时的起始站是在进站刷卡时记录在武汉通上面的。而且计费跟乘车时间无关，你可以在 $i$ 站进站，在地铁上玩一整天后从 $j$ 站出站，还是付出 $cost(i,j)$ 的代价。

于是陆仁甲和陆仁乙灵机一动，想出了一个绝妙的免费乘车方案。

首先，陆仁甲从循礼门站进站出发，在中途的螃蟹甲站下车逗留。与此同时，陆仁乙从广埠屯站进站出发，也在中途的螃蟹甲站下车逗留。

接着陆仁甲与陆仁乙在螃蟹甲站会面，交换武汉通。

最后，陆仁甲乘地铁前往广埠屯站，此时陆仁甲的武汉通记录的起始站是广埠屯站，所以扣费 $0$ 元。

陆仁乙乘地铁前往循礼门站，此时陆仁乙的武汉通记录的起始站是循礼门站，所以也扣费 $0$ 元。

这样他们就完成了一次免费乘车。

于是陆仁甲和陆仁乙开始思考：假设有 $n$ 个人来搭地铁，分别编号为 $1,\cdots,n$，第 $i$ 人从第 $s_i$ 站出发去第 $e_i$ 站 $s_i\ne e_i$，沿最短路坐地铁。即：

• 若 $s_i<e_i$ 则依次经过 $s_i,s_i+1,\cdots,e_i-1,e_i$。
• 若 $s_i>e_i$ 则依次经过 $s_i,s_i-1,\cdots,e_i+1,e_i$。

那么假设他们足够聪明，会在中途下车换票，那么他们乘车的最小总代价是多少？

具体乘车方式说明如下：

• 一开始，所有人刷卡进站，第 $i$ 个人在第 $s_i$ 站。
• 每次可以进行如下两个操作之一：
• $0\;x\;y$：让编号为 $x$ 的人乘地铁到第 $y$ 站下车。不允许绕路，即必须往接近 $e_x$ 的方向乘车。而且不允许从原地出发前往原地，即 $y$ 不能是第 $x$ 个人现在所在的地铁站编号。你需要保证 $1\le x\le n,1\le y\le m$。
• $1\;x\;y$：让编号为 $x$ 的人和编号为 $y$ 的人交换武汉通。注意此时在同一个地铁站的两人才可以交换车票。你需要保证 $1\le x\le n,1\le y\le n$。
• 每次操作时，没有在操作中提到的人会在原地逗留。
• 所有操作结束后，所有人一起刷卡出站。注意要保证第 $\boldsymbol i$ 个人此时在第 $\boldsymbol{e_i}$ 站。
• 最后要使得所有人出站后，武汉通上扣费总和最小。求一个最小的乘车方案。

陆仁甲和陆仁乙当然知道怎么做啦！但是他们想考考你……

输入格式

第一行一个正整数 $T$，表示有几组数据。接下来有 $T$ 个数据，对于每组数据：

第一行两个用空格隔开的正整数 $n,m$。表示有 $n$ 个人，$m$ 个地铁站。

接下来 $n$ 行每行两个用空格隔开的正整数 $s_i,e_i$。表示第 $i$ 个人的起始站和终点站。（$s_i\ne e_i,1\le s_i,e_i\le m$）

输出格式

对于每组数据，输出一个最优方案。如果有多组都能让扣费总和最小，输出任意一组即可。

第一行有两个用空格隔开的非负整数 $ans,s$，分别表示最小总代价和操作数。操作数不能太大，要满足 $s\le400000$。

接下来 $s$ 行每行三个正整数 $type\;x\;y$ 表示一个操作。（$type\in\{0,1\}$，$x,y$ 的限制如前所述）

2
3 7
1 7
1 6
5 1
2 7
1 7
7 1

7 5
0 1 5
1 3 1
0 1 7
0 2 6
0 3 1
0 3
0 1 7
1 2 1
0 2 1

提示

对于所有数据，$T\le6$。

编号	$\boldsymbol n$	$\boldsymbol m$
$1$	$=2$	$=1000$
$2$	$=100$	$=2$
$3$	$=4$	$=5$
$4$	$\le40$	$\le100$
$5\sim6$	$\le100$	$\le1000$
$7\sim8$	$\le2000$	$\le2\times10^4$
$9$	$\le6\times10^4$	$\le10^5$
$10$	$\le10^5$	$\le10^6$

（本题纯属 VFleaKing 脑洞……亲测表示进站再出站扣费 $1.8$ 元，所以不要尝试模仿题目描述中的行为……）