补题写题解，即可得牛币https://ac.nowcoder.com/discuss/988926

A

首先简化一下题意，等价于有 个区间 ，定义两个区间连通当且仅当它们交集非空，你可以任意添加区间，求使得 个区间连通需要添加的最小区间长度和。

将所有区间按 排序，然后每个合并小区间得到的大区间可以表示为下标的一个连续段，填补大区间之间的空隙即可。

时间复杂度 。

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 9;
int ans, id[N], n, r[N], x[N];
int main() {
    cin >> n;

    for (int i = 1; i <= n; ++i) 
        id[i] = i, scanf("%d%d", &x[i], &r[i]);

    sort(id + 1, id + n + 1, [&](int a, int b) { return x[a] - r[a] < x[b] - r[b]; });

    for (int ii = 2, mx = x[id[1]] + r[id[1]]; ii <= n; ++ii) {
        int i = id[ii];
        if (x[i] - r[i] > mx)
            ans += x[i] - r[i] - mx;
        mx = max(mx, x[i] + r[i]);
    }

    printf("%d", ans);
    return 0;
}

C

首先对于 和 的行特判一下，他们会挡住后面的所有人。

一个点造成的影响就是 两个点到他的射线的交。

对于同一行的两个点 ，其中 ，第一个点的影响范围会完全包含第二个点，所以有用的点只有 个。

画图会发现，造成的影响是一个折线图。具体的，对于一行 ，会存在一个 表示 都合法， 都不合法。并且我们可以做两遍，第一次求出 对每行的影响，再求出 对每行的影响，每一行的 最终就是两次求得的较小值。

到此有个显然的做法就是直接李超树，但是时间复杂度无法接受，我们需要一个线性的做法。

以 到每个点为例。从小到大枚举每一行 ，然后比较已有射线和当前射线 （其中 表示第 行横坐标最小的点。），更新为斜率较大的一条，然后更新这一行的 。

时间复杂度 。

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 2e5 + 9;
int n, m, k, q;
int x1[N], mn[N];
int X[N], Y[N];
signed main() {
    cin >> n >> m >> k >> q;

    for (int i = 1; i <= k; i++)
        scanf("%lld%lld", &X[i], &Y[i]);

    while (q--) {
        int id;
        cin >> id;
        scanf("%lld%lld", &X[id], &Y[id]);

        for (int i = 1; i <= m; i++)
            x1[i] = n + 1, mn[i] = n;

        for (int i = 1; i <= k; i++)
            x1[Y[i]] = min(x1[Y[i]], X[i]);

        int j = 0;

        for (int i = 1; i <= m; i++) { //(0,1)
            // (0,1,x1[i],i) (0,1,x1[j],j)
            if (x1[i] != n + 1 && (!j || x1[i] * (j - 1) - (i - 1)*x1[j] < 0))
                j = i;

            if (j == 1)
                mn[i] = min(mn[i], i == 1 ? x1[i] - 1 : n);
            else
                mn[i] = min(mn[i], j ? ((i - 1) * x1[j] - 1) / (j - 1) : n);
        }

        j = 0;

        for (int i = m; i >= 1; i--) { //(0,m)
            // (0,m,x1[i],i) (0,m,x1[j],j)
            if (x1[i] != n + 1 && (!j || x1[i] * (j - m) - (i - m)*x1[j] > 0))
                j = i;

            if (j == m)
                mn[i] = min(mn[i], i == m ? x1[i] - 1 : n);
            else
                mn[i] = min(mn[i], j ? ((m - i) * x1[j] - 1) / (m - j) : n);
        }

        int ans = 0;

        for (int i = 1; i <= m; i++)
            ans += mn[i];

        cout << ans << endl;
    }

    return 0;
}

D

首先根据圆的对称性， 和 是等效的，于是只需考虑 的答案。

显然摧毁的墙壁是一段劣弧，那么长度的大小关系就可以映射到弦长的大小关系。设电磁炮摧毁墙壁的端点为 ，则对应弦长长度为 ， 为定值，那么显然两点纵坐标之差的绝对值越大时弦长越大。

设 的两端点分别为 ，不妨设 ，令 为 的 值，则有 ，显然此时 垂直于 轴，即 ，弧长的计算使用极角相关知识即可。

