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 $ .

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 $ .

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 $ .