Maximizing the Shortest Path in a Grid Graph

You are given an N × M grid. Consider each cell as a vertex. Two vertices share an edge if they are adjacent (up, down, left, right) and the edge (with weight 1) may or may not exist. You are allowed to remove some edges as long as the graph remains connected. Given two distinct vertices \((A, B)\) and \((C, D)\), your task is to design a connected subgraph (in fact, a spanning tree) so that the shortest path (measured by the number of nodes visited along the path) between \((A,B)\) and \((C,D)\) is as long as possible.

A key observation is that in any spanning tree the unique path between two vertices can visit at most all \(N \times M\) nodes. In other words, the maximum possible number of nodes on the shortest path is \(N\times M\) if and only if there exists a Hamiltonian path between \((A,B)\) and \((C,D)\) (i.e. a path that visits every vertex exactly once). However, since our grid is bipartite, a necessary condition for the existence of a Hamiltonian path is:

• If \(N\times M\) is even then the two endpoints must belong to different bipartite sets, i.e. their colors (defined by \((i+j) \bmod 2\)) must be different.
• If \(N\times M\) is odd then the two endpoints must both belong to the majority color (which turns out to be even because \((1,1)\) is even).

If the above condition is met, you can construct a Hamiltonian path and the answer is \(N \times M\); otherwise, the maximum possible number of nodes on the path is \(N \times M - 1\).

Your task is to compute and output the maximum possible number of nodes on the shortest path between \((A,B)\) and \((C, D)\) under the connectivity constraint.

Note: The path length is defined as the number of nodes (vertices) the path passes through.

inputFormat

The input consists of three lines:

1. The first line contains two integers \(N\) and \(M\) (\(1 \leq N, M \leq 10^5\)) representing the dimensions of the grid.
2. The second line contains two integers \(A\) and \(B\) (\(1 \leq A \leq N, 1 \leq B \leq M\)) representing the coordinates of the first vertex.
3. The third line contains two integers \(C\) and \(D\) (\(1 \leq C \leq N, 1 \leq D \leq M\)) representing the coordinates of the second vertex.

outputFormat

Output a single integer which is the maximum possible number of vertices on the shortest path between \((A,B)\) and \((C,D)\) after constructing the connected subgraph.

The answer is \(N \times M\) if a Hamiltonian path with endpoints \((A,B)\) and \((C,D)\) exists; otherwise, the answer is \(N \times M - 1\).

sample

2 2
1 1
1 2

4