#P12418. 【MX-X12-T1】「ALFR Round 5」地铁

【MX-X12-T1】「ALFR Round 5」地铁

题目背景

原题链接:https://oier.team/problems/X12A

题目描述

为了方便市民出行,缓解地面上的道路拥堵问题,S 市决定在地底下建一些地铁。

根据城市规划,S 市的地下网络将由 nn 条横向通道和 mm 条纵向通道构成。地铁站将设置在所有横向通道与纵向通道的交叉处,共 n×mn\times m 处。

地下网络的所有站点都需要被地铁线路覆盖,地铁线路之间可以有重叠部分。

由于地铁拐弯处的建造成本、安全要求较高,因此,S 市要求每一条地铁线路途径的所有站点,均在同一条横向通道或纵向通道内。即,地铁线路不能拐弯。

此外,地铁线路网必须是连通的。也就是说,无论从哪个地铁站出发乘坐地铁,经过若干次换乘(可以不换乘),都一定可以到达其它所有地铁站。

例如,当 n=5n=5m=7m=7 时,下图就是一个符合 S 市要求的地铁交通网络图(灰线代表地下通道,深灰色的格子为地铁站,即道路交叉处)。

因为盾构一条地铁线路的流程十分麻烦,S 市不想要建造太多的地铁线路。现在,你知道了 S 市的地下网络大小为 n×mn\times m,请你求出 S 市最少要建几条地铁线路。

输入格式

本题有多组测试数据,第一行输入一个整数 TT,表示数据组数。对于每组数据:

  • 仅一行,两个正整数 n,mn,m

输出格式

对于每组数据,输出一行一个整数,表示 S 市最少需要建造的地铁线路数量。

3
1 1
1 2
2 2
1
1
3

提示

【样例解释】

在第一组数据中,需要建造一条长度为 00,经过唯一一个站点的地铁线路。

在第二组数据中,需要建造一条长度为 11,连接两个站点的地铁线路。

在第三组数据中,一个合法的建造方案如下图。要覆盖所有深灰色的交叉路口,至少需要三条地铁线路。

【数据范围】

对于 15%15\% 的数据,保证 n=1n=1

对于另外 15%15\% 的数据,保证 n,m10n,m\le10

对于另外 15%15\% 的数据,保证 n=mn=m

对于另外 15%15\% 的数据,保证 nmn\le m

对于 100%100\% 的数据,1T101\le T\le101n,m3×1041\le n,m\le3\times10^4