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