#include <bits/stdc++.h>
using namespace std;
typedef long double ll;
int main() {
    int t_case;
    scanf("%d", &t_case);
    while (t_case--) {
        ll d, r, x, y;
        scanf("%Lf%Lf%Lf%Lf", &r, &x, &y, &d);
        ll p = sqrt(x * x + y * y);
        ll L = p - d, R = p + d;
        printf("%.10Lf\n", (acos(L / r) - acos(R / r)) * r);
    }
    return 0;
}

E

设 表示第一棵树上以 为根的子树和第二棵树上以 为根的子树的最大公共子序列的大小。

考虑更新 ，首先可以从所有的 取最大值继承过来。

若 ，那么 可以匹配。只需要再将 的儿子和 的儿子两两匹配，得到最大权值。

每次更新都枚举 ，然后建立一条边 ，边权为 。跑一遍最大权匹配，用最后所得的答案 去更新 即可。

分析时间复杂度。假设左部点有 个，右部点有 个，且 ，增广的时间复杂度就是

那么时间复杂度就是 级别。

#include <bits/stdc++.h>
using namespace std;
const int N = 5e2 + 9;
const int INF = 1e9;
int c1[N], c2[N];
vector<int>e1[N], e2[N];
int dp[N][N], w[N][N];
int km(int n, int m) {
    vector<int>u(n + 1), v(m + 1), p(m + 1), Fa(m + 1);

    for (int i = 1; i <= n; i++) {
        p[0] = i;
        int a = 0;
        vector<int>mn(m + 1, INF);
        vector<bool>used(m + 1, false);

        do {
            used[a] = true;
            int i0 = p[a], del = INF, b = 0;

            for (int j = 1; j <= m; ++j)
                if (!used[j]) {
                    int val = w[i0][j] - u[i0] - v[j];

                    if (val < mn[j])
                        mn[j] = val, Fa[j] = a;

                    if (mn[j] < del)
                        del = mn[j], b = j;
                }

            for (int j = 0; j <= m; ++j)
                if (used[j])
                    u[p[j]] += del, v[j] -= del;
                else
                    mn[j] -= del;

            a = b;
        } while (p[a] != 0);

        do {
            int b = Fa[a];
            p[a] = p[b];
            a = b;
        } while (a);
    }

    return -v[0];
}
int n, m;
void dfs2(int x, int fx, int i, int fa) {
    for (auto to : e2[i])
        if (to != fa)
            dfs2(x, fx, to, i);

    for (auto to : e2[i])
        if (to != fa)
            dp[x][i] = max(dp[x][i], dp[x][to]);

    for (auto to : e1[x])
        if (to != fx)
            dp[x][i] = max(dp[x][i], dp[to][i]);

    if (c1[x] == c2[i]) {
        int f = (e1[x].size() <= e2[i].size());

        for (int j = 0; j < e1[x].size(); j++)
            for (int k = 0; k < e2[i].size(); k++) {
                int v = -dp[e1[x][j]][e2[i][k]] * (e1[x][j] != fx && e2[i][k] != fa);
                f ? (w[j + 1][k + 1] = v) : (w[k + 1][j + 1] = v);
            }

        if (f)
            dp[x][i] = max(dp[x][i], 1 - km(e1[x].size(), e2[i].size()));
        else
            dp[x][i] = max(dp[x][i], 1 - km(e2[i].size(), e1[x].size()));

    }
}
void dfs(int x, int fa) {
    for (auto to : e1[x])
        if (to != fa)
            dfs(to, x);

    dfs2(x, fa, 1, 0);
}
signed main() {
    cin >> n >> m;

    for (int i = 1; i <= n; i++)
        scanf("%d", &c1[i]);

    for (int i = 1; i <= m; i++)
        scanf("%d", &c2[i]);

    for (int i = 1; i < n; i++) {
        int x, y;
        scanf("%d%d", &x, &y);
        e1[x].push_back(y);
        e1[y].push_back(x);
    }

    for (int i = 1; i < m; i++) {
        int x, y;
        scanf("%d%d", &x, &y);
        e2[x].push_back(y);
        e2[y].push_back(x);
    }

    dfs(1, 0);
    printf("%d\n", dp[1][1]);
    return 0;
}

F

先考虑如何快速做 操作。具体的，考虑如何快速合并两个有序的区间。动态开点值域线段树就非常方便。我们每次可以直接暴力合并。（当然，平衡树也可以）。

