CF2185G.Mixing MEXes

You are given $n$ arrays $a_1, a_2, \ldots, a_n$.

The following operation is performed exactly once:

• Choose any array among $a_1, a_2, \ldots, a_n$. Suppose you've chosen array $a_i$ ($1 \leq i \leq n$).
• Choose any element in array $a_i$. Suppose you've chosen the $j$-th element of $a_i$, denoted by $a_{i,j}$ ($1 \leq j \leq |a_i|$, where $|a_i|$ denotes the length of array $a_i$).
• Choose any other array among $a_1, a_2, \ldots a_n$ that is not $a_i$. Suppose you've chosen $a_k$ ($1 \leq k \leq n, k \neq i$).
• Add $a_{i,j}$ to the back of array $a_k$. Then, remove $a_{i,j}$ from $a_i$.
• The value of this operation $(i,j,k)$ is defined as the sum of each array's $\operatorname{MEX}$ after the operation is performed. More formally, the value of an operation after the operation is performed is $\sum_{i=1} ^{n} \operatorname{MEX}(a_i)$.

Evaluate the sum of the values of all possible distinct independent operations. Two operations are distinct if the ordered triple of integers $(i,j,k)$ is different.

$\operatorname{MEX}(a)$ is defined as the smallest non-negative integer that is not present in the array. For example, $\operatorname{MEX}([1, 2, 0, 5])$ is $3$, and $\operatorname{MEX}([1, 2, 4, 9])$ is $0$.

给你 $n$ 个数组 $a_1, a_2, \ldots, a_n$。

以下操作恰好执行一次：

• 在 $a_1, a_2, \ldots, a_n$ 中任选一个数组。假设你选择了数组 $a_i$（其中 $1 \leq i \leq n$）。
• 在数组 $a_i$ 中任选一个元素。假设你选择了 $a_i$ 的第 $j$ 个元素，记为 $a_{i,j}$（其中 $1 \leq j \leq |a_i|$，$|a_i|$ 表示数组 $a_i$ 的长度）。
• 在 $a_1, a_2, \ldots, a_n$ 中另选一个不同于 $a_i$ 的数组。假设你选择了 $a_k$（其中 $1 \leq k \leq n$ 且 $k \neq i$）。
• 将 $a_{i,j}$ 添加到数组 $a_k$ 的末尾；然后从 $a_i$ 中删除 $a_{i,j}$。
• 此操作 $(i,j,k)$ 的值定义为：操作执行后，所有数组的 $\operatorname{MEX}$ 值之和。更准确地说，该操作的值为 $\sum_{i=1} ^{n} \operatorname{MEX}(a_i)$。

请计算所有可能的、互不相同的独立操作的值之和。若两个操作对应的三元组 $(i,j,k)$（有序整数三元组）不同，则称这两个操作互不相同。

$\operatorname{MEX}(a)$ 定义为数组 $a$ 中未出现的最小非负整数。例如，$\operatorname{MEX}([1, 2, 0, 5]) = 3$，而 $\operatorname{MEX}([1, 2, 4, 9]) = 0$。

The first line of the input contains a single integer $t$ ($1 \leq t \leq 10^4$) — the number of test cases.

The first line of each test case contains a single integer $n$ ($2 \le n \le 2 \cdot 10^5$) — the number of arrays.

The next $n$ lines start with $l_i$ ($1 \le l_i \le 10^5$) — the length of the $i$th array — then contain $l_i$ integers $a_1, a_2, \ldots, a_{l_i}$ ($0 \le a_{i_j} \le 10^6$) — the array $a_i$.

It is guaranteed that the sum of $l_i$ over all test cases does not exceed $2 \cdot 10^5$.

输入的第一行包含一个整数 $t$（$1 \leq t \leq 10^4$）—— 表示测试用例的数量。

每个测试用例的第一行包含一个整数 $n$（$2 \le n \le 2 \cdot 10^5$）—— 表示数组的个数。

接下来的 $n$ 行，每行以 $l_i$（$1 \le l_i \le 10^5$）开头，表示第 $i$ 个数组的长度；随后是 $l_i$ 个整数 $a_1, a_2, \ldots, a_{l_i}$（$0 \le a_{i_j} \le 10^6$）—— 即数组 $a_i$。

保证所有测试用例中 $l_i$ 的总和不超过 $2 \cdot 10^5$。

For each test case, output the sum of the values of all possible distinct operations.

对于每个测试用例，输出所有可能的不同操作的值的总和。

For the first test case, we have 3 possible distinct operations:

• $i = 1, j = 1, k = 2$: The arrays are now [] and [$0, 1, 2$], which have a $\operatorname{mex}$ of $0$ and $3$ respectively, so the value of the operation is $3$.
• $i = 2, j = 1, k = 1$: The arrays are now [$0, 1$] and [$2$], which have a $\operatorname{mex}$ of $2$ and $0$ respectively, so the value of the operation is $2$.
• $i = 2, j = 2, k = 1$: The arrays are now [$0, 2$] and [$1$], which have a $\operatorname{mex}$ of $1$ and $0$ respectively, so the value of the operation is $1$.

For the second test case, since no array contains a zero, the value of all operations will be $0$.

对于第一个测试用例，我们有 3 种可能的互不相同的操作：

• $i = 1, j = 1, k = 2$：此时两个数组分别为 [] 和 [$0, 1, 2$]，它们的 $\operatorname{mex}$ 值分别为 $0$ 和 $3$，因此该操作的值为 $3$。
• $i = 2, j = 1, k = 1$：此时两个数组分别为 [$0, 1$] 和 [$2$]，它们的 $\operatorname{mex}$ 值分别为 $2$ 和 $0$，因此该操作的值为 $2$。
• $i = 2, j = 2, k = 1$：此时两个数组分别为 [$0, 2$] 和 [$1$]，它们的 $\operatorname{mex}$ 值分别为 $1$ 和 $0$，因此该操作的值为 $1$。

对于第二个测试用例，由于没有任何数组包含 $0$，所有操作的值均为 $0$。