CF1648F Two Avenues

可以在 [P13542](https://www.luogu.com.cn/problem/P13542) 评测本题。

为了让伯兰德的首都更具吸引力，伟大的国王提出了如下方案：选择城市中的两条街道，将它们命名为大道。这两条大道将被宣布为极其重要的历史地标，旨在吸引来自世界各地的游客。 首都可以用一个图来表示，顶点代表十字路口，边代表直接连接两个十字路口的街道。图中共有 $n$ 个顶点和 $m$ 条边，任意一条街道都可以双向通行。任意两个十字路口之间都可以仅通过街道到达，且每条街道连接的是两个不同的十字路口，没有两条街道连接同一对十字路口。 为了减少普通市民在大道上的通行量，决定对每条大道的双向通行都收取过路费。每经过大道一次需支付 $1$ 图格里克，其他街道免费。 分析师收集了 $k$ 位市民的样本，第 $i$ 位市民需要从十字路口 $a_i$ 前往十字路口 $b_i$。选定两条大道后，每位市民都会选择总费用最少的路径上下班。 为了让收入最大化，需要选择两条街道作为大道，使得所有 $k$ 位市民支付的总图格里克数最大。请你帮国王计算：根据给定的城市结构和市民样本，应该选择哪两条街道作为大道，以及在此选择下市民们总共会支付多少图格里克。

每个测试包含多组数据。第一行包含两个整数，$t$（$1 \leq t \leq 10^5$）表示测试组数。接下来是每组测试的数据。 每组测试的第一行包含两个整数 $n$ 和 $m$（$3 \leq n \leq 500\,000$，$n-1 \leq m \leq 500\,000$，$m \leq \frac{n(n-1)}{2}$），表示十字路口和街道的数量。 接下来的 $m$ 行，每行两个整数 $s_i$ 和 $f_i$（$1 \leq s_i, f_i \leq n$，$s_i \neq f_i$），表示第 $i$ 条街道连接的两个十字路口。保证没有两条街道连接同一对十字路口，且图是连通的。 接下来一行一个整数 $k$（$1 \leq k \leq 500\,000$），表示市民的数量。 接下来的 $k$ 行，每行两个整数 $a_i$ 和 $b_i$（$1 \leq a_i, b_i \leq n$，$a_i \neq b_i$），表示第 $i$ 位市民需要从 $a_i$ 走到 $b_i$。 设 $M$ 为所有测试组中 $m$ 的总和，$K$ 为所有测试组中 $k$ 的总和。保证 $M, K \leq 500\,000$。

对于每组测试，输出如下内容： 第一行输出所有市民需要支付的总图格里克数（即总费用最大值）。 第二行输出第一条被选为大道的街道所连接的两个十字路口编号。 第三行输出第二条被选为大道的街道所连接的两个十字路口编号。 大道的两个端点顺序任意，输出的两条街道需是图中实际存在的不同街道。