F. Два проспекта
ограничение по времени на тест
8 секунд
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Для того чтобы сделать столицу Берляндии более привлекательным туристическим местом, великий король придумал следующий план: выбрать две улицы города и назвать их проспектами. Естественно, эти проспекты будут объявлены чрезвычайно важными историческими местами, что должно привлечь туристов со всего мира.

Столицу Берляндии можно представить в виде графа, вершинами которого являются перекрестки, а ребрами являются улицы, соединяющие два перекрестка напрямую. Всего в графе $$$n$$$ вершин и $$$m$$$ ребер, по любой улице можно двигаться в обоих направлениях, от любого перекрестка можно добраться до любого другого, перемещаясь только по улицам, каждая улица соединяет два различных перекрестка, и никакие две улицы не соединяют одинаковую пару перекрестков.

Чтобы снизить поток обычных горожан, перемещающихся по великим проспектам, было решено ввести платный проезд по каждому их них в обе стороны. Теперь за один проезд по проспекту нужно заплатить $$$1$$$ тугрик. За проезд по остальным улицам платить не нужно.

Аналитики собрали выборку из $$$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$$$ улиц города, выбранные улицы должны быть различными.

Пример
Входные данные
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
Выходные данные
5
4 2
5 4
5
1 5
3 2
3
7 6
2 3