D2. Turtle and a MEX Problem (Hard Version)

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

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

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

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

Output

16
18
1281
4
6556785365
1842836177961

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

解题思路

  先给出赛时的做法。假设第 $i$ 个序列最小没出现的自然数是 $x_i$，第二小没出现的自然数是 $y_i$。如果 $k \ne x_i$，那么结合第 $i$ 个序列操作后有 $k = x_i$，否则有 $k = y_i$。为此我们可以进行 $x_i \to y_i$ 的连边，得到若干个 DAG。

  在 Easy Version 中由于可以多次选择同一个序列，因此对于任意一个 $k$ 一定可以通过操作到达 DAG 中最大的节点，所以答案就是 $\sum\limits_{k=0}^{m}{\max\{k, \max\{ y_i \} \}}$。

  而 Hard Version 中每个序列只能选择一次，因此每个 $k$ 不一定都能到达 DAG 中最大的节点。不妨考虑什么情况下 $k$ 可以到达某个 DAG 的最大节点。首先如果 $k$ 本身就是 DAG 中的节点那么一定可以。另外如果 DAG 中存在某个节点 $u$ 的出度至少为 $2$，那么我们可以先通过一次操作将 $k$ 变成 $u$，再通过 $u$ 一步一步变成最大节点。我们可以通过并查集维护每个 $x_i$ 和 $y_i$ 所在的 DAG，以及 DAG 中的最大节点。

  记 $r = \max\{ y_i \}$，对于 $k > r$ 的 $k$，显然不应该进行操作，答案就是 $k$ 本身。对于 $k \leq r$ 的情况，除了 $k$ 本身外，还可以变成最大的 $x_i$（赛时没考虑到这种情况 WA 麻了），以及存在出度至少为 $2$ 的节点的 DAG 中的最大节点，以及 $k$ 所在 DAG 中的最大节点（如果 $k$ 属于某个 DAG 的话）。取这几种情况的最大值即可。

  AC 代码如下，时间复杂度为 $O(\sum{l_i}\log{\sum{l_i}})$：

#include <bits/stdc++.h>
using namespace std;

typedef long long LL;

const int N = 2e5 + 5;

int x[N], y[N];
int s[N];
int fa[N], g[N];

int find(int x) {
    return fa[x] == x ? fa[x] : fa[x] = find(fa[x]);
}

void solve() {
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        int m;
        cin >> m;
        set<int> st;
        while (m--) {
            int x;
            cin >> x;
            st.insert(x);
        }
        for (int j = 0; true; j++) {
            if (!st.count(j)) {
                x[i] = j;
                for (int k = j + 1; true; k++) {
                    if (!st.count(k)) {
                        y[i] = k;
                        break;
                    }
                }
                break;
            }
        }
    }
    int r = *max_element(y, y + n);
    iota(fa, fa + r + 1, 0);
    memset(g, 0, r + 1 << 2);
    memset(s, 0, r + 1 << 2);
    for (int i = 0; i < n; i++) {
        g[x[i]] = x[i];
        g[y[i]] = y[i];
        s[x[i]]++;
    }
    for (int i = 0; i < n; i++) {
        int a = find(x[i]), b = find(y[i]);
        g[a] = max(g[a], g[b]);
        fa[b] = a;
    }
    int mx = 0;
    for (int i = 0; i < n; i++) {
        mx = max(mx, x[i]);
        if (s[x[i]] > 1) mx = max(mx, g[find(x[i])]);
    }
    LL ret = max(0ll, (m - r) * (m + r + 1ll)) / 2;
    r = min(r, m);
    for (int i = 0; i <= r; i++) {
        ret += max({i, mx, g[find(i)]});
    }
    cout << ret << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    
    return 0;
}

  然后是官方题解的做法。思路其实和上面的差不多，不过题解是在建出 DAG 后通过 dp 求出（DAG 上）每个节点可以到达的最大节点，定义为 $f(i)$。由于节点 $i$ 必定指向比 $i$ 大的节点，因此我们可以通过倒叙枚举 $i$ 进行 dp。

  一样的，当 $k > r$ 答案是 $k$ 本身。当 $k \leq r$，首先有 $f(k)$（如果 $k$ 不在任何 DAG 上有 $f(k) = 0$），还有出度至少为 $2$ 的节点 $u$ 的 $f(u)$，以及最重要的可以变成最大的 $x_i$。取这几种情况的最大值即可。

  AC 代码如下，时间复杂度为 $O(\sum{l_i}\log{\sum{l_i}})$：

#include <bits/stdc++.h>
using namespace std;

typedef long long LL;

const int N = 2e5 + 5;

int x[N], y[N];
int h[N], e[N], ne[N], idx;
int f[N];

void add(int u, int v) {
    e[idx] = v, ne[idx] = h[u], h[u] = idx++;
}

void solve() {
    int n, m;
    cin >> n >> m;
    int mx = 0, r = 0;
    for (int i = 0; i < n; i++) {
        int m;
        cin >> m;
        set<int> st;
        while (m--) {
            int x;
            cin >> x;
            st.insert(x);
        }
        for (int j = 0; true; j++) {
            if (!st.count(j)) {
                x[i] = j;
                mx = max(mx, j);
                for (int k = j + 1; true; k++) {
                    if (!st.count(k)) {
                        y[i] = k;
                        r = max(r, k);
                        break;
                    }
                }
                break;
            }
        }
    }
    idx = 0;
    memset(h, -1, r + 1 << 2);
    for (int i = 0; i < n; i++) {
        add(x[i], y[i]);
    }
    memset(f, 0, r + 1 << 2);
    for (int i = r; i >= 0; i--) {
        f[i] = i;
        int cnt = 0;
        for (int j = h[i]; j != -1; j = ne[j]) {
            f[i] = max(f[i], f[e[j]]);
            cnt++;
        }
        if (cnt > 1) mx = max(mx, f[i]);
    }
    LL ret = max(0ll, (m - r) * (m + r + 1ll) / 2);
    r = min(r, m);
    for (int i = 0; i <= r; i++) {
        ret += max(mx, f[i]);
    }
    cout << ret << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    
    return 0;
}

参考资料

  Codeforces Round 968 (Div. 2) Editorial - Codeforces：https://codeforces.com/blog/entry/132953