#abc131f. [abc131_f]Must Be Rectangular!

[abc131_f]Must Be Rectangular!

题目描述

在二维平面上有 NN 个点。第 ii 个点的坐标为 (xi,yi)(x_i, y_i)

我们将重复以下操作,直到不能再进行为止:

  • 选择四个整数 aa, bb, cc, dd (ac,bd)(a \neq c, b \neq d),使得位置 (a,b)(a, b)(a,d)(a, d)(c,b)(c, b)(c,d)(c, d) 中恰好有三个位置上有点,然后在剩下的位置上添加一个点。

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

约束条件

  • 1N1051 \leq N \leq 10^5
  • 1xi,yi1051 \leq x_i, y_i \leq 10^5
  • iji \neq j 时,xixjx_i \neq x_jyiyjy_i \neq y_j
  • 输入中的所有值均为整数。

输入

从标准输入读入输入数据,数据格式如下:

NN x1x_1 y1y_1 : xNx_N yNy_N

输出

打印可以进行的最大操作次数。


示例输入 1

3
1 1
5 1
5 5

示例输出 1

1

选择 a=1a = 1b=1b = 1c=5c = 5d=5d = 5,我们可以在 (1,5)(1, 5) 的位置上添加一个点。我们不能再进行这个操作,因此最大操作次数为 11


示例输入 2

2
10 10
20 20

示例输出 2

0

只有两个点,所以我们根本无法进行这个操作。


示例输入 3

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

示例输出 3

16

我们可以对所有形如 a=1a = 1b=1b = 1c=ic = id=jd = j (2i,j5)(2 \leq i,j \leq 5) 的选择进行这个操作,而且不能再多了。因此,最大操作次数为 1616