C - 対戦カードの組み合わせ 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 333 点

問題文

高橋君はスポーツ大会の対戦表を作成しています。

大会には N 人の選手が参加しており、選手には 1 から N までの番号が付けられています。選手 i (1 \leq i \leq N) には「競技番号」 P_i と「所属チーム番号」 Q_i という2つの整数が割り当てられています。競技番号はその選手がエントリーしている競技の識別番号を、所属チーム番号はその選手が所属するチームの識別番号を表します。

この大会では、選手 i と選手 j (1 \leq i < j \leq N) が対戦できるのは、同じ競技にエントリーしていて、かつ異なるチームに所属している場合に限ります。すなわち、P_i = P_j かつ Q_i \neq Q_j であるときに限り対戦が成立します。

なお、競技番号と所属チーム番号の組がまったく同じ選手が複数存在することもあります。そのような選手同士は選手番号によって区別される別々の選手ですが、同じチームに所属しているため Q_i \neq Q_j の条件を満たさず、互いに対戦することはできません。

対戦が成立する2人の選手の組（順序を区別しない）の総数を求めてください。

制約

  • 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

1 行目には、選手の人数を表す整数 N が与えられる。続く N 行のうち、上から i 番目の行 (1 \leq i \leq N) には、選手 i の競技番号 P_i と所属チーム番号 Q_i が空白区切りで与えられる。

出力

対戦が成立する2人の選手の組の総数を1行で出力せよ。

入力例 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

Score : 333 pts

Problem Statement

Takahashi is creating a match schedule for a sports tournament.

There are N players participating in the tournament, numbered from 1 to N. Each player i (1 \leq i \leq N) is assigned two integers: a "sport number" P_i and a "team number" Q_i. The sport number represents the identifier of the sport the player has entered, and the team number represents the identifier of the team the player belongs to.

In this tournament, player i and player j (1 \leq i < j \leq N) can compete against each other only if they are entered in the same sport and belong to different teams. That is, a match is possible only when P_i = P_j and Q_i \neq Q_j.

Note that there may be multiple players with exactly the same combination of sport number and team number. Such players are considered distinct players distinguished by their player numbers, but since they belong to the same team, they do not satisfy the condition Q_i \neq Q_j and cannot compete against each other.

Find the total number of unordered pairs of players that can compete against each other.

Constraints

  • 2 \leq N \leq 2 \times 10^5
  • 1 \leq P_i \leq 10^5
  • 1 \leq Q_i \leq 10^5
  • All input values are integers
  • It is guaranteed that the answer is at most 2^{63} - 1

Input

Input is given from standard input in the following format:

N
P_1 Q_1
P_2 Q_2
\vdots
P_N Q_N

The first line contains an integer N representing the number of players. In the following N lines, the i-th line (1 \leq i \leq N) contains the sport number P_i and team number Q_i of player i, separated by a space.

Output

Output the total number of unordered pairs of players that can compete against each other, in a single line.

Sample Input 1

4
1 1
1 2
2 1
1 1

Sample Output 1

2

Sample Input 2

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

Sample Output 2

5

Sample Input 3

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

Sample Output 3

11