P12425 【MX-X12-T7+】「ALFR Round 5」地铁（Hard Version）
题目背景
原题链接：。
---
**本题与 Easy Version 的区别在于数据范围和时间限制不同，且本题需要输出构造方案。**
题目描述
为了方便市民出行，缓解地面上的道路拥堵问题，S 市决定在地底下建一些地铁。
根据城市规划，S 市的地下网络将由 $n$ 条横向通道和 $m$ 条纵向通道构成。地铁站将设置在所有横向通道与纵向通道的交叉处，共 $n\times m$ 处。
地下网络的所有站点都需要被地铁线路覆盖，地铁线路之间可以有重叠部分。
每一条地铁线路都不应「绕路」。如果一条地铁线路，在从其中一个起点站开到终点站的过程中，存在两段列车朝相反方向行驶的平行道路，则我们称这条地铁线路是「绕路」的。
在下图所示的地下网络中，灰线代表地下通道（深灰色的格子为地铁站，即道路交叉处）。红、绿、蓝线所代表的地铁线路没有「绕路」，而黄、橙、紫线所代表的地铁线路「绕路」了。
此外，地铁线路网必须是连通的。也就是说，无论从哪个地铁站出发乘坐地铁，经过若干次换乘（可以不换乘），都一定可以到达其它所有地铁站。
因为盾构一条地铁线路的流程十分麻烦，S 市不想要建造太多的地铁线路。现在，你知道了 S 市的地下网络大小为 $n\times m$，请你求出 S 市最少要建几条地铁线路，并给出一个方案。如果你求出的数不是最少需要的地铁线路数量，也可以获得一部分分数。**具体评分标准请参照题目最后面。**
输入格式
无
输出格式
无
说明/提示
**【样例解释】**
第一组数据的构造方案如下图。要覆盖所有深灰色的交叉路口，至少需要四条地铁线路。
第二组数据的构造方案如下图。要覆盖所有深灰色的交叉路口，至少需要六条地铁线路。
**【数据范围】**
**具体评分标准请参照题目最后面。**
对于 $100\%$ 的数据，$1\le T\le10$，$1\le n,m\le10^3$，$nm>1$。
|子任务|测试点个数|总分|特殊性质|
|:-:|:-:|:-:|:-:|
|$1$|$5$|$10$|$n,m\le10$|
|$2$|$5$|$5$|$m\ge n^2$|
|$3$|$5$|$15$|$n=m$|
|$4$|$6$|$30$|$n\le10$|
|$5$|$10$|$40$|无|
其中 Subtask 5 保证第 $k(k\in[1,10])$ 个测试点满足 $\max(\frac n m,\frac m n)\in[arr_{k-1},arr_{k})$，$arr$ 的值如下：
| $x$ | $0$ | $1$ | $2$ | $3$ | $4$ | $5$ | $6$ | $7$ | $8$ | $9$ | $10$ |
| :----------: | :----------: | :----------: | :----------: | :----------: | :----------: | :----------: | :----------: | :----------: | :----------: | :----------: | :----------: |
| $arr_x$ | $1$ | $\frac{11}{10}$ | $\frac{6}{5}$ | $\frac{4}{3}$ | $\frac{3}{2}$ | $\frac{5}{3}$ | $2$ | $3$ | $5$ | $10$ | $1000$ |
**【评分标准】**
**每个子任务得分为该子任务各个测试点得分向下取整之和。每个测试点得分为该测试点每组测试数据得分的平均值。**
每组测试数据评分标准如下：
- 如果程序未按格式要求输出或输出不符合题意，将获得 $0\%$ 的分数。一个测试点中，只要有一个测试数据因此获得 $0\%$ 的分数，则整个测试点都不会得分。
- 未按格式要求输出的例子：没有另外输出 $ans$ 行，$s$ 的长度不为 $l$ 等。
- 输出不符合题意的例子：有地铁线路「绕路」或超出 $n\times m$ 的范围了，所有地铁线路并没有连通，有路口没有被任何线路经过等。
- 否则，若程序在本测试数据输出了一个答案 $ans$ 并正确构造出了一个对应的方案，设 $X=\min(n,m)+1$，$A$ 为该测试数据的正确答案，即最少需要的地铁线路数量，则将会获得 $\lfloor-\frac{100}{X-A}ans+\frac{100X}{X-A}\rfloor\%$ 的分数。除去下取整，这是一个经过 $(A,100\%)$ 和 $(X,0\%)$ 的一次函数。