建议读者可以先去学习边三连通分量，因为本题的做法很大程度上与边三相关。

题意

给定一张 $n$ 个点 $m$ 条边的无向简单连通图和 $k$ 个二元组 $(a_i,b_i)$。初始时所有边权为 $0$，你需要选择两条不同的边，将它们的边权置为 $1$，使得 $\sum\operatorname{dist}(a_i,b_i)$ 最大，其中 $\operatorname{dist}(a_i,b_i)$ 表示 $a_i,b_i$ 之间的最短路长度。多测 $1\leq T\leq 10^5$，$3\leq n\leq 5\times 10^5$，$n-1\leq m\leq 5\times 10^5$，$1\leq \sum{m},\sum{k}\leq 5\times 10^5$。

题解

有点难。

$0/1$ 边权非常特殊，我们发现一条 $1$ 边对一个点对 $(a_i,b_i)$ 有贡献，当且仅当将这条边删去后 $a_i,b_i$ 不连通。

这类问题套路地考虑建出一棵 DFS 生成树，我们不妨先考察这棵生成树是一条链的时候怎么做。对于一条树边 $(i,i+1)$，设 $S_i$ 为所有跨过这条边的非树边集合，$cov_i$ 表示有多少 $(a_i,b_i)$ 的路径跨过这条边。

分类讨论一下删去的两条边的类型。有一些比较平凡的 case：

• 两条都是非树边：显然此时整张图还是连通的，贡献为 $0$。
• 两条都是满足 $S=\varnothing$ 的树边，或者一条满足 $S=\varnothing$，另一条不满足：此时贡献为 $cov_i+cov_j$ 或者 $cov_i$。

考虑如果其中一条树边的 $S_i\neq \varnothing$，我们发现此时必须要有 $|S_i|=1$，且另一条边恰好是 $S_i$ 中的那条非树边。此时 $[1,i]$ 和 $[i+1,n]$ 的部分就不连通了，因此贡献为 $cov_i$。我们可以使用 XOR Hash，为每条非树边赋一条随机边权，然后令一条树边的边权为 $S_i$ 中边权的异或和。差分求出每条树边的权值，使用哈希表即可轻松维护这种 case。

再考虑两条树边 $(i,i+1),(j,j+1)$ 满足 $S_i\neq\varnothing\land S_j\neq\varnothing$ 的 case，此时分为 $[1,i],[i+1,j],[j+1,n]$ 三个部分。可以发现，如果左、中部分有连边，或者中、右部分有连边，那么整张图一定还是连通的。因此 $S_i,S_j$ 中的边一定连接左、右部分，等价于 $S_i=S_j$。此时中部分和左、右部分分离开，那么容斥一下，贡献就是 $cov_i+cov_j-g(i,j)$，其中 $g(i,j)$ 表示有多少 $(a_i,b_i)$ 的路径同时跨过 $(i,i+1),(j,j+1)$ 这两条边。

暴力枚举无法承受。考虑按照 $S$ 划分等价类，把同一个等价类里的边拉出来计算贡献。对于每条边 $(i,i+1)$，设 $f_i(f_i>i)$ 表示与这条边匹配的树边，使得这两条边的贡献最大。我们指出 $f_i$ 单调不减。

:::info[证明] 钦定 $a_i<b_i$，于是显然

$$g(i,j)=\sum_{i=1}^k[a_i\leq i\land b_i>j]$$

考虑对于某个 $i$，我们计算出了其对应的 $f_i$。那么考察一个 $j>i$ 和一个匹配边 $f_j$ 满足 $f_j<f_i$。首先由于 $f_i$ 是最优的匹配边，我们有

$$\begin{align*} &cov_i+cov_{f_i}-g(i,f_i)\geq cov_i+cov_{f_j}-g(i,f_j)\\ \Leftrightarrow\ &cov_j+cov_{f_i}-g(i,f_i)\geq cov_j+cov_{f_j}-g(i,f_j)\tag{1} \end{align*}$$

设 $d_1=g(i,f_i)-g(j,f_i),d_2=g(i,f_j)-g(j,f_j)$。根据 $g$ 的定义，我们有

$$d_1=\sum_{i=1}^k[a_i\leq i\land b_i>f_i]-\sum_{i=1}^k[a_i\leq j\land b_i>f_i]=-\sum_{i=1}^k[i<a_i\leq j\land b_i>f_i]\\ d_2=\sum_{i=1}^k[a_i\leq i\land b_i>f_j]-\sum_{i=1}^k[a_i\leq j\land b_i>f_j]=-\sum_{i=1}^k[i<a_i\leq j\land b_i>f_j]$$

可以发现 $d_1\geq d_2$，因此我们可以在 $(1)$ 式左右两侧分别加上 $d_1,d_2$，变为

$$cov_j+cov_{f_i}-g(j,f_i)\geq cov_j+cov_{f_j}-g(j,f_j)$$

这就说明我们把 $f_j$ 移动到 $f_i$ 的位置一定不劣。$\Box$ :::

于是我们可以做决策单调性分治，这样就只需要计算 $\mathcal{O}(n\log{n})$ 次 $(i,j)$ 的贡献。$g(i,j)$ 显然是二维数点的形式，那么我们用主席树支持在线求矩形内点权和，即可做到 $\mathcal{O}(n\log^2{n})$。

