eolymp
bolt
Try our new interface for solving problems
Məsələlər

Ахтунг!

Ахтунг!

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 256 MiB

Ахтунг! Механическую няню кто-то включил, и теперь она бегает за Пином, пытаясь окружить его лаской и заботой! Во дворе Пина есть n бункеров, и он рад бы спрятаться в одном из них, но в каждом бункере у него есть очень важное и очень срочное дело.

Поэтому Пин просит вас составить маршрут его передвижения между бункерами, чтобы он смог посетить каждый ровно один раз, и вернуться в начало. При этом начать Пин может с любого бункера.

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

Giriş verilənləri

Во входном файле дано описание двора Пина.

В первой строке входного файла находится одно целое число n (1n100000) - количество бункеров во дворе Пина.

В следующих n строках записано по два целых числа x_i и y_i (|x_i|, |y_i| ≤ 10^9) - координаты входа в i-ый бункер. Вход в бункер настолько мал по сравнению с размерами двора, что считается точкой. Никакие два бункера не лежат в одной точке.

Çıxış verilənləri

В выходной файл выведите перестановку из n чисел - номера бункеров в порядке их посещения Пином, либо 'No solution', если не существует маршрута, по которому Пин может пробежать и не быть пойманным няней.

Nümunə

Giriş verilənləri #1
4
0 0
0 1
1 0
1 1
Çıxış verilənləri #1
1
3
4
2
Müəllif А.Комаров, А.Цыпленков