MCC 2025 P3: Trick or Treat

Trick or Treat

Statement

It’s Halloween! Evirir the dragon wants to give their two hatchlings candies. As a dragon who likes candies, Evirir has a hoard of $N$ candy packs numbered $1, 2, \ldots, N$. For each $i = 1, 2, \ldots, N$, candy pack $i$ contains two candies, one with colour $a_i$ and one with colour $b_i$.

Evirir wants to give each hatchling 3 candies, so they will choose 3 candy packs ($3 \times 2 = 6$ candies in total). To make clear which candies are whose, there must be two distinct colours $x$ and $y$ ($x \ne y$) such that 3 of the 6 candies have colour $x$, and the other 3 candies have colour $y$.

In how many ways can Evirir choose the candy packs?

Note: Two ways are different if a candy pack is chosen in one way but not in the other (the order of chosen candy packs does not matter). Candy packs numbered differently are considered different, even if they have the same candy colours.

Input Format

The first line contains an integer $N$.

Then, $N$ lines follow. The $i$-th of the $N$ lines contains two space-separated integers, $a_i$ and $b_i$.

Output Format

Output an integer, the answer.

Constraints

For all tasks:

• $1 \le N \le 200\,000$.

• $1 \le a_i, b_i \le 10^9$.

• Task 1 (5 points): $N \le 10$
• Task 2 (10 points): $N \le 20$
• Task 3 (15 points): $N \le 500$
• Task 4 (25 points): $N \le 5000$
• Task 5 (10 points): $a_i, b_i \le 2$ for all $1 \le i \le N$
• Task 6 (35 points): No additional constraints

Sample Input

9
1 2
1 3
2 1
1 1
2 2
1 3
3 1
1 1
1 1

Sample Output

7

Sample Explanation

There are 9 candy packs. Candy pack 1 has candies with colour 1 and colour 2, candy pack 2 has candies with colour 1 and colour 3, and so on.

There are 7 ways to choose the 3 candy packs:

• Choose candy packs 1, 4, 5: The candy colours are 1, 2, 1, 1, 2, 2. Here, 3 candies have colour 1 and 3 candies have colour 2.
• Choose candy packs 1, 5, 8: The candy colours are 1, 2, 2, 2, 1, 1.
• Choose candy packs 1, 5, 9: The candy colours are 1, 2, 2, 2, 1, 1.
• Choose candy packs 2, 6, 7: The candy colours are 1, 3, 1, 3, 3, 1.
• Choose candy packs 3, 4, 5: The candy colours are 2, 1, 1, 1, 2, 2.
• Choose candy packs 3, 5, 8: The candy colours are 2, 1, 2, 2, 1, 1.
• Choose candy packs 3, 5, 9: The candy colours are 2, 1, 2, 2, 1, 1.

Here are some invalid ways to choose the 3 candy packs:

• Choose candy packs 1, 2, 3: The candy colours are 1, 2, 1, 3, 2, 1. There should be only 2 colours, and each colour should appear 3 times.
• Choose candy packs 7, 8, 9: The candy colours are 3, 1, 1, 1, 1, 1. Each colour should appear 3 times.
• Choose candy packs 4, 8, 9: The candy colours are 1, 1, 1, 1, 1, 1. There must be 2 distinct colours.

One valid way and the three invalid ways above are shown in Figure 1:

Figure 1: Examples of valid and invalid ways to choose 3 candy packs.

Trick or Treat

Pernyataan

Hari ini merupakan hari Halloween! Evirir si naga ingin memberikan gula-gula kepada dua ekornya anaknya yang baru menetas. Sebagai seekor naga yang gemarkan gula-gula, Evirir mempunyai timbunan sebanyak $N$ bungkus gula-gula yang bernombor $1, 2, \ldots, N$. Bagi setiap $i = 1, 2, \ldots, N$, bungkusan gula-gula ke-$i$ mengandungi dua biji gula-gula, satu berwarna $a_i$ dan satu lagi berwarna $b_i$.

