eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Ладья

Ладья

Лимит времени 1 секунда
Лимит использования памяти 64 MiB

Ладья викингов плывет по бескрайнему океану в поисках Вальгаллы. Руль давно потерян, половина вёсел - и подавно, так что все повороты она может совершить лишь с помощью водоворотов, коих на карте n штук. Но и это не так просто, поэтому и до, и после поворота ладья может направляться только на север, юг, запад либо восток. У первого водоворота начинает она свой путь, и у последнего закончится её путь. Но вот сколько сил останется для последней битвы? Сыграйте против коварного Локи, проложите лучший путь для ладьи. Боги сочтут путь лучшим, если он потребует сил на минимальное количество поворотов, а среди таких ещё и окажется самым коротким. Помните, что в начале пути ладья смотрит на север.

Входные данные

Первая строка входного файла содержит единственное целое число n. Следующие n строк содержат по два целых числа каждая - координаты соответствующего водоворота. Все водовороты находятся в различных точках. 2n100000, все координаты по модулю не превышают 10^9. Север расположен в направлении увеличения координаты y.

Выходные данные

Выведите в выходной файл две строки. Первая из них должна содержать два целых числа: искомое минимальное количество поворотов и искомое минимальное расстояние. Вторая же должна содержать описание оптимального пути: номера водоворотов в порядке их прохождения без повторений, начиная с первого и заканчивая последним.

Если ладье суждено блуждать по морю, не находя пути, выведите в единственной строке два числа -1.

Пример

Входные данные #1
3
1 1
1 2
2 2
Выходные данные #1
1 2
1 2 3
Автор Юрий Петров
Источник Тринадцатая международная командная олимпиада школьников ЛКШ среди параллелей A, A' и B