Description

为了让伯兰德的首都更具吸引力，伟大的国王提出了如下方案：选择城市中的两条街道，将它们命名为大道。这两条大道将被宣布为极其重要的历史地标，旨在吸引来自世界各地的游客。

首都可以用一个图来表示，顶点代表十字路口，边代表直接连接两个十字路口的街道。图中共有 $n$ 个顶点和 $m$ 条边，任意一条街道都可以双向通行。任意两个十字路口之间都可以仅通过街道到达，且每条街道连接的是两个不同的十字路口，没有两条街道连接同一对十字路口。

为了减少普通市民在大道上的通行量，决定对每条大道的双向通行都收取过路费。每经过大道一次需支付 $1$ 图格里克，其他街道免费。

分析师收集了 $k$ 位市民的样本，第 $i$ 位市民需要从十字路口 $a_i$ 前往十字路口 $b_i$。选定两条大道后，每位市民都会选择总费用最少的路径上下班。

为了让收入最大化，需要选择两条街道作为大道，使得所有 $k$ 位市民支付的总图格里克数最大。请你帮国王计算：根据给定的城市结构和市民样本，应该选择哪两条街道作为大道，以及在此选择下市民们总共会支付多少图格里克。

Input Format

每个测试包含多组数据。第一行包含两个整数，$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$。

Output Format

对于每组测试，输出如下内容：

第一行输出所有市民需要支付的总图格里克数（即总费用最大值）。

第二行输出第一条被选为大道的街道所连接的两个十字路口编号。

第三行输出第二条被选为大道的街道所连接的两个十字路口编号。

大道的两个端点顺序任意，输出的两条街道需是图中实际存在的不同街道。

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

Hint

本题测试数据分为 7 组。只有通过某一组的全部测试点，且通过所有必需的前置组，才能获得该组分数。有些分组不要求通过样例测试点。离线评测表示该组的评测结果将在比赛结束后公布。