Evirir ingin memberikan setiap anak naganya 3 biji gula-gula, maka dia akan memilih 3 bungkusan gula-gula (jumlah keseluruhan $3 \times 3 = 6$ biji gula-gula). Untuk membezakan gula-gula antara kedua-dua anak naga tersebut, terdapat tepat dua warna berbeza $x$ dan $y$, $x \ne y$, dengan 3 daripada 6 gula-gula berwarna $x$ dan 3 yang selebihnya berwarna $y$.

Berapakah bilangan cara Evirir boleh memilih bungkusan gula-gula tersebut?

Nota: Dua cara dianggap berbeza jika terdapat sekurang-kurangnya satu bungkusan gula-gula yang dipilih dalam satu cara tetapi tidak dalam cara yang lain (urutan pemilihan tidak penting). Bungkusan gula-gula yang bernombor berbeza dianggap berbeza, walaupun mengandungi warna gula-gula yang sama.

Format Input

Baris pertama mengandungi satu integer $N$.

Kemudian, terdapat $N$ baris berikutnya. Baris ke-$i$ (daripada $N$ baris tersebut) mengandungi dua integer yang dipisahkan oleh ruang, $a_i$ dan $b_i$.

Format Output

Keluarkan satu integer, iaitu jawapan kepada bilangan cara yang mungkin.

Kekangan

Untuk semua tugasan:

• $1 \le N \le 200\,000$.

• $1 \le a_i, b_i \le 10^9$.

• Tugasan 1 (5 markah): $N \le 10$
• Tugasan 2 (10 markah): $N \le 20$
• Tugasan 3 (15 markah): $N \le 500$
• Tugasan 4 (25 markah): $N \le 5000$
• Tugasan 5 (10 markah): $a_i, b_i \le 2$ bagi semua $1 \le i \le N$
• Tugasan 6 (35 markah): Tiada kekangan tambahan

Contoh Input

9
1 2
1 3
2 1
1 1
2 2
1 3
3 1
1 1
1 1

Contoh Output

7

Penjelasan Contoh

Terdapat 9 bungkusan gula-gula. Bungkusan 1 mempunyai warna 1 dan 2, bungkusan 2 mempunyai warna 1 dan 3, dan seterusnya.

Terdapat 7 cara untuk memilih 3 bungkusan gula-gula yang memenuhi syarat:

• Pilih bungkusan 1, 4, 5: warna gula-gula ialah 1, 2, 1, 1, 2, 2. Di sini, 3 gula-gula mempunyai warna 1 dan 3 gula-gula mempunyai warna 2.
• Pilih bungkusan 1, 5, 8: warna gula-gula ialah 1, 2, 2, 2, 1, 1.
• Pilih bungkusan 1, 5, 9: warna gula-gula ialah 1, 2, 2, 2, 1, 1.
• Pilih bungkusan 2, 6, 7: warna gula-gula ialah 1, 3, 1, 3, 3, 1.
• Pilih bungkusan 3, 4, 5: warna gula-gula ialah 2, 1, 1, 1, 2, 2.
• Pilih bungkusan 3, 5, 8: warna gula-gula ialah 2, 1, 2, 2, 1, 1.
• Pilih bungkusan 3, 5, 9: warna gula-gula ialah 2, 1, 2, 2, 1, 1.

Berikut ialah beberapa contoh pemilihan yang tidak sah:

• Pilih bungkusan 1, 2, 3: warna gula-gula ialah 1, 2, 1, 3, 2, 1. Sepatutnya cuma perlu ada 2 warna, dan setiap warna sepatutnya muncul 3 kali.
• Pilih bungkusan 7, 8, 9: warna gula-gula ialah 3, 1, 1, 1, 1, 1. Setiap warna sepatutnya muncul 3 kali.
• Pilih bungkusan 4, 8, 9: warna gula-gula ialah 1, 1, 1, 1, 1, 1. Mesti terdapat dua warna yang berbeza.

