非常好题目，使我代码旋转。
思路
考虑什么样的边有贡献。
我们首先提出原图的一个 dfs 树。
处理出经过关键点的树上路径在每一条树边的经过次数 \(v_i\)。
我们选点会有以下几种情况。
- 选两条割边 \(i,j\)，由于割边肯定是树边，所以答案就是 \(v_i+v_j\)。
- 选一条只被一条非树边覆盖的树边 \(i\)，如果一个树边只被一条非树边覆盖，那么我们把这两条边删掉，则树边连接的两部分就会断开，所以答案是 \(v_i\)。
- 选两条非树边覆盖集合相同的树边 \(i,j\)，可以发现，这两条边一定具有祖孙关系，那么此时若是短掉这两条边，整个树会被分成两个部分，其中上面于下面联通，但都不与中间联通，所以答案是 \(v_i+v_j-v_{i,j}\)，\(v_i,j\) 代表同时经过 \(i\) 与 \(j\) 的路径数量。
可以发现这个过程与边三连通分量极其相似，所以会边三连通分量有助于理解。
如何判断非树边覆盖集合是否相同。
可以使用异或哈希。
我们将每一条非树边随机一个随机权值。
然后把这条路径上的树边都异或这个值即可。
现在考虑如何计算答案。
对于第一种情况，我们直接求出最大的两条割边，但要注意，如果整张图只有一条割边 \(i\)，那么你可以选这条边再随便选一条边，得到 \(v_i\) 的权值。
对于第二种情况，我们把非树边的随机权值记下来，判断这条树边是否与一条非树边相等即可。
对于第三种情况，这是最难的一种情况。
首先考虑一个性质，颜色（我们把非树边覆盖集合称为颜色），一样的边只有不交与包含。
也就意味着不会出现像 \(\text{ABAB}\) 一样的段。
那么我们每次访问到一个点后，我们可以把从自己父亲到上一个颜色相同的点之间减 \(\text{inf}\)，相当于去掉这一段。
其他的贡献可以使用线段树合并往上维护。
具体的可以维护两棵线段树。
一棵不用动态开点，维护标记即可。
时间复杂度：\(O(n\log n)\)。
Code
#include <bits/stdc++.h>
using namespace std;
char buf[1<<21], *p1, *p2;
#define gc() (p1==p2&&(p2=(p1=buf)+cin.rdbuf()->sgetn(buf,1<<21),p1==p2)?EOF:*p1++)
template<typename T> inline void read(T &x) {
x = 0; int q = 1; char z;
while(!isdigit(z = gc())) if(z == '-') q = -1;
while(isdigit(z)) x = x * 10 + (z ^ 48), z = gc(); x *= q;
}
using i64 = long long;
using ull = unsigned long long;
const int N = 500010;
const int M = 599959;
const i64 I = 1e9;
int n, m, q, k, ct, nd, ans, ans1, ans2;
int a[N], b[N], u[N], v[N];
int ff[N], hd[N], bg[N];
int id[N], pr[N], tp[N];
int dp[N], val[N];
bool vis[N], ps[N];
bool tre[N << 1];
bool cut[N << 1];
ull hsh[N];
struct edge { int to, nxt, id; } e[N * 6];
struct Hash {
int ct, tt, h[M], v[M], c[M], nxt[M]; ull a[M];
inline int&operator[](const ull&tmp) {
int x = tmp % M;
for (int i = h[x]; i; i = nxt[i])
if (a[i] == tmp) return v[i];
if (!h[x]) c[++tt] = x;
nxt[++ct] = h[x], h[x] = ct;
return a[ct] = tmp, v[ct] = 0, v[ct];
}
inline bool chk(const ull&tmp) {
int x = tmp % M;
for (int i = h[x]; i; i = nxt[i])
if (a[i] == tmp) return 1;
return 0;
}
inline void clr() { while (tt) h[c[tt--]] = 0; ct = 0; }
} mp;
struct Node {
int u; i64 w;
inline bool operator<(const Node&tmp) const { return w < tmp.w; }
inline Node operator+(const i64&tmp) const { return {u, w + tmp}; }
inline void operator+=(const i64&tmp) { w += tmp; }
} mx;
mt19937_64 rng(random_device{}());
int rt[N];
int tg[N<<1], gt[N*19], vl[N*19];
int ls[N*19], rs[N*19];
Node v1[N<<1], v2[N*19];
inline Node get(int p, int q) { return (p ? v2[p] : v1[q]); }
inline void nnod(int&p, int q) {
p = ++nd, v2[p] = v1[q], ls[p] = rs[p] = gt[p] = vl[p] = 0;
}
inline void psh1(int p, int k) { tg[p] += k, v1[p] += k * I; }
inline void psh2(int p, int k) { gt[p] += k, v2[p] += k * I; }
inline void pdo1(int p, int mid) {
if (tg[p]) {
psh1(mid<<1, tg[p]);
psh1(mid<<1|1, tg[p]);
tg[p] = 0;
}
}
inline void pdo2(int p) {
if (gt[p]) {
if (ls[p]) psh2(ls[p], gt[p]);
if (rs[p]) psh2(rs[p], gt[p]);
gt[p] = 0;
}
}
inline void pup1(int p, int mid) {
v1[p] = max(v1[mid<<1], v1[mid<<1|1]);
}
inline void pup2(int p, int mid) {
v2[p] = max(get(ls[p], mid<<1), get(rs[p], mid<<1|1)) + vl[p];
}
inline void add1(int p, int l, int r, int L, int R, int k) {
if (L <= l && r <= R) psh1(p, k);
else {
int mid = (l + r) >> 1;
pdo1(p, mid);
if (mid >= L) add1(mid<<1, l, mid, L, R, k);
if (mid < R) add1(mid<<1|1, mid + 1, r, L, R, k);
pup1(p, mid);
}
}
inline void cge(int p, int l, int r, int k, int x) {
if (l == r) v1[p] = {l, x};
else {
int mid = (l + r) >> 1;
pdo1(p, mid);
if (mid >= k) cge(mid<<1, l, mid, k, x);
if (mid < k) cge(mid<<1|1, mid + 1, r, k, x);
pup1(p, mid);
}
}
inline void add2(int &p, int p2, int l, int r, int L, int R) {
if (!p) nnod(p, p2);
if (L <= l && r <= R) v2[p].w -= 2, vl[p] -= 2;
else {
int mid = (l + r) >> 1;
pdo2(p), pdo1(p2, mid);
if (mid >= L) add2(ls[p], mid<<1, l, mid, L, R);
if (mid < R) add2(rs[p], mid<<1|1, mid + 1, r, L, R);
pup2(p, mid);
}
}
inline void add3(int p, int p2, int l, int r, int L, int R, int k) {
if (!p) return;
if (L <= l && r <= R) psh2(p, k);
else {
int mid = (l + r) >> 1;
pdo2(p), pdo1(p2, mid);
if (mid >= L) add3(ls[p], mid<<1, l, mid, L, R, k);
if (mid < R) add3(rs[p], mid<<1|1, mid + 1, r, L, R, k);
pup2(p, mid);
}
}
inline int mer(int p1, int p2, int p3, int l, int r) {
if (!p1 || !p2) return p1 | p2;
vl[p1] += vl[p2];
if (l == r) v2[p1] = v1[p3] + vl[p1];
else {
int mid = (l + r) >> 1;
pdo2(p1), pdo2(p2), pdo1(p3, mid);
ls[p1] = mer(ls[p1], ls[p2], mid<<1, l, mid);
rs[p1] = mer(rs[p1], rs[p2], mid<<1|1, mid + 1, r);
pup2(p1, mid);
}
return p1;
}
inline Node ask(int p, int p2, int l, int r, int L, int R) {
if (L <= l && r <= R) return get(p, p2);
int mid = (l + r) >> 1;
pdo1(p2, mid), pdo2(p);
Node num = {0, (i64)-1e18};
if (mid >= L) num = max(num, ask(ls[p], mid<<1, l, mid, L, R));
if (mid < R) num = max(num, ask(rs[p], mid<<1|1, mid + 1, r, L, R));
return num + vl[p];
}
inline int gf(int x) { return (ff[x] == x ? x : ff[x] = gf(ff[x])); }
inline void add1(int x, int u) {
if (mx.w + x > ans) {
ans = mx.w + x;
ans1 = mx.u;
ans2 = u;
if (!ans1) ans1 = (ans2 == 1 ? 2 : 1);
}
mx = max((Node){u, x}, mx);
}
inline void add2(int x, int u, int v) {
if (x > ans) {
ans = x;
ans1 = u;
ans2 = v;
}
}
inline void dfs1(int x, int fa) {
vis[x] = 1, dp[x] = dp[fa] + 1, k = max(k, dp[x]);
for (int i = hd[x]; i; i = e[i].nxt) {
if (e[i].to == fa) continue;
if (vis[e[i].to]) {
if (dp[e[i].to] < dp[x]) {
ull val = rng();
hsh[e[i].to] ^= val;
hsh[x] ^= val;
mp[val] = e[i].id;
}
} else {
dfs1(e[i].to, x);
ff[e[i].to] = x;
hsh[x] ^= hsh[e[i].to], tre[i] = 1;
if (hsh[e[i].to] == 0) cut[i] = cut[i ^ 1] = 1;
}
}
int bx = 0;
for (int i = bg[x]; i; i = e[i].nxt) {
if (ps[e[i].to]) {
int y = a[e[i].to] + b[e[i].to] - x;
val[y]++;
val[gf(y)] -= 2;
val[x]++;
if (x != gf(y)) e[++ct] = {gf(y), bx}, bx = ct;
if (y != gf(y)) e[++ct] = {gf(y), bg[y]}, bg[y] = ct;
}
ps[e[i].to] = 1;
}
bg[x] = bx;
}
inline void dfs2(int x, int fa) {
for (int i = hd[x]; i; i = e[i].nxt) {
if (!tre[i]) continue;
int y = e[i].to;
dfs2(y, x);
val[x] += val[y];
if (cut[i]) add1(val[y], e[i].id);
if (mp.chk(hsh[y])) add2(val[y], e[i].id, mp[hsh[y]]);
}
}
inline void dfs3(int x, int fa, int di) {
if (di) id[dp[x]] = di;
if (hsh[x]) {
pr[x] = mp[hsh[x]], mp[hsh[x]] = x;
if (pr[x]) {
if (dp[pr[x]] + 1 <= dp[x] - 1) {
add1(1, 1, k, dp[pr[x]] + 1, dp[x] - 1, -1);
}
tp[x] = tp[pr[x]];
} else tp[x] = dp[x];
cge(1, 1, k, dp[x], val[x]);
}
for (int i = hd[x]; i; i = e[i].nxt) {
if (!tre[i]) continue;
dfs3(e[i].to, x, e[i].id);
rt[x] = mer(rt[x], rt[e[i].to], 1, 1, k);
}
for (int i = bg[x]; i; i = e[i].nxt) {
add2(rt[x], 1, 1, k, dp[e[i].to] + 1, dp[x]);
}
if (hsh[x]) {
if (tp[x] <= dp[x] - 1) {
Node num = ask(rt[x], 1, 1, k, tp[x], dp[x] - 1);
add2(num.w + val[x], id[num.u], di);
}
if (pr[x]) {
if (dp[pr[x]] + 1 <= dp[x] - 1) {
add1(1, 1, k, dp[pr[x]] + 1, dp[x] - 1, 1);
add3(rt[x], 1, 1, k, dp[pr[x]] + 1, dp[x] - 1, 1);
}
}
mp[hsh[x]] = pr[x];
}
}
inline void sol() {
read(n), read(m), k = 0, ct = 1;
for (int i = 1; i <= m; i++) {
read(u[i]), read(v[i]);
e[++ct] = {v[i], hd[u[i]], i}, hd[u[i]] = ct;
e[++ct] = {u[i], hd[v[i]], i}, hd[v[i]] = ct;
}
read(q);
for (int i = 1; i <= q; i++) {
read(a[i]), read(b[i]);
e[++ct] = {i, bg[a[i]]}, bg[a[i]] = ct;
e[++ct] = {i, bg[b[i]]}, bg[b[i]] = ct;
}
ans1 = 1, ans2 = 2;
iota(ff + 1, ff + n + 1, 1);
dfs1(1, 0);
dfs2(1, 0), mp.clr();
dfs3(1, 0, 0), mp.clr();
cout << ans << "\n";
cout << u[ans1] << " " << v[ans1] << "\n";
cout << u[ans2] << " " << v[ans2] << "\n";
ans = ans1 = ans2 = nd = 0, mx = {};
for (int i = 1; i <= n; i++) {
bg[i] = id[i] = rt[i] = dp[i] = val[i] = 0;
hd[i] = bg[i] = tp[i] = pr[i] = vis[i] = hsh[i] = 0;
}
for (int i = 1; i <= q; i++) ps[i] = 0;
for (int i = 1; i <= ct; i++) tre[i] = cut[i] = 0;
for (int i = 1; i <= n + n; i++) tg[i] = 0, v1[i] = {};
}
int main() {
ios::sync_with_stdio(0), cin.tie(0);
int t;
read(t);
while (t--) sol();
}