← 返回题目列表

Codeforces · 1648/F

F. 两条大道

中文机器翻译题面 查看原题

为了让贝尔兰的首都成为对游客更有吸引力的地方,伟大的国王想出了以下计划:选择城市的两条街道,并将它们称为大道。当然,这些大道将被宣布为极其重要的历史名胜,应该吸引来自世界各地的游客。

Berland的首都可以表示为一个图,其顶点是十字路口,边是连接两个十字路口的街道。总共,图中有 $$$n$$$ 个顶点和 $$$m$$$ 个边,您可以沿着任何街道在两个方向上移动,您可以通过仅沿着街道移动从任何十字路口到达任何其他十字路口,每条街道连接两个不同的十字路口,并且没有两条街道连接同一对十字路口。

为了减少普通市民沿主要大道通行的流量,决定在每条大道上实行双向收费。现在您需要为沿大道的一段路程支付 $$$1$$$ tugrik。您无需为其余街道付费。

分析师收集了 $$$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 \le \frac{n (n - 1)}{2}$$$) — 的数量分别是十字路口和街道。

接下来的 $$$m$$$ 行包含街道的描述,第 $$$i$$$ 行包含两个整数 $$$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$$$ 行包含公民的描述,第 $$$i$$$ 行包含两个整数 $$$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 \le 500\,000$$$。

输出

对于每个测试用例,打印问题的答案。

第一行打印公民将支付的图格里克总额。

在第二行中打印两个整数 $$$x_1$$$ 和 $$$y_1$$$ - 将由第一条大道连接的十字路口的数量。

在第三行中打印两个整数 $$$x_2$$$ 和 $$$y_2$$$ - 将由第二条大道连接的十字路口的数量。

一条大道所连接的十字路口的编号可以按任意顺序打印,每条打印的街道应在该城市的 $$$m$$$ 街道中,选择的街道应不同。

示例

输入 #1

3
6 5
1 2
2 3
2 4
4 5
4 6
3
1 6
5 3
2 5
5 5
1 2
2 3
3 4
4 5
5 1
6
1 5
1 3
1 3
2 4
2 5
5 3
8 10
1 2
2 3
3 4
4 5
5 6
6 7
7 8
7 1
1 8
3 6
4
2 5
3 7
2 5
7 8

输出 #1

5
4 2
5 4
5
1 5
3 2
3
7 6
2 3