Hamster
Description
Hamster Joe is one of the beloved pets of Tomorrow Programming School. The biology department entrusted the school's "Central Robot Endowed with Smashing AI" (CRESAI) with the job of projecting and building a playpen for Joe. This playpen will be situated in a newly designated animal space within the department. This space is a flat horizontal area, tiled with uniformly sized square tiles of unit side length, that come together to create a rectangular grid marked by grooves where tiles meet. The playpen will be bordered by unit-length wall segments, each rising from the groove between two adjacent tiles, ensuring that both ends of every segment align with tile corners.
Joe can move from his current tile to any adjacent tile if the tiles are not separated by a wall segment. Joe cannot jump or crawl over any wall segment and Joe also cannot squeeze himself between two adjacent wall segments, or smash himself through them. Thus, when the locations of the wall segments are chosen appropriately, they form an enclosure, from which Joe would not be able to escape.
Surprisingly, CRESAI was not up to the task. It positioned each wall segment of unit length correctly, in the sense that each segment's base now sits in a groove and its ends coincide with the corners of a tile. However, it seems that most of the wall segments were positioned randomly so that the existence of any enclosure of any shape is not guaranteed.
To fix the problem at least temporarily, biologists are looking for the minimum number of additional wall segments of unit length, which, when installed at appropriately selected unused grooves, would create an enclosure of any shape or size. In the resulting layout, some of the wall segments originally installed by CRESAI may remain useless.
The first line contains one integer $M$ ($1 \leq M \leq 10^5$), the number of wall segments installed by CRESAI. Next, there are $M$ lines, each describing one wall segment installed by CRESAI. A wall segment is described by four integers $x_1, y_1, x_2, y_2$, where $x_1, y_1$ are the coordinates of one end of the wall segment and, $x_2, y_2$ are the coordinates of the other end of the segment. The axes of the system of coordinates are parallel to the grooves and the coordinates of each grove intersection are integers. For all wall segment coordinates, it holds $-10^9 \leq x_1, y_1, x_2, y_2 \leq 10^9$ and $|x_1 - x_2| + |y_1 - y_2| = 1$.
Output one line with the minimum number of additional wall segments which would create an enclosure of any size or shape, from which Joe would not be able to escape.
Input
The first line contains one integer $M$ ($1 \leq M \leq 10^5$), the number of wall segments installed by CRESAI. Next, there are $M$ lines, each describing one wall segment installed by CRESAI. A wall segment is described by four integers $x_1, y_1, x_2, y_2$, where $x_1, y_1$ are the coordinates of one end of the wall segment and, $x_2, y_2$ are the coordinates of the other end of the segment. The axes of the system of coordinates are parallel to the grooves and the coordinates of each grove intersection are integers. For all wall segment coordinates, it holds $-10^9 \leq x_1, y_1, x_2, y_2 \leq 10^9$ and $|x_1 - x_2| + |y_1 - y_2| = 1$.
Output
Output one line with the minimum number of additional wall segments which would create an enclosure of any size or shape, from which Joe would not be able to escape.
9
0 0 0 1
0 1 1 1
1 1 1 2
1 2 0 2
0 2 -1 2
-1 2 -2 2
-2 2 -2 1
-2 1 -2 0
-2 0 -1 0
1
Note
Figure 1: Rendering of the sample input