Turtle and a MEX Problem (Hard Version)
Contest: Codeforces Round 968 (Div. 2)
Difficulty rating: 2100
Tags: dfs and similar, dp, graphs, greedy, implementation, math

The two versions are different problems. In this version of the problem, you can't choose the same integer twice or more. You can make hacks only if both versions are solved.

One day, Turtle was playing with $$$n$$$ sequences. Let the length of the $$$i$$$-th sequence be $$$l_i$$$. Then the $$$i$$$-th sequence was $$$a_{i, 1}, a_{i, 2}, \ldots, a_{i, l_i}$$$.

Piggy gave Turtle a problem to solve when Turtle was playing. The statement of the problem was:

- There was a non-negative integer $$$x$$$ at first. Turtle would perform an arbitrary number (possibly zero) of operations on the integer.
- In each operation, Turtle could choose an integer $$$i$$$ such that $$$1 \le i \le n$$$ and $$$i$$$ wasn't chosen before, and set $$$x$$$ to $$$\text{mex}^{\dagger}(x, a_{i, 1}, a_{i, 2}, \ldots, a_{i, l_i})$$$.
- Turtle was asked to find the answer, which was the maximum value of $$$x$$$ after performing an arbitrary number of operations.

Turtle solved the above problem without difficulty. He defined $$$f(k)$$$ as the answer to the above problem when the initial value of $$$x$$$ was $$$k$$$.

Then Piggy gave Turtle a non-negative integer $$$m$$$ and asked Turtle to find the value of $$$\sum\limits_{i = 0}^m f(i)$$$ (i.e., the value of $$$f(0) + f(1) + \ldots + f(m)$$$). Unfortunately, he couldn't solve this problem. Please help him!

$$$^{\dagger}\text{mex}(c_1, c_2, \ldots, c_k)$$$ is defined as the smallest non-negative integer $$$x$$$ which does not occur in the sequence $$$c$$$. For example, $$$\text{mex}(2, 2, 0, 3)$$$ is $$$1$$$, $$$\text{mex}(1, 2)$$$ is $$$0$$$.

Input format:
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). The description of the test cases follows.

The first line of each test case contains two integers $$$n, m$$$ ($$$1 \le n \le 2 \cdot 10^5, 0 \le m \le 10^9$$$).

Each of the following $$$n$$$ lines contains several integers. The first integer $$$l_i$$$ ($$$1 \le l_i \le 2 \cdot 10^5$$$) represents the length of the $$$i$$$-th sequence, and the following $$$l_i$$$ integers $$$a_{i, 1}, a_{i, 2}, \ldots, a_{i, l_i}$$$ ($$$0 \le a_{i, j} \le 10^9$$$) represent the elements of the $$$i$$$-th sequence.

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

Output format:
For each test case, output a single integer — the value of $$$\sum\limits_{i = 0}^m f(i)$$$.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
In the first test case, when $$$x$$$ is initially $$$2$$$, Turtle can choose $$$i = 3$$$ and set $$$x$$$ to $$$\text{mex}(x, a_{3, 1}, a_{3, 2}, a_{3, 3}, a_{3, 4}) = \text{mex}(2, 7, 0, 1, 5) = 3$$$. It can be proved that Turtle can't make the value of $$$x$$$ greater than $$$3$$$, so $$$f(2) = 3$$$.

It can be seen that $$$f(0) = 3$$$, $$$f(1) = 3$$$, $$$f(2) = 3$$$, $$$f(3) = 3$$$, and $$$f(4) = 4$$$. So $$$f(0) + f(1) + f(2) + f(3) + f(4) = 3 + 3 + 3 + 3 + 4 = 16$$$.

In the second test case, when $$$x$$$ is initially $$$1$$$, Turtle can choose $$$i = 1$$$ and set $$$x$$$ to $$$\text{mex}(x, a_{1, 1}, a_{1, 2}, a_{1, 3}, a_{1, 4}, a_{1, 5}) = \text{mex}(1, 0, 2, 0, 4, 11) = 3$$$. It can be proved that Turtle can't make the value of $$$x$$$ greater than $$$3$$$, so $$$f(1) = 3$$$.

It can be seen that $$$f(0) = 4$$$, $$$f(1) = 3$$$, $$$f(2) = 4$$$, $$$f(3) = 3$$$, and $$$f(4) = 4$$$. So $$$f(0) + f(1) + f(2) + f(3) + f(4) = 4 + 3 + 4 + 3 + 4 = 18$$$.

In the fourth test case, it can be seen that $$$f(0) = 3$$$ and $$$f(1) = 1$$$. So $$$f(0) + f(1) = 3 + 1 = 4$$$.

Example input:
6
3 4
2 0 2
3 2 3 3
4 7 0 1 5
3 4
5 0 2 0 4 11
1 1
5 1 3 0 3 3
2 50
2 1 2
2 1 2
1 1
7 1 2 4 1 4 9 5
4 114514
2 2 2
5 7 3 6 0 3
3 0 1 1
5 0 9 2 1 5
5 1919810
1 2
2 324003 0
3 1416324 2 1460728
4 1312631 2 0 1415195
5 1223554 192248 2 1492515 725556

Example output:
16
18
1281
4
6556785365
1842836177961

Editorial:
Please first read the solution for problem D1.
Construct a directed graph. For the $$$i$$$-th sequence, add a directed edge from $$$u_i$$$ to $$$v_i$$$.
In each operation, you can either move along an outgoing edge of $$$x$$$ or move to any vertex $$$u$$$ and remove one of its outgoing edges.
Let $$$f_i$$$ be the maximum vertex number that can be reached starting from vertex $$$i$$$ by continuously selecting one outgoing edge in the directed graph. This can be solved using DP in reverse order from large to small.
Firstly, the answer for $$$x$$$ is at least $$$f_x$$$. Additionally, the answer for every $$$x$$$ is at least $$$\max\limits_{i=1}^n u_i$$$. Moreover, for any vertex $$$i$$$ with outdegree greater than 1, the answer for every $$$x$$$ is at least $$$f_i$$$, since you can disconnect any outgoing edge from $$$i$$$ except the one leading to $$$f_i$$$.
Let $$$k = \max\limits_{i=1}^n v_i$$$. For values $$$\le k$$$, we can directly enumerate and calculate. For values $$$> k$$$, they won't be operated.
Time complexity: $$$O(\sum l_i)$$$ per test case.