Minimizing Post‐Cut Connectivity in a Grid Garden

A garden is laid out as a \((N+1)\times(M+1)\) grid of points, and a chili pepper is planted at each grid point. Between any two adjacent grid points (neighbors sharing an edge) a rope is placed, but only \([(N+1)\times(M+1)-1]\) of these ropes are chosen such that they form a spanning tree over the grid. Two chili plants are considered connected if there is a path between them along the ropes of the spanning tree.

At night, a saboteur will make a single straight cut in either the horizontal or vertical direction. This cut will cut all rope segments that it crosses. After the cut, the chili plants become divided into several connected components (each component being a block connected by uncut ropes). The saboteur will choose the direction and position of the cut so as to maximize the number of connected components.

Your task is to design a method to arrange the ropes (i.e. choose a spanning tree of the grid) so that after the worst‐case cut, the number of connected components is minimized. Under the optimal rope arrangement, compute the minimum possible maximum number of connected components that can result after such a cut.

Observation: A cut in one of the two directions will sever precisely all the rope segments that cross that line. Since the spanning tree is acyclic, cutting \(r\) edges results in \(r+1\) connected components. One can show that by an appropriate arrangement, the maximum number of rope segments cut (over any horizontal or vertical line) can be minimized to \(\min\{N,M\}+1 - 1 = \min\{N,M\}\) edges, yielding \(\min\{N,M\}+1\) connected components. In other words, if the garden dimensions are given in terms of \(N\) and \(M\) (defining a grid with \(N+1\) rows and \(M+1\) columns), then the answer is:

[ \text{Answer} = \min{N,M} + 1. ]

You are given two integers \(N\) and \(M\) from the input. Output the minimum possible maximum number of connected components after the saboteur’s worst‐case cut.

inputFormat

The input consists of a single line containing two space-separated integers \(N\) and \(M\) \((0 \leq N, M \leq 10^9)\). The grid has \(N+1\) rows and \(M+1\) columns.

outputFormat

Output a single integer representing the minimal possible maximum number of connected components after the worst-case cut.

sample

1 1

2