P13542 [OOI 2022] Two avenues

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

每个测试包含多组数据。第一行包含两个整数，$t$（$1 \leq t \leq 10^5$）表示测试组数，$g$（$0 \leq g \leq 7$）表示本测试属于哪一组。接下来是每组测试的数据。 每组测试的第一行包含两个整数 $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$。

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

本题测试数据分为 7 组。只有通过某一组的全部测试点，且通过所有必需的前置组，才能获得该组分数。有些分组不要求通过样例测试点。**离线评测**表示该组的评测结果将在比赛结束后公布。 | 组别 | 分值 | $n$ | $m$ | $k$ | 必须通过的组 | 备注 | |:----:|:----:|:--:|:--:|:--:|:------------:|:----:| | 0 | 0 | -- | -- | -- | -- | -- | 样例测试点 | | 1 | 14 | $n \leq 20$ | $m \leq 20$ | $K \leq 1000$ | 0 | $t \leq 100$ | | 2 | 11 | $n \leq 100$ | $M \leq 2000$ | $K \leq 2000$ | 0--1 | | | 3 | 15 | $n \leq 2000$ | $M \leq 20\,000$ | $K \leq 20\,000$ | 0--2 | | | 4 | 16 | -- | $M \leq 100\,000$ | $K \leq 100\,000$ | 0--3 | | | 5 | 11 | -- | -- | -- | -- | $n = m + 1$ | | 6 | 19 | -- | -- | -- | -- | 每个十字路口正好连出两条街道 | | 7 | 14 | -- | -- | -- | 0--6 | **离线评测** |