CF1598D Training Session

Monocarp 是 Berland State University 编程队的教练。他决定为他的队伍准备一次训练赛题集。 Monocarp 有 $n$ 道题目，这些题目他的学生们都还没有见过。第 $i$ 道题有一个主题 $a_i$（是 $1$ 到 $n$ 之间的整数）和一个难度 $b_i$（是 $1$ 到 $n$ 之间的整数）。所有题目都是不同的，即不存在两道题目同时拥有相同的主题和难度。 Monocarp 决定从这 $n$ 道题目中恰好选出 $3$ 道题组成题集。选出的题目需要满足以下两个条件中的至少一个（也可以同时满足）： - 这三道题的主题各不相同； - 这三道题的难度各不相同。 你的任务是计算有多少种方式可以选出满足要求的三道题。

第一行包含一个整数 $t$（$1 \le t \le 50000$），表示测试用例的数量。 每个测试用例的第一行包含一个整数 $n$（$3 \le n \le 2 \cdot 10^5$），表示 Monocarp 拥有的题目数量。 接下来的 $n$ 行中，第 $i$ 行包含两个整数 $a_i$ 和 $b_i$（$1 \le a_i, b_i \le n$），分别表示第 $i$ 道题的主题和难度。 保证不存在两道题目同时拥有相同的主题和难度。 所有测试用例中 $n$ 的总和不超过 $2 \cdot 10^5$。

输出满足题意的三道训练题的选法数量。

在第一个样例中，可以选择以下三道题的组合： - 题目 $1$、$2$、$4$； - 题目 $1$、$3$、$4$； - 题目 $2$、$3$、$4$。 因此，方案数为 $3$。 由 ChatGPT 4.1 翻译