11228. Має вийти прямокутник
На площині задані \(N\) точок. Координати \(i\)-ї точки: (\(x_i, y_i\)).
Ми будемо повторювати таку операцію якомога довше:
- Вибрати чотири цілі числа \(a\), \(b\), \(c\), \(d\) (\(a \neq c\), \(b \neq d\)), щоб було три точки з існуючими координатами (\(a, b\)), (\(a, d\)), (\(c, b\)), (\(c, d\)) а четверта точка позначить координату утвореного прямокутника.
Можна довести, що виконати цю операцію можна лише скінченну кількість разів.
Знайдіть максимальну кількість разів, яку можна виконати описану операцію.
Формат вхідних даних
Перший рядок вхідноо потоку містить ціле число \(N\) (\(1 \le N \le 10^5\)).
Наступні \(N\) рядків містять по два цілі числа \(x_i, x_i\) (\(1 \le x_i, y_i \le 10^5\)). Числа розділяються пропуском.
При \(i \neq j\) \(x_i \neq y_j\) або \(y_i \neq y_j\)
Формат вихідних даних
У вихідний потік виведіть максимальну кількість разів, яку можна виконати описану операцію.
Примітка
До прикладу 1:
Якщо вибрати \(a = 1\), \(b = 1\), \(c = 5\), \(d = 5\), то можна додати точку в (1, 5) щоб вийшов прямокутник.
Ми більше не можемо виконувати цю операцію і тому максимальна кількість операцій рівна 1.
Приклад вхідних даних
3
1 1
5 1
5 5
Приклад вихідних даних
1
Приклад вхідних даних
2
10 10
20 20
Приклад вихідних даних
0
Приклад вхідних даних
9
1 1
2 1
3 1
4 1
5 1
1 2
1 3
1 4
1 5
Приклад вихідних даних
16
До прикладу 3
Ми можемо виконати операцію для всіх варіантів виду \(a = 1\), \(b = 1\), \(c = i\), \(d = j\) (\(2 \leq i,j \leq 5\)), і не більше.
Таким чином, максимальна кількість операцій становить 16.
Коментарі