所以我们有一个做法，初始每个点都是一个区间，即一棵值域线段树。每次排序一个区间时，把完整在这个区间的进行合并。对于左右两端的，部分在区间内的线段树，我们使用线段树分裂分成两部分然后合并。

一个比较基础的询问就是询问区间和。具体地我们另开一个维护答案的数据结构。对于一整个区间，我们把这个区间的答案放在左端点上。每次询问区间，暴力查询两端散块，在维护答案的数据结构里查询整块答案。

那么对于这道题的询问，考虑没有 操作怎么快速维护。我们在线段树每个区间维护 表示起点奇偶性为 ，末尾奇偶性为 的最长答案。合并区间时合并答案。还有一个更方便的方法就是，一个区间 的答案就是这个区间的长度 减去相邻两个数奇偶性相同的个数。把这个东西同样的套到这道题上即可。

初始 个节点，每次分裂产生 个节点 ，时间复杂度

#include <bits/stdc++.h>
#define pi pair<int,int>
#define IT set<int>::iterator
using namespace std;
const int N = 1e5 + 9;
const int M = 1e7 + 9;
int read() {
    int f = 0, x = 0;
    char ch = getchar();

    while (!isdigit(ch)) {
        f |= (ch == '-');
        ch = getchar();
    }

    while (isdigit(ch)) {
        x = x * 10 + ch - '0';
        ch = getchar();
    }

    return f ? -x : x;
}
int n, m, a[N];
struct point {
    int sum;
    bool ok, vl, vr;
};
point operator+(point a, point b) {
    point res;
    res.ok = a.ok | b.ok;
    res.sum = a.sum + b.sum;
    res.sum += (a.vr == b.vl) && (a.ok && b.ok);
    res.vl = a.ok ? a.vl : b.vl;
    res.vr = b.ok ? b.vr : a.vr;
    return res;
}
struct tree {
#define ls p<<1
#define rs p<<1|1
    point t[N << 2];
    void add(int p, int l, int r, int nl, int x, pi y) {
        if (l == r) {
            t[p].ok = 1;
            t[p].sum = x;
            t[p].vl = y.first;
            t[p].vr = y.second;
            return;
        }

        int mid = l + r >> 1;

        if (nl <= mid)
            add(ls, l, mid, nl, x, y);
        else
            add(rs, mid + 1, r, nl, x, y);

        t[p] = t[ls] + t[rs];
    }
    void del(int p, int l, int r, int nl) {
        if (l == r) {
            t[p].ok = 0;
            t[p].sum = 0;
            t[p].vl = 0, t[p].vr = 0;
            return;
        }

        int mid = l + r >> 1;

        if (nl <= mid)
            del(ls, l, mid, nl);
        else
            del(rs, mid + 1, r, nl);

        t[p] = t[ls] + t[rs];
    }
    point get(int p, int l, int r, int nl, int nr) {
        if (l >= nl && r <= nr)
            return t[p];

        int mid = l + r >> 1;

        if (nr <= mid)
            return get(ls, l, mid, nl, nr);

        if (nl > mid)
            return get(rs, mid + 1, r, nl, nr);

        return get(ls, l, mid, nl, nr) + get(rs, mid + 1, r, nl, nr);
    }
#undef ls
#undef rs
} T;
int idx, rt[N];
int ls[M], rs[M], cnt[M], sum[M], tag[N];
bool vl[M], vr[M];
struct Tree {
    void push_up(int p) {
        sum[p] = sum[ls[p]] + sum[rs[p]];
        sum[p] += (vr[ls[p]] == vl[rs[p]]) && (ls[p] && rs[p]);
        vl[p] = ls[p] ? vl[ls[p]] : vl[rs[p]];
        vr[p] = rs[p] ? vr[rs[p]] : vr[ls[p]];
    }
    void add(int &p, int l, int r, int k) {
        cnt[p = ++idx] = 1;

        if (l == r) {
            vl[p] = vr[p] = k & 1;
            return;
        }

        int mid = (l + r) >> 1;
        k <= mid ? add(ls[p], l, mid, k) : add(rs[p], mid + 1, r, k);
        push_up(p);
    }
    int get(int p, int l, int r) {
        if (l == r)
            return l;

        int mid = (l + r) >> 1;
        return ls[p] ? get(ls[p], l, mid) : get(rs[p], mid + 1, r);
    }
    void merge(int &x, int y) {
        if (!(x && y)) {
            x |= y;
            return;
        }

        cnt[x] += cnt[y];
        merge(ls[x], ls[y]);
        merge(rs[x], rs[y]);
        push_up(x);
    }
    void split(int &p1, int p2, int k, int tag) {
        if (cnt[p2] == k)
            return;

        cnt[p1 = ++idx] = cnt[p2] - k;
        cnt[p2] = k;

        if (tag) {
            if (k <= cnt[rs[p2]])
                split(rs[p1], rs[p2], k, tag),
                      ls[p1] = ls[p2], ls[p2] = 0;
            else
                split(ls[p1], ls[p2], k - cnt[rs[p2]], tag);
        } else {
            if (k <= cnt[ls[p2]])
                split(ls[p1], ls[p2], k, tag),
                      rs[p1] = rs[p2], rs[p2] = 0;
            else
                split(rs[p1], rs[p2], k - cnt[ls[p2]], tag);
        }

        push_up(p1);
        push_up(p2);
    }
} G;
set<int>t;
IT work(int p) {
    auto it = t.lower_bound(p);

    if (*it == p)
        return it;

    --it;
    int x = *it;
    G.split(rt[p], rt[x], p - x, tag[p] = tag[x]);
    T.del(1, 1, n, x);
    pi res = make_pair(vl[rt[x]], vr[rt[x]]);

    if (tag[p])
        swap(res.first, res.second);

    T.add(1, 1, n, x, sum[rt[x]], res);
    res = make_pair(vl[rt[p]], vr[rt[p]]);

    if (tag[p])
        swap(res.first, res.second);

    T.add(1, 1, n, p, sum[rt[p]], res);
    return t.insert(p).first;
}
int main() {
    n = read(), m = read();
    t.insert(n + 1);

    for (int i = 1; i <= n; i++) {
        G.add(rt[i], 1, n, a[i] = read());
        t.insert(i);
        T.add(1, 1, n, i, 0, make_pair(a[i] & 1, a[i] & 1));
    }

    for (int i = 1; i <= m; i++) {
        int op = read() - 1, l = read(), r = read();

        if (op < 2) {
            auto L = work(l), R = work(r + 1);

            for (auto i = ++L; i != R; ++i)
                G.merge(rt[l], rt[*i]);

            tag[l] = op;
            pi res = make_pair(vl[rt[l]], vr[rt[l]]);

            if (op)
                swap(res.first, res.second);

            T.add(1, 1, n, l, sum[rt[l]], res);

            for (auto it = L; it != R; ++it)
                T.del(1, 1, n, *it);

            t.erase(L, R);
        } else {
            work(l), work(r + 1);
            printf("%d\n", r - l + 1 - T.get(1, 1, n, l, r).sum);
        }
    }
}

