#P12424. 【MX-X12-T7】「ALFR Round 5」地铁(Easy Version)

【MX-X12-T7】「ALFR Round 5」地铁(Easy Version)

题目背景

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


本题与 Hard Version 的区别在于数据范围和时间限制不同,且本题不需要输出构造方案。本题满分为 5050 分。

题目描述

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

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

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

每一条地铁线路都不应「绕路」。如果一条地铁线路,在从其中一个起点站开到终点站的过程中,存在两段列车朝相反方向行驶的平行道路,则我们称这条地铁线路是「绕路」的。

在下图所示的地下网络中,灰线代表地下通道(深灰色的格子为地铁站,即道路交叉处)。红、绿、蓝线所代表的地铁线路没有「绕路」,而黄、橙、紫线所代表的地铁线路「绕路」了。

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

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

输入格式

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

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

输出格式

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

2
5 7
9 8
4
6
7
1 1
4 5
1 4
3 3
2 7
114514430240 191981099899
90102 240520
1
3
1
2
2
92804190717
80103

提示

【样例解释 #1】

第一组数据的构造方案如下图。要覆盖所有深灰色的交叉路口,至少需要四条地铁线路。

第二组数据的构造方案如下图。要覆盖所有深灰色的交叉路口,至少需要六条地铁线路。

【数据范围】

本题使用捆绑测试。

对于 100%100\% 的数据,1T1061\le T\le10^61n,m10181\le n,m\le10^{18}

子任务 分值 TT n,mn,m
11 55 T10T\le10 n,m10n,m\le10
22 n=m105n=m\le10^5
33 n,m105n,m\le10^5
44 T103T\le10^3
55 1010 n,m108n,m\le10^8
66 2020 T106T\le10^6 n,m1018n,m\le10^{18}

本题输入量较大,请使用较快的 I/O 方式。