CF1648F.Two Avenues

In order to make the capital of Berland a more attractive place for tourists, the great king came up with the following plan: choose two streets of the city and call them avenues. Certainly, these avenues will be proclaimed extremely important historical places, which should attract tourists from all over the world.

The capital of Berland can be represented as a graph, the vertices of which are crossroads, and the edges are streets connecting two crossroads. In total, there are $n$ vertices and $m$ edges in the graph, you can move in both directions along any street, you can get from any crossroad to any other by moving only along the streets, each street connects two different crossroads, and no two streets connect the same pair of crossroads.

In order to reduce the flow of ordinary citizens moving along the great avenues, it was decided to introduce a toll on each avenue in both directions. Now you need to pay $1$ tugrik for one passage along the avenue. You don't have to pay for the rest of the streets.

Analysts have collected a sample of $k$ citizens, $i$-th of them needs to go to work from the crossroad $a_i$ to the crossroad $b_i$. After two avenues are chosen, each citizen will go to work along the path with minimal cost.

In order to earn as much money as possible, it was decided to choose two streets as two avenues, so that the total number of tugriks paid by these $k$ citizens is maximized. Help the king: according to the given scheme of the city and a sample of citizens, find out which two streets should be made avenues, and how many tugriks the citizens will pay according to this choice.

为了使贝尔兰首都对游客更具吸引力，伟大的国王提出了如下计划：从城市中选择两条街道并将其命名为“大道”。当然，这些大道将被宣布为极其重要的历史场所，以吸引来自世界各地的游客。

贝尔兰首都可用一个图来表示，其中顶点代表十字路口，边代表连接两个十字路口的街道。该图共有 $n$ 个顶点和 $m$ 条边；任意街道均可双向通行；仅通过街道即可从任一十字路口到达另一任意十字路口；每条街道连接两个不同的十字路口；且不存在两条街道连接同一对十字路口。

为减少普通市民在大道上的通行流量，决定在每条大道的两个方向上均设置通行费。现在沿任一大道通行一次需支付 $1$ 图格里克（tugrik）；其余街道则无需付费。

分析人员收集了 $k$ 名市民的样本，其中第 $i$ 名市民需从十字路口 $a_i$ 前往十字路口 $b_i$ 上班。在选定两条大道后，每名市民均会选择总费用最小的路径前往工作地点。

为使收入最大化，决定将两条街道选为大道，使得这 $k$ 名市民所支付的图格里克总额最大。请帮助国王：根据给定的城市结构图及市民样本，确定应选哪两条街道作为大道，并计算在此选择下市民总共需支付多少图格里克。

Each test consists of multiple test cases. The first line contains one integer $t$ ($1 \leq t \leq 10^5$) — the number of test cases.

The first line of each test case contains two integers $n$ and $m$ ($3 \leq n \leq 500\,000$, $n - 1 \leq m \leq 500\,000$, $m \le \frac{n (n - 1)}{2}$) — the number of crossroads and streets, respectively.

The next $m$ lines contain the description of streets, $i$-th line contains two integers $s_i$ and $f_i$ ($1 \leq s_i, f_i \leq n$, $s_i \neq f_i$) — indexes of crossroads which are connected by $i$-th street. It is guaranteed that no two streets connect the same pair of crossroads, you can get from any crossroad to any other by moving only along the streets.

The next line contains a single integer $k$ ($1 \leq k \leq 500\,000$) — the amount of citizens in the sample.

The next $k$ lines contain the description of citizens, $i$-th line contains two integers $a_i$ and $b_i$ ($1 \leq a_i, b_i \leq n$, $a_i \neq b_i$) — $i$-th citizen goes to work from crossroad $a_i$ to crossroad $b_i$.

Let $M$ be the sum of $m$ over all test cases and $K$ be the sum of $k$ over all test cases. It is guaranteed that $M, K \le 500\,000$.

每个测试包含多个测试用例。第一行包含一个整数 $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$。

For each test case print the answer to the problem.

In the first line print the total amount of tugriks that will be paid by citizens.

In the second line print two integers $x_1$ and $y_1$ — the numbers of crossroads that will be connected by the first avenue.

In the third line print two integers $x_2$ and $y_2$ — the numbers of crossroads that will be connected by the second avenue.

The numbers of crossroads connected by an avenue can be printed in any order, each of the printed streets should be among $m$ streets of the city, chosen streets should be different.

对于每个测试用例，请输出该问题的答案。

第一行输出市民将支付的图格里克总额。

第二行输出两个整数 $x_1$ 和 $y_1$ —— 表示第一条大道所连接的两个路口编号。

第三行输出两个整数 $x_2$ 和 $y_2$ —— 表示第二条大道所连接的两个路口编号。

每条大道所连接的路口编号顺序可任意；所输出的每条街道必须属于城市原有的 $m$ 条街道之一，且所选的两条街道必须互不相同。