← 返回题目列表

AtCoder · awc0015_c

C. 匹配卡组合

中文机器翻译题面 查看原题

分数: 333 分

问题陈述

高桥正在为体育锦标赛制定比赛时间表。

有 N 参加比赛的选手,编号从 1 to N。每个玩家 i (1 \leq i \leq N) 被分配了两个整数:“运动编号” P_i 和“团队编号” Q_i。运动编号代表运动员所参加的运动项目的标识符,球队编号代表运动员所属球队的标识符。

在本次比赛中,玩家 i 和玩家 j (1 \leq i < j \leq N) 只有参加同一运动且属于不同团队时才能相互竞争。也就是说,只有当 P_i = P_j 和 Q_i \neq Q_j.

请注意,可能有多名球员的运动号码和球队号码的组合完全相同。这些球员被认为是通过球员编号来区分的不同球员,但由于他们属于同一支球队,因此他们不满足条件 Q_i \neq Q_j 并且不能相互竞争。

找出可以相互竞争的无序对玩家的总数。

约束

  • 2 \leq N \leq 2 \times 10^5
  • 1 \leq P_i \leq 10^5
  • 1 \leq Q_i \leq 10^5
  • 所有输入值均为整数
  • 保证答案最多是 2^{63} - 1

输入

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

N
P_1 Q_1
P_2 Q_2
\vdots
P_N Q_N

第一行包含一个整数 N 代表玩家数量。在下文中 N 行, i第行 (1 \leq i \leq N) 包含运动编号 P_i 和团队编号 玩家的 Q_i 玩家的 i,用空格分隔。

输出

在一行中输出可以相互竞争的无序对玩家的总数。


示例输入 1

4
1 1
1 2
2 1
1 1

示例输出 1

2

示例输入 2

6
1 1
1 2
1 3
2 1
2 1
2 2

示例输出 2

5

示例输入 3

10
1 1
1 1
1 2
1 2
1 3
2 1
2 2
2 3
3 1
3 1

示例输出 3

11