Description
众所周知，Alice 和 Bob 是一对好朋友。今天，他们约好一起玩游戏。
一开始，他们各自有一张空白的纸条。接下来，他们会在纸条上依次写 \(n\) 个 \([1,m]\) 范围内的正整数。等 Alice 写完，Bob 在看到 Alice 写的纸条之后开始写他的纸条。
Alice 需要保证她写下的第 \(i\) 个数在集合 \(S_{i}\) 中，Bob 需要保证他写下的第 \(i\) 个数在集合 \(T_{i}\) 中。题目保证 \(1 \leq\left|S_{i}\right|,\left|T_{i}\right| \leq 2\) 。
Alice 喜欢相同，因此，她希望她写下的数与 Bob 写下的数对应位置相同的个数尽量多。Bob 喜欢不同，因此，他希望他写下的 \(n\) 个数 \(b_{1}, \ldots, b_{n}\) 互不相同。在此基础上，Bob 希望他写下的数与 Alice 写下的数对应位置相同的个数尽量少。
即设 Alice 写下的数为 \(a_{1}, \ldots, a_{n}\)，Bob 写下的数为 \(b_{1}, \ldots, b_{n}\)，记 \(X\) 为满足 \(1 \leq i \leq n, a_{i}=b_{i}\) 的下标 \(i\) 的个数，则
- Alice 希望最大化 \(X,\)
- Bob 在保证 \(b_{1}, \ldots, b_{n}\) 互不相同的前提下希望最小化 \(X\)。
你首先想知道 Bob 能否保证他写下的 \(n\) 个数互不相同。如果 Bob 能够做到，你想知道在双方均采取最优策略的前提下 \(X\) 的值会是多少。
\(n,m\leq 10^6,\sum n,\sum m\leq 1.5\times 10^6\)。
Solution
这题 Bob 在看到 Alice 写的纸条之后才开始写他的纸条！！
先做特殊性质 A。这个就是让你判断 \(b_1,\dots,b_n\) 能否互不相同。
考虑把所有 \(T_{i,0}\) 和 \(T_{i,1}\) 连边（如果 \(|T|=1\)，就连一条 \(T_{i,0}\) 的自环），题目就转化为将一个图中的边定向，使得每个点的入度不超过 \(1\)。
容易发现对于每个连通块，如果边数大于点数就一定不合法，否则这个连通块是个树或者基环树，一定合法。
然后考虑怎么对一个基环树求答案。
容易发现基环树除掉环的边的方向是定好的，只有环上的边有两种可能。设环的大小为 \(k\)。
所以 Alice 就只要在这 \(k\) 条边对应的 \(k\) 个集合中每个集合选一个数，使得两种方向答案的 \(\min\) 值最大。
首先对于 \(|S_i\cap T_i|=0\) 的边，显然没有贡献。\(|S_i\cap T_i|=1\) 的边，肯定选择那个交的数，这相当于已经确定了选的数。\(|S_i\cap T_i|=2\) 的边，就只能对于两种方向的一种产生贡献。
设 \(c_u\) 表示已经确定的数中第一种方向已有的贡献，\(c_u\) 表示已经确定的数中第二种方向已有的贡献，\(c\) 表示待确定的集合数量。
那么答案就是：
\[\max_{i=0}^{c}{\left\{\min\{c_u+i,c_v+c-i\}\right\}} \]这个暴力求就行了。
这一部分的时间复杂度：\(O(n)\)。
然后考虑树的情况。
显然定向方式就是选定一个点作为根的外向树。
对于交为 \(1\) 的边 \(u\to v\)，如果 \(u\) 是交的数，那么根一定在 \(v\) 的子树里，否则根一定在 \(v\) 的子树外。
这一部分的贡献可以用 dfs 序上差分维护。
设 \(f_i\) 表示以 \(i\) 为根的答案。
然后题目转化为对于所有交为 \(2\) 的边 \(u\to v\)，要选择把 \(v\) 子树内或子树外的 \(f\) 全加一，使得最后 \(\min\{f_1,\dots,f_n\}\) 最大。
观察可知如果两个点他们要将 \(f\) 加一的集合不交，则把这两个集合都换成原来的补集一定更优。
所以对于两个点 \(u,v\)，如果 \(u\) 是 \(v\) 的祖先，那么不能出现 \(u\) 选子树外和 \(v\) 选子树内的情况。如果 \(u\) 不是 \(v\) 祖先，那么不能出现 \(u\) 和 \(v\) 都选子树外。
于是根据这两个性质可以得到选子树的点一定构成一个到根的链，然后 dfs 一边用线段树维护答案即可。
这一部分的时间复杂度：\(O(n\log n)\)。
所以总的时间复杂度就是 \(O(n\log n)\)。
Code
#include <bits/stdc++.h>
// #define int int64_t
namespace FASTIO {
char ibuf[1 << 21], *p1 = ibuf, *p2 = ibuf;
char getc() {
return p1 == p2 && (p2 = (p1 = ibuf) + fread(ibuf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++;
}
template<class T> bool read(T &x) {
x = 0; int f = 0; char ch = getc();
while (ch < '0' || ch > '9') f |= ch == '-', ch = getc();
while (ch >= '0' && ch <= '9') x = (x * 10) + (ch ^ 48), ch = getc();
x = (f ? -x : x); return 1;
}
template<typename A, typename ...B> bool read(A &x, B &...y) { return read(x) && read(y...); }
char obuf[1 << 21], *o1 = obuf, *o2 = obuf + (1 << 21) - 1;
void flush() { fwrite(obuf, 1, o1 - obuf, stdout), o1 = obuf; }
void putc(char x) { *o1++ = x; if (o1 == o2) flush(); }
template<class T> void write(T x) {
if (!x) putc('0');
if (x < 0) x = -x, putc('-');
char c[40]; int tot = 0;
while (x) c[++tot] = x % 10, x /= 10;
for (int i = tot; i; --i) putc(c[i] + '0');
}
void write(char x) { putc(x); }
void write(char *x) { while (*x) putc(*x++); }
void write(const char *x) { while (*x) putc(*x++); }
template<typename A, typename ...B> void write(A x, B ...y) { write(x), write(y...); }
struct Flusher {
~Flusher() { flush(); }
} flusher;
} // namespace FASTIO
using FASTIO::read; using FASTIO::putc; using FASTIO::write;
const int kMaxN = 1e6 + 5;
int n, m;
int cnt[kMaxN], fa[kMaxN], sz[kMaxN], cnted[kMaxN];
std::vector<int> s[kMaxN], t[kMaxN];
std::vector<std::pair<int, int>> G[kMaxN];
int find(int x) {
return x == fa[x] ? x : fa[x] = find(fa[x]);
}
void unionn(int x, int y) {
int fx = find(x), fy = find(y);
if (fx != fy) {
fa[fx] = fy, sz[fy] += sz[fx], cnted[fy] += cnted[fx];
}
++cnted[fy];
}
void addedge(int u, int v, int id) {
G[u].emplace_back(v, id), unionn(u, v);
if (u != v) G[v].emplace_back(u, id);
}
namespace Cycle {
int res, p[kMaxN], pid[kMaxN], dep[kMaxN];
bool vis[kMaxN], onc[kMaxN];
std::vector<int> circ, circ_v;
void clear() {
std::fill_n(vis + 1, m, 0);
std::fill_n(onc + 1, m, 0);
std::fill_n(p + 1, m, 0);
}
void dfs1(int u, int fa, int faid) {
p[u] = fa, dep[u] = dep[fa] + 1, vis[u] = 1;
for (auto [v, id] : G[u]) {
if (id == faid) continue;
if (!vis[v]) {
pid[v] = id, dfs1(v, u, id);
} else if (dep[u] >= dep[v]) {
for (int i = u; i != v; i = p[i]) {
circ.emplace_back(pid[i]);
circ_v.emplace_back(i);
onc[i] = 1;
}
circ.emplace_back(id), onc[v] = 1, circ_v.emplace_back(v);
}
}
}
void dfs2(int u, int fa) {
for (auto [v, id] : G[u]) {
if (v == fa || onc[v]) continue;
res += (v == s[id][0] || v == s[id].back());
dfs2(v, u);
}
}
int solve(int rt) {
res = 0, circ.clear(), circ_v.clear(), dfs1(rt, 0, 0);
for (auto x : circ_v) dfs2(x, 0);
assert(circ.size() == circ_v.size());
int cu = 0, cv = 0, c = 0;
for (int i = 0; i < circ.size(); ++i) {
if (cnt[circ[i]] == 1) {
if (circ_v[i] == s[circ[i]][0] || circ_v[i] == s[circ[i]].back()) ++cu;
else ++cv;
} else if (cnt[circ[i]] == 2) {
++c;
}
}
if (circ.size() == 1) c *= 2;
return res + (abs(cu - cv) <= c ? (cu + cv + c) / 2 : std::min(cu, cv) + c);
}
} // namespace Cycle
namespace Tree {
struct SGT {
int mi[kMaxN * 4], tag[kMaxN * 4];
void pushup(int x) {
mi[x] = std::min(mi[x << 1], mi[x << 1 | 1]);
}
void addtag(int x, int v) {
mi[x] += v, tag[x] += v;
}
void pushdown(int x) {
if (!tag[x]) return;
addtag(x << 1, tag[x]), addtag(x << 1 | 1, tag[x]);
tag[x] = 0;
}
void build(int x, int l, int r) {
mi[x] = tag[x] = 0;
if (l == r) return;
int mid = (l + r) >> 1;
build(x << 1, l, mid), build(x << 1 | 1, mid + 1, r);
}
void update(int x, int l, int r, int ql, int qr, int v) {
if (l > qr || r < ql) {
return;
} else if (l >= ql && r <= qr) {
return addtag(x, v);
}
pushdown(x);
int mid = (l + r) >> 1;
update(x << 1, l, mid, ql, qr, v), update(x << 1 | 1, mid + 1, r, ql, qr, v);
pushup(x);
}
} sgt;
int res, dfnc;
int dfn[kMaxN], sz[kMaxN];
void dfs1(int u, int fa) {
dfn[u] = ++dfnc, sz[u] = 1;
for (auto [v, id] : G[u]) {
if (v == fa) continue;
dfs1(v, u);
sz[u] += sz[v];
}
}
void dfs2(int u, int fa) {
for (auto [v, id] : G[u]) {
if (v == fa) continue;
if (cnt[id] == 1) {
if (v == s[id][0] || v == s[id].back()) {
sgt.update(1, 1, dfnc, 1, dfn[v] - 1, 1), sgt.update(1, 1, dfnc, dfn[v] + sz[v], dfnc, 1);
} else {
sgt.update(1, 1, dfnc, dfn[v], dfn[v] + sz[v] - 1, 1);
}
} else if (cnt[id] == 2) {
sgt.update(1, 1, dfnc, 1, dfn[v] - 1, 1), sgt.update(1, 1, dfnc, dfn[v] + sz[v], dfnc, 1);
}
dfs2(v, u);
}
}
void dfs3(int u, int fa) {
res = std::max(res, sgt.mi[1]);
for (auto [v, id] : G[u]) {
if (v == fa) continue;
if (cnt[id] == 2) {
sgt.update(1, 1, dfnc, 1, dfn[v] - 1, -1);
sgt.update(1, 1, dfnc, dfn[v] + sz[v], dfnc, -1);
sgt.update(1, 1, dfnc, dfn[v], dfn[v] + sz[v] - 1, 1);
}
dfs3(v, u);
if (cnt[id] == 2) {
sgt.update(1, 1, dfnc, 1, dfn[v] - 1, 1);
sgt.update(1, 1, dfnc, dfn[v] + sz[v], dfnc, 1);
sgt.update(1, 1, dfnc, dfn[v], dfn[v] + sz[v] - 1, -1);
}
}
}
int solve(int rt) {
res = dfnc = 0;
dfs1(rt, 0);
sgt.build(1, 1, dfnc);
dfs2(rt, 0), dfs3(rt, 0);
return res;
}
} // namespace Tree
void dickdreamer() {
read(n, m);
for (int i = 1; i <= m; ++i) {
G[i].clear();
fa[i] = i, sz[i] = 1, cnted[i] = 0;
}
Cycle::clear();
for (int i = 1; i <= n; ++i) {
int c;
read(c);
s[i].clear();
for (int j = 1; j <= c; ++j) {
int x;
read(x);
s[i].emplace_back(x);
}
}
for (int i = 1; i <= n; ++i) {
int c;
read(c);
cnt[i] = 0, t[i].clear();
for (int j = 1; j <= c; ++j) {
int x;
read(x);
t[i].emplace_back(x);
for (auto y : s[i]) cnt[i] += (x == y);
}
if (c == 1) cnt[i] *= 2;
if (c == 1) addedge(t[i][0], t[i][0], i);
else addedge(t[i][0], t[i][1], i);
}
int ans = 0;
for (int i = 1; i <= m; ++i) {
if (i == find(i)) {
if (cnted[i] > sz[i]) return void(write("-1\n"));
else if (cnted[i] == sz[i]) ans += Cycle::solve(i);
else ans += Tree::solve(i);
}
}
write(ans, '\n');
}
int32_t main() {
#ifdef ORZXKR
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
#endif
int T = 1;
read(T);
while (T--) dickdreamer();
// std::cerr << 1.0 * clock() / CLOCKS_PER_SEC << "s\n";
return 0;
}