尝试推广到任意形态的生成树上。我们使用树上差分依然可以求出每条树边的 $cov$，这样前面三种 case 都可以简单维护。

对于最后一种 case，注意到非树边都是返祖边，所以一个等价类中的边一定在一条祖先链上，我们还是可以和先前一样把这些边拉出来跑决策单调性分治，只需要修改 $g$ 的计算方式。具体来说，我们要计算 $g(i,j)$ 表示所有同时跨过 $(i,fa_i),(j,fa_j)$ 这两条边的 $(a_i,b_i)$ 路径数。钦定 $i$ 为 $j$ 的祖先，那么这实际上就是限制一个端点在 $sub_j$ 内，另一个端点在 $sub_i$ 外，显然可以看作 DFS 序平面上的至多两个矩形，所以同样用主席树维护即可。时间复杂度 $\mathcal{O}(n\log^2{n})$。

:::success[主要代码]

inline void dfs(int x) {
	st.f[0][dfn[x] = ++stmp] = fa[x], rev[stmp] = x;
	for (int i = G.head[x]; i; i = G.nxt[i]) if (i ^ fe[x] ^ 1) {
		int y = G.to[i];
		if (!dfn[y]) fa[y] = x, fe[y] = i, dfs(y), val[x] ^= val[y];
		else if (dfn[y] < dfn[x]) { ull v = gen(); nte[w[i >> 1] = v] = i >> 1, val[x] ^= v, val[y] ^= v; }
	}
	edfn[x] = stmp;
	ull cur = val[x];
	if (!cur) return;
	if (!id[cur]) vec[id[cur] = ++tot].clear();
	vec[id[cur]].push_back(x);
}
inline int calc(int x, int y) {
	int res = cov[x] + cov[y];
	if (dfn[x] > 1) res -= sgt.query(rt[dfn[y] - 1], rt[edfn[y]], 1, n, 1, dfn[x] - 1) << 1;
	if (edfn[x] < n) res -= sgt.query(rt[dfn[y] - 1], rt[edfn[y]], 1, n, edfn[x] + 1, n) << 1;
	return res;
}
inline void solve(int l, int r, int L, int R, const vector<int> &vc) {
	if (l > r || L > R) return;
	if (L == R) {
		for (int i = l; i <= r; ++i) f[i] = {calc(vc[i], vc[L]), L};
		return;
	}
	int mid = l + r >> 1, p = max(mid + 1, L); f[mid] = {-1, 0};
	for (int i = p; i <= R; ++i) chk_max(f[mid], {calc(vc[mid], vc[i]), i});
	solve(l, mid - 1, L, f[mid].second, vc), solve(mid + 1, r, f[mid].second, R, vc);
}

int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	cin >> T >> _;
	for (int tc = 1; tc <= T; ++tc) {
		cin >> n >> m, G.init();
		for (int i = 1, u, v; i <= m; ++i) cin >> u >> v, G.ins(u, v), G.ins(v, u);
		cin >> k;
		for (int i = 1, a, b; i <= k; ++i) cin >> a >> b, pth[i] = {a, b}, pth[i + k] = {b, a};
		clr(), dfs(1), st.init();
		for (int i = 1, a, b; i <= k; ++i) a = pth[i].first, b = pth[i].second, ++cov[a], ++cov[b], cov[lca(a, b)] -= 2;
		for (int i = n; i > 1; --i) cov[fa[rev[i]]] += cov[rev[i]];
		cov[0] = -1;
		int mx = 0;
		for (int x = 2; x <= n; ++x) {
			if (!val[x]) {
				if (mx) chk_max(ans, {cov[x] + cov[mx], fe[x] >> 1, fe[mx] >> 1});
				chk_max(ans, {cov[x], fe[x] >> 1, fe[x == 2 ? 3 : x - 1] >> 1});
				if (cov[x] > cov[mx]) mx = x;
			} else if (nte.count(val[x])) chk_max(ans, {cov[x], fe[x] >> 1, nte[val[x]]});
		}
		sort(pth + 1, pth + (k << 1) + 1, [](pii x, pii y) { return dfn[x.first] < dfn[y.first]; });
		for (int i = 1, j = 1; i <= n; ++i) {
			int lst = j, cur = rt[i - 1];
			while (j <= k << 1 && dfn[pth[j].first] == i) sgt.add(rt[i], cur, 1, n, dfn[pth[j++].second], 1), cur = rt[i];
			if (lst == j) rt[i] = rt[i - 1];
		}
		for (int i = 1; i <= tot; ++i) {
			auto &vc = vec[i];
			if (vc.size() == 1) continue;
			reverse(vc.begin(), vc.end());
			int sz = vc.size();
			solve(0, sz - 2, 0, sz - 1, vc);
			for (int j = 0; j < sz - 1; ++j) chk_max(ans, {f[j].first, fe[vc[j]] >> 1, fe[vc[f[j].second]] >> 1});
		}
        if (ans.val == -1) ans = {0, 1, 2};
		cout << ans.val << '\n';
		cout << G.to[ans.e1 << 1] << ' ' << G.to[ans.e1 << 1 | 1] << '\n';
		cout << G.to[ans.e2 << 1] << ' ' << G.to[ans.e2 << 1 | 1] << '\n';
	}
	return 0;
}

:::