G

从高到低贪心放 ，那么答案有两种可能：

若 除了最后一位都是 ，答案就是 ，否则答案是 个 。

#include <bits/stdc++.h>
using namespace std;
int main(){
    string s;
    cin >> s;
    cout << max(s,string( s.size() - 1 ,'9'));
}

H

因为限制是对于某一个二进制位，完全背包就很麻烦。这启发考虑按位处理。

具体的，类似于二进制分组优化的想法，把一个物品拆成 份，从小到大枚举二进制位，每一位暴力做 背包。因为做到第 位的时候，加上的数是 的倍数，更低位的数是没有贡献的。于是可以大胆的弃掉。

表示做到第 位，现在背包体积 的方案数。

每次暴力 背包的复杂度显然不能接受。观察每次乘上去的式子 其中 表示二进制第 位被 掉的位置。他也等价于：
$\rm NTT$ 实现。

考虑到 不同的最多只有 个，意思是不同的二项式只有根号个。我们可以暴力求出点值，然后 回去，得到原本的多项式。相比分治 这个非常好写。

然后再暴力除掉下面的每个二项式，这相当于退掉 背包。因为总共的限制只有 个，每次退的时间复杂度是 ，和 同阶。所以这部分的时间复杂度是 。

题目要求体积小于等于 的方案数，我们直接乘上一个 转化为求恰好，那么每次进位只能保留和 二进制奇偶相同的体积。即 。进位最多进 ，数组只需要开到 即可。

