P6270 [湖北省队互测 2014] 十万人的地铁

从前有两个人叫陆仁甲和陆仁乙，他们去搭地铁。 陆仁甲要从循礼门出发去广埠屯，而陆仁乙要从广埠屯出发去循礼门。 作为地铁的脑残粉，陆仁甲和陆仁乙很清楚武汉地铁收费的规则。 武汉地铁 $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_ie_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$ 的限制如前所述）

对于所有数据，$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$ 元，所以不要尝试模仿题目描述中的行为……）