Connection

Time limit1sMemory limit128 MB

Summary

Place two vertex-disjoint grid paths on an N x M lattice, one joining A1 to A2 and the other B1 to B2, to minimize the total number of unit segments.

Level: Hard8 of 10
Topics: Graph, Shortest path, BFS, Implementation
Solved: No attempts yet

Problem

When you connect two points with a wire in an electric circuit, a shorter wire is better.

Four points $A_1$ , $A_2$ , $B_1$ , and $B_2$ are given on an empty $N \times M$ circuit board. You want to connect $A_1$ to $A_2$ with one wire and $B_1$ to $B_2$ with another wire.

The board is a grid, and each lattice point has coordinates $(x, y)$ with $0 \le x \le N$ and $0 \le y \le M$ . A wire may run only along the unit vertical or horizontal segments of the grid, and it may never leave the board.

The two wires must not touch each other: they may not share any lattice point and may not cross. (It is fine for the two wires to run side by side one cell apart.)

Write a program that finds the minimum possible total length of the two wires.

Input

The first line contains the board dimensions $N$ and $M$ , separated by a space. ( $2 \le N, M \le 100$ )

Each of the next four lines contains the coordinates of $A_1$ , $A_2$ , $B_1$ , and $B_2$ , in that order. Each coordinate consists of two integers $x$ and $y$ with $0 \le x \le N$ and $0 \le y \le M$ . All four points are at distinct positions.

Output

Print the minimum possible total length of the two wires connecting $A_1$ - $A_2$ and $B_1$ - $B_2$ . If it is impossible to place the two wires under the given conditions, print IMPOSSIBLE.

Examples3

Example 1
Input
```
6 6
2 1
5 4
4 0
4 5
```
Expected output
```
15
```
Example 2
Input
```
6 3
2 3
4 0
0 2
6 1
```
Expected output
```
IMPOSSIBLE
```
Example 3
Input
```
3 2
0 0
3 0
0 1
3 1
```
Expected output
```
6
```