#include <bits/stdc++.h>
using namespace std;
const int p = 998244353;
const int N = 1e5 + 5e4;
const int G = 3, Gi = 332748118;
const int lim = 40001;
int inv(int x, int base = p - 2) {
    int res = 1;

    while (base) {
        if (base & 1)
            res = 1ll * res * x % p;

        x = 1ll * x * x % p;
        base >>= 1;
    }

    return res;
}
int r[N << 1];
inline int get(int x) {
    int len = 1;

    while (len <= x)
        len <<= 1;

    return len;
}
void NTT(int *A, int len, int tag) {
    for (int i = 1; i <= len; i++)
        r[i] = (r[i >> 1] >> 1) | ((i & 1) ? (len >> 1) : 0);

    for (int i = 0; i < len; i++)
        if (i < r[i])
            swap(A[i], A[r[i]]);

    for (int mid = 1; mid < len; mid <<= 1) {
        int wn = inv(tag ? G : Gi, (p - 1) / (mid << 1));

        for (int j = 0; j < len; j += (mid << 1))
            for (int k = 0, w = 1; k < mid; k++, w = 1ll * w * wn % p) {
                int x = A[j + k], y = 1ll * w * A[j + k + mid] % p;
                A[j + k] = (x + y) % p;
                A[j + k + mid] = (x + p - y) % p;
            }
    }

    if (tag)
        return;

    int invlen = inv(len);

    for (int i = 0; i < len; i++)
        A[i] = 1ll * A[i] * invlen % p;
}
int a[N], A[N], F[N], g[N];
int n, K, cnt[N];
long long m;
vector<int>had[62];
int vis[N], tag;
signed main() {
    scanf("%d%lld%d", &n, &m, &K);
    a[0] = 1;
    ++cnt[1];

    for (int i = 1; i <= n; i++)
        scanf("%d", &a[i]), ++cnt[a[i]];

    for (int i = 1; i <= K; i++) {
        int x, y;
        scanf("%d%d", &x, &y);
        had[y].push_back(x);
    }

    int len = get(lim);
    int w = inv(3, (p - 1) / len);
    A[0] = 1;

    for (int i = 1; i < len; i++)
        A[i] = 1ll * A[i - 1] * w % p;

    for (int i = 0; i < len; i++)
        F[i] = 1;

    for (int i = 0; i <= lim; i++)
        if (cnt[i])
            for (int j = 0; j < len; j++)
                F[j] = 1ll * F[j] * inv((A[(j * i) & (len - 1)] + 1) % p, cnt[i]) % p;

    NTT(F, len, 0);
    len = get(2 * lim);
    memset(A, 0, sizeof(A));
    A[0] = 1;

    for (int i = 0; (i <= 60) && m; i++) {
        memcpy(g, F, sizeof(F));
        ++tag;

        for (auto x : had[i])
            if (vis[x] != tag) {
                vis[x] = tag;

                for (int j = a[x]; j <= lim; j++)
                    g[j] = (g[j] + p - g[j - a[x]]) % p;
            }

        NTT(A, len, 1);
        NTT(g, len, 1);

        for (int j = 0; j < len; j++)
            g[j] = 1ll * g[j] * A[j] % p;

        NTT(g, len, 0);
        memset(A, 0, sizeof(A));

        for (int j = m % 2; j <= 2 * lim; j += 2)
            A[j >> 1] = g[j];

        m >>= 1;
    }

    printf("%d", A[0]);
    return 0;
}

I

题目有个条件就是，初始手牌每一种最多两张。那么最优策略就是，只要新摸到的牌能和手中的单牌凑出对子，就留着，打出一张单牌；否则打出摸到的牌。

那么就可以考虑一个暴力的 表示已经摸了 张牌，手上有 张单牌还需进行的期望轮数。

首先牌库里还有的牌有 张

若摸到的是手中的单牌，期望为 ，否则为

注意，手中的单牌在牌库里一定剩下 张，否则一定在之前凑一起了。

