308914: CF1598D. Training Session
Memory Limit:256 MB
Time Limit:2 S
Judge Style:Text Compare
Creator:
Submit:0
Solved:0
Description
Training Session
题意翻译
多组询问,每次给定 $n$ 个二元组 $(a_i,b_i)$,保证任意两个二元组的 $a_i$ 或者 $b_i$ 至少一个不同。求从这 $n$ 个二元组中选三个满足 $a_i$ 或者 $b_i$ 至少一个两两不同的方案数。 $\sum n\leq 2\cdot 10^5,a_i,b_i\leq n$。 Translated by LinkZelda.题目描述
Monocarp is the coach of the Berland State University programming teams. He decided to compose a problemset for a training session for his teams. Monocarp has $ n $ problems that none of his students have seen yet. The $ i $ -th problem has a topic $ a_i $ (an integer from $ 1 $ to $ n $ ) and a difficulty $ b_i $ (an integer from $ 1 $ to $ n $ ). All problems are different, that is, there are no two tasks that have the same topic and difficulty at the same time. Monocarp decided to select exactly $ 3 $ problems from $ n $ problems for the problemset. The problems should satisfy at least one of two conditions (possibly, both): - the topics of all three selected problems are different; - the difficulties of all three selected problems are different. Your task is to determine the number of ways to select three problems for the problemset.输入输出格式
输入格式
The first line contains a single integer $ t $ ( $ 1 \le t \le 50000 $ ) — the number of testcases. The first line of each testcase contains an integer $ n $ ( $ 3 \le n \le 2 \cdot 10^5 $ ) — the number of problems that Monocarp have. In the $ i $ -th of the following $ n $ lines, there are two integers $ a_i $ and $ b_i $ ( $ 1 \le a_i, b_i \le n $ ) — the topic and the difficulty of the $ i $ -th problem. It is guaranteed that there are no two problems that have the same topic and difficulty at the same time. The sum of $ n $ over all testcases doesn't exceed $ 2 \cdot 10^5 $ .
输出格式
Print the number of ways to select three training problems that meet either of the requirements described in the statement.
输入输出样例
输入样例 #1
2
4
2 4
3 4
2 1
1 3
5
1 5
2 4
3 3
4 2
5 1
输出样例 #1
3
10