Satu contoh cara yang sah dan tiga contoh cara yang tidak sah ditunjukkan dalam Rajah 1.

Rajah 1: Contoh cara yang sah dan cara yang tidak sah untuk memilih 3 bungkusan gula-gula.

不给糖就捣蛋

题目描述

是万圣节诶！龙 Evirir 想给他的两个幼崽一些糖果。身为一个喜爱糖果的龙，Evirir 囤积了 $N$ 袋标记为 $1, 2, \ldots, N$ 的糖果包。对于每个 $i = 1, 2, \ldots, N$，糖果包 $i$ 拥有两个糖果，其中一个是颜色 $a_i$ 而另一个是颜色 $b_i$。

Evirir 想要给每个幼崽3粒糖果，所以他会选择三个糖果包（共有 $3 \times 2 = 6$ 粒糖果）。为了分清楚哪个糖果是谁的，六粒糖果必须仅有两种不同颜色 $x$ 和 $y$（$x \ne y$），并且其中三个糖果必须是颜色 $x$ 而另外三个糖果必须是颜色 $y$。

请问 Evirir 共有多少种方式选择糖果包？

注意：若在一种方式中选择了某个糖果包，而在另一种方式中没有选择，则认为这两种方式不同。选择顺序无关。编号不同的糖果包视为不同，即使它们的糖果颜色相同。

输入格式

第一行包含一个整数 $N$。

接下来的 $N$ 行中，第 $i$ 行包含两个整数 - $a_i$ 和 $b_i$。

输出格式

输出一个整数表示答案。

约束

对于每项任务：

• $1 \le N \le 200\,000$.

• $1 \le a_i, b_i \le 10^9$.

• 任务 1（5 分）：$N \le 10$
• 任务 2（10 分）：$N \le 20$
• 任务 3（15 分）：$N \le 500$
• 任务 4（25 分）：$N \le 5000$
• 任务 5（10 分）：每个 $1 \le i \le N$，$a_i, b_i \le 2$
• 任务 6（35 分）：无额外约束

样例输入

9
1 2
1 3
2 1
1 1
2 2
1 3
3 1
1 1
1 1

样例输出

7

样例解释

一共有九袋糖果包。糖果包1有一个颜色为一的糖果和一个颜色为2的糖果；糖果包2有一个颜色为1的糖果和一个颜色为3的糖果，以此类推。

一共有七种方式选择三袋糖果包，如下：

• 选糖果包1、4、5：所有糖果的颜色分别是 1、2、1、1、2、2。有三个糖果是颜色1和三个糖果是颜色2。
• 选糖果包1、5、8：所有糖果的颜色分别是 1、2、2、2、1、1。
• 选糖果包1、5、9：所有糖果的颜色分别是 1、2、2、2、1、1。
• 选糖果包2、6、7：所有糖果的颜色分别是 1、3、1、3、3、1。
• 选糖果包3、4、5：所有糖果的颜色分别是 2、1、1、1、2、2。
• 选糖果包3、5、8：所有糖果的颜色分别是 2、1、2、2、1、1。
• 选糖果包3、5、9：所有糖果的颜色分别是 2、1、2、2、1、1。

一些无效的选择方式如下：

• 选糖果包1、2、3：所有糖果的颜色分别是 1、2、1、3、2、1。仅可以有两种颜色，而每种颜色只可以出现三次。
• 选糖果包7、8、9：所有糖果的颜色分别是 3、1、1、1、1、1。每种颜色应该出现三次。
• 选糖果包4、8、9：所有糖果的颜色分别是 1、1、1、1、1、1。必须有两种不同的颜色。

图一表示其中一种有效和三种无效的方式：

图一：一些有效和无效地选三个糖果包的例子。