Connecting a Grid of Points

Special for beginners, ^_^

Problem Description

There is a grid of points with $M$ rows and $N$ columns; adjacent points may be connected. A vertical connection costs one unit, and a horizontal connection costs two units. Some pairs of points are already connected. Find the minimum number of additional units needed to make all points connected.

Input Format

The first line contains two positive integers $m$ and $n$.

The following lines each contain four positive integers $x_1,y_1,x_2,y_2$, meaning the point at row $x_1$, column $y_1$ and the point at row $x_2$, column $y_2$ are already connected. The input guarantees $|x_1-x_2|+|y_1-y_2|=1$.

Output Format

The minimum additional cost needed to connect all points.

Sample Input 1

2 2
1 1 2 1

Sample Output 1

3

Constraints

1s, 1024KiB for each test case.

$30\%$ of the data: $n*m\le1000$.

$100\%$ of the data: $m,n\le1000$.