Hide

Problem B
Connect

/problems/connect/file/statement/en/img-0001.png

When constructing electric circuits one has to connect pairs of points using wire, preferable as short as possible. In this problem we have an empty circuit board of size $N \times M$ where we want to connect the two points $A_1$ and $A_2$ with each other using one wire, and the two points $B_1$ and $B_2$ with each other using another wire. The wires must go along the horizontal and vertical edges of the grid (see figure), and the two wires may not share a common vertex. Determine the minimum length of wire needed to do so. The wire may not go outside the circuit board.

Input

The first line contains two integers, $N$ ($2 \le N \le 100$) and $M$ ($2 \le M \le 100$), the grid size of the circuit board.

Then follows four lines containing the coordinates for the points $A_1$, $A_2$, $B_1$ and $B_2$, respectively. Each coordinate pair will be described using two integers and will correspond to an intersection point in the grid. The first coordinate will be between $0$ and $N$ inclusive and the second coordinate between $0$ and $M$ inclusive. All coordinate pairs will be unique.

Output

A single line containing the minimum length of wire needed to connect the points, or “IMPOSSIBLE” if it’s not possible to do so.

Sample Input 1 Sample Output 1
6 3
2 3
4 0
0 2
6 1
IMPOSSIBLE
Sample Input 2 Sample Output 2
6 6
2 1
5 4
4 0
4 5
15

Please log in to submit a solution to this problem

Log in