题目描述

题目译自 Open Olympiad in Informatics 2022 Day1 T2 「Два проспекта / 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 500000, n-1 \leq m \leq 500000, m \leq \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 500000)$，表示样本中市民的数量。

接下来的 $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 \leq 500000$。

输出格式

对于每组输入数据，输出问题的答案。

答案的第一行输出市民支付的图格里克总数。

答案的第二行输出两个整数 $x_1$ 和 $y_1$，表示应作为第一条大街的街道所连接的两个路口的编号。

答案的第三行输出两个整数 $x_2$ 和 $y_2$，表示应作为第二条大街的街道所连接的两个路口的编号。

连接街道的路口编号可以按任意顺序输出，每条输出的街道必须是城市中 $m$ 条街道之一，且两条选择的街道必须不同。

3 0
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

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

数据范围与提示

详细子任务附加限制及分值如下表所示。其中子任务 $0$ 是样例。