Minimum Subway Lines for Connected Underground Network

S City is planning an underground metro network to ease surface traffic congestion. According to the plan, the underground network consists of \(n\) horizontal tunnels and \(m\) vertical tunnels. A metro station is located at every intersection, totaling \(n \times m\) stations.

Every station must be covered by at least one metro line. Different metro lines are allowed to overlap. However, each metro line must not be detouring. Formally, a metro line is defined as a Manhattan shortest path: when traveling from one endpoint station to the other, it cannot contain two segments that are parallel (either horizontal or vertical) but traveled in opposite directions. In other words, the line must move monotonically in each axis.

Additionally, the entire metro network must be connected. This means that starting from any station, by riding the metro and making transfers (possibly none), one must be able to reach any other station in the network.

S City wishes to minimize the number of metro lines built. Given the dimensions \(n\) and \(m\) of the network, determine the minimum number of metro lines required to meet the above conditions.

Hint: It can be shown that:

• If \(\min(n,m)=1\), one line suffices.
• If \(\min(n,m)=2\), two lines are necessary and sufficient.
• If \(\min(n,m)\ge 3\), three lines are necessary and sufficient.

inputFormat

The input consists of a single line containing two positive integers \(n\) and \(m\) (\(1 \le n, m \le 10^9\)), representing the number of horizontal and vertical tunnels, respectively.

outputFormat

Output a single integer: the minimum number of metro lines required.

Note: Each metro line must be a Manhattan shortest path (i.e. it does not detour) and the union of all lines must cover every station and be connected.

sample

1 5

1