Inner Vertices

Time limit2sMemory limit64 MB

Summary

Given initial black points on an infinite grid, simulate a closure process filling row/column-enclosed points and count final black vertices or detect non-termination.

Level: Hard8 of 10
Topics: Geometry, Simulation, Math
Solved: No attempts yet

Problem

There is an infinite square grid whose vertices are each colored either black or white.

Call a vertex $V$ horizontal-inner if its row contains two black vertices with $V$ strictly between them, and vertical-inner if its column contains two black vertices with $V$ strictly between them. A vertex is inner if it is both horizontal-inner and vertical-inner.

Repeat the following step: simultaneously turn every white inner vertex black, while all other vertices keep their color. The process stops once no white inner vertex remains.

Compute the number of black vertices once the process stops.

Input

The first line contains one integer $n$ ( $0 \le n \le 100000$ ), the number of initially black vertices.

Each of the next $n$ lines contains two integers, the coordinates of a black vertex. All listed vertices are distinct, and every coordinate has absolute value at most $10^9$ .

Output

Output the number of black vertices once the process stops. If the process never stops, output -1.

Hint

Examples5

Example 1
Input
```
4
0 2
2 0
-2 0
0 -2
```
Expected output
```
5
```
Example 2
Input
```
1
0 0
```
Expected output
```
1
```
Example 3
Input
```
2
0 0
5 0
```
Expected output
```
2
```
Example 4
Input
```
8
0 0
1 0
2 0
0 1
2 1
0 2
1 2
2 2
```
Expected output
```
9
```

Example 5

Input

Expected output