其中手中只剩一张牌并且摸到了需要的要特判转移，或者记忆化搜索。

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int p = 1e9 + 7;
int dp[200][14];
int inv(int x, int base = p - 2) {
    int res = 1;

    while (base) {
        if (base & 1)
            res = 1ll * res * x % p;

        x = 1ll * x * x % p;
        base >>= 1;
    }

    return res;
}
//136-13=123
char s[100];
int sta[100], top;
int dfs(int a, int c) {
    if (c == -1) {
        return 0;
    }

    if (dp[a][c] != -1)
        return dp[a][c];

    int res = 0;

    if (123 - a - c * 3)
        res += 1ll * (123 - a - c * 3) * inv(123 - a) % p * dfs(a + 1, c) % p;

    res += 1ll * (3 * c) * inv(123 - a) % p * dfs(a + 1, c - 2) % p;
    return dp[a][c] = (res + 1) % p;

}
signed main() {
    int q;
    cin >> q;
    memset(dp, -1, sizeof dp);

    for (int k = 1; k <= q; k++) {
        scanf("%s", s + 1);

        for (int i = 1; i <= 13; i++)
            sta[i] = (s[i * 2 - 1] - '0') * 100 + (s[i * 2] - 'a');

        sort(sta + 1, sta + 1 + 13);
        int x = 0;

        for (int i = 1; i <= 12; i++)
            if (sta[i] == sta[i + 1])
                x++;

        printf("Case #%d: %lld\n", k, (dfs(0, 13 - 2 * x)) % p);
    }

    return 0;
}

J

首先可以观察出，若两个点的答案集合有交集，则这两个集合一定是包含关系（严谨证明见出题人sol），因此我们可以尝试将每个点的后继合并到这个点，最后输出最大的集合大小。

暴力合并的复杂度显然是无法接受的，因此考虑如下技巧：

若该后继的某个前驱已经在当前点的答案集合，则将该前驱直接从后继的前驱集合中删去。否则说明当前点无法被合并，直接退出循环。最后将当前点插入后继的前驱集合。这样可以避免无意义查询，使得点 的遍历次数是 的。

但是合并后继时貌似有点问题：我们会将后继的后继当成新的后继，若我们构造一个链套菊花图，使得菊花图部分的点都无法被合并但链部分的点都能被合并，则菊花图部分的点会被加入链长次，这样时间复杂度就被卡到了 。

解决方案当然是有的，若我们从链顶开始做，就能避免这一情况，因此我们判断若当前点有唯一前驱且前驱编号比自己大（避免在出现环时出错），则不处理当前点，等到处理前驱时再考虑。

时间复杂度也许是

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
struct dsu {
    int fa[N], siz[N];
    inline void init(int k) {
        for (int i = 1; i <= k; ++i) fa[i] = i, siz[i] = 1;
    }
    int find(int k) { return k == fa[k] ? k : fa[k] = find(fa[k]); }
    inline bool merge(int x, int y) {
        x = find(x), y = find(y);
        if (x != y) {
            fa[x] = y, siz[y] += siz[x];
            return true;
        }
        return false;
    }
} d;
int deg[N], n, num, t_case;
set<int> fa[N], to[N];
bool vis[N];
int main() {
    scanf("%d", &t_case);
    while (t_case--) {
        scanf("%d", &n);
        for (int i = 1; i <= n; ++i) fa[i].clear(), to[i].clear();
        for (int i = 1; i <= n; ++i) {
            scanf("%d", deg + i);
            for (int j = 1, x; j <= deg[i]; ++j) {
                scanf("%d", &x);
                fa[i].insert(x);
                to[x].insert(i);
            }
        }
        int ans = 0;
        d.init(n);
        for (int i = 1; i <= n; ++i)
            if (d.find(i) == i) {
                if (fa[i].size() == 1 && *fa[i].begin() > i)
                    continue;
                auto update = [&](int k) {
                    for (auto it = to[k].begin(); it != to[k].end(); ++it)
                        if (d.find(*it) != *it)
                            it = to[k].erase(it);
                };
                update(i);
                queue<int> q;
                for (int j : to[i]) q.push(j);
                while (q.size()) {
                    int p = q.front();
                    q.pop();
                    if (!to[i].count(p))
                        continue;
                    for (auto it = fa[p].begin(); it != fa[p].end();) {
                        if (d.find(*it) == i)
                            it = fa[p].erase(it);
                        else {
                            to[i].insert(p);
                            goto skip;
                        }
                    }
                    d.merge(p, i);
                    to[i].erase(p);
                    update(p);
                    for (int j : to[p])
                        if (i != j)
                            q.push(j), to[i].insert(j);
                skip:;
                    fa[p].insert(i);
                }
                ans = max(ans, d.siz[i]);
            }
        printf("Case #%d: %d\n", ++num, ans);
    }
    return 0;
}