必须是矩形

题目描述

二维平面上有 $N$ 个点,第 $i$ 个点的坐标为 $(x_i, y_i)$。

只要还能执行下面的操作,就不断重复:

• 选择满足以下条件的整数 $a, b, c, d$ ($a \neq c, b \neq d$):坐标 $(a, b), (a, d), (c, b), (c, d)$ 中恰好有 3 个位置存在点,然后在剩下的 1 个位置添加一个点。

可以证明这个操作只能执行有限次。求操作次数的最大值。

输入格式

输入按以下格式从标准输入给出:

$N$
$x_1$ $y_1$
$:$
$x_N$ $y_N$

输出格式

输出操作次数的最大值。

样例

3
1 1
5 1
5 5

1

取 $a = 1, b = 1, c = 5, d = 5$,可以在 $(1, 5)$ 处添加一个点。之后无法再执行操作,所以操作次数的最大值是 $1$ 次。

2
10 10
20 20

0

因为只有 2 个点,所以一次操作也无法执行。

9
1 1
2 1
3 1
4 1
5 1
1 2
1 3
1 4
1 5

16

可以对所有的 $a = 1, b = 1, c = i, d = j$ ($2 \le i,j \le 5$) 执行操作,之后无法再执行操作,所以操作次数的最大值是 $16$ 次。

数据范围

• $1 \le N \le 10^5$
• $1 \le x_i, y_i \le 10^5$
• $x_i \neq x_j$ 或 $y_i \neq y_j$ $(i \neq j)$
• 输入均为整数