Для того чтобы сделать столицу Берляндии более привлекательным туристическим местом, великий король придумал следующий план: выбрать две улицы города и назвать их проспектами. Естественно, эти проспекты будут объявлены чрезвычайно важными историческими местами, что должно привлечь туристов со всего мира.
Столицу Берляндии можно представить в виде графа, вершинами которого являются перекрестки, а ребрами являются улицы, соединяющие два перекрестка напрямую. Всего в графе \(n\) вершин и \(m\) ребер, по любой улице можно двигаться в обоих направлениях, от любого перекрестка можно добраться до любого другого, перемещаясь только по улицам, каждая улица соединяет два различных перекрестка, и никакие две улицы не соединяют одинаковую пару перекрестков.
Чтобы снизить поток обычных горожан, перемещающихся по великим проспектам, было решено ввести платный проезд по каждому их них в обе стороны. Теперь за один проезд по проспекту нужно заплатить \(1\) тугрик. За проезд по остальным улицам платить не нужно.
Аналитики собрали выборку из \(k\) горожан, \(i\)-му из них надо ездить на работу от перекрестка \(a_i\) к перекрестку \(b_i\). После выбора двух проспектов каждый горожанин будет добираться на работу вдоль пути, стоимость которого будет минимальна.
Для того чтобы заработать как можно больше денег, было решено выбрать в качестве двух проспектов две такие улицы, что суммарное количество тугриков, которые заплатят эти \(k\) горожан, будет максимально возможным. Помогите королю: по заданной схеме города и выборке горожан найдите, какие две улицы нужно сделать проспектами, и сколько тугриков заплатят горожане при таком выборе.
Выходные данные
Для каждого набора входных данных в выведите ответ на задачу.
В первой строке ответа данных выведите суммарное количество тугриков, которое заплатят горожане.
Во второй строке ответа выведите два целых числа \(x_1\) и \(y_1\) — номера перекрёстков, дорогу между которыми нужно сделать первым проспектом.
В третей строке ответа выведите два целых числа \(x_2\) и \(y_2\) — номера перекрёстков, дорогу между которыми нужно сделать вторым проспектом.
Номера перекрестков, соединенных улицей, можно выводить в произвольном порядке, каждая из двух выведенных улиц должна встречаться среди \(m\) улиц города, выбранные улицы должны быть различными.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
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
|