308504: CF1531B2. Мониторинг

Memory Limit:0 MB Time Limit:0 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

Мониторинг

题意翻译

给定 $n(2\leq n\leq 10^5)$ 个数对 $(a,b)$,求有多少个**不同**的数对满足 $a_i=a_j$ 或 $a_i=b_j$ 或 $b_i=a_i$ 或 $b_i=a_j$。

题目描述

ВКонтакте открыла второй штаб в Санкт-Петербурге! Вы не преминули возможностью сменить обстановку и решили переехать из офиса в Доме Зингера в офис на Красном мосту. Для комфортной работы вам потребуются два монитора с одинаковой высотой, чтобы изображение на них выглядело единым целым. На складе офиса на Красном мосту есть $ n $ мониторов, $ i $ -й из них имеет ширину $ w_i $ и высоту $ h_i $ . Любой монитор можно повернуть на 90 градусов, и тогда он будет иметь ширину $ h_i $ и высоту $ w_i $ . Назовём неупорядоченную пару из двух различных мониторов подходящей, если можно их повернуть так, чтобы они имели одинаковую высоту. Любой из мониторов в паре можно как повернуть относительно исходной ориентации, так и не поворачивать. Подсчитайте подходящие пары мониторов.

输入输出格式

输入格式


В первой строке задано одно целое число $ n $ — число мониторов на складе. В каждой из следующих $ n $ строк заданы два целых числа $ w_i $ и $ h_i $ ( $ 1 \le w_i, h_i \le 10^9 $ ) — ширина и высота $ i $ -го монитора. Обратите внимание, что мониторы могут быть квадратными ( $ w_i = h_i $ ), а размеры разных мониторов могут совпадать. В этой версии задачи $ 2 \le n \le 10^5 $ .

输出格式


Выведите число подходящих пар мониторов.

输入输出样例

输入样例 #1

5
3 2
2 2
5 5
3 5
4 3

输出样例 #1

5

输入样例 #2

7
10 10
10 20
20 10
10 20
10 20
10 10
20 10

输出样例 #2

21

Input

题意翻译

给定 $n(2\leq n\leq 10^5)$ 个数对 $(a,b)$,求有多少个**不同**的数对满足 $a_i=a_j$ 或 $a_i=b_j$ 或 $b_i=a_i$ 或 $b_i=a_j$。

加入题单

上一题 下一题 算法标签: