Задача №114662. Два проспекта
Для того чтобы сделать столицу Берляндии более привлекательным туристическим местом, великий король придумал следующий план: выбрать две улицы города и назвать их проспектами. Естественно, эти проспекты будут объявлены чрезвычайно важными историческими местами, что должно привлечь туристов со всего мира.
Столицу Берляндии можно представить в виде графа, вершинами которого являются перекрестки, а ребрами являются улицы, соединяющие два перекрестка напрямую. Всего в графе \(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 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\) улиц города, выбранные улицы должны быть различными.
Тесты к этой задаче состоят из 7 групп. Баллы за каждую группу ставятся только при прохождении всех тестов группы и всех тестов необходимых групп. Обратите внимание, что прохождение тестов из условия не требуется для некоторых групп. Offline-проверка означает, что результаты тестирования вашего решения на данной группе станут доступны только после окончания соревнования.
| Дополнительные ограничения | ||||||
| Группа | Баллы | \(n\) | \(m\) | \(k\) | Необх. группы | Комментарий |
| 0 | 0 | – | – | – | – | Тесты из условия |
| 1 | 14 | \(n \leq 20\) | \(m \leq 20\) | \(K \leq 1000\) | \(0\) | \(t \leq 100\) |
| 2 | 11 | \(n \leq 100\) | \(M \leq 2000\) | \(K \leq 2000\) | \(0\) – \(1\) | |
| 3 | 15 | \(n \leq 2000\) | \(M \leq 20\,000\) | \(K\leq 20\,000\) | \(0\) – \(2\) | |
| 4 | 16 | – | \(M \leq 100\,000\) | \(K \leq 100\,000\) | \(0\) – \(3\) | |
| 5 | 11 | – | – | – | – | \(n = m + 1\) |
| 6 | 19 | – | – | – | – | Из каждого перекрестка выходит ровно \(2\) улицы |
| 7 | 14 | – | – | – | \(0\) – \(6\) | Offline-проверка |
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