| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 1024 MB | 3 | 1 | 1 | 33.333% |
Ахтунг! Механическую няню кто-то включил, и теперь она бегает за Пином, пытаясь окружить его лаской и заботой! Во дворе Пина есть $n$ бункеров, и он рад бы спрятаться в одном из них, но в каждом бункере у него есть очень важное и очень срочное дело.
Поэтому Пин просит вас составить маршрут его передвижения между бункерами, чтобы он смог посетить каждый ровно один раз, и вернуться в начало. При этом начать Пин может с любого бункера.
Кроме того, так как Пин сам писал программу перехвата для няни и собирал ее двигатель, то он точно знает, что будет пойман, если будет бежать от одного бункера к другому не по прямой, либо если он дважды пробежит через одно и то же место, то есть пересечёт или коснётся отрезка пути, который он уже пробежал.
Во входном файле дано описание двора Пина.
В первой строке входного файла находится одно целое число $n$ (1ドル \le n \le 100{,円}000$) --- количество бункеров во дворе Пина.
В следующих $n$ строках записано по два целых числа $x_i$ и $y_i$ ($|x_i|, |y_i| \le 10^9$) --- координаты входа в $i$-ый бункер. Вход в бункер настолько мал по сравнению с размерами двора, что считается точкой. Никакие два бункера не лежат в одной точке.
В выходной файл выведите перестановку из $n$ чисел --- номера бункеров в порядке их посещения Пином, либо 'No solution', если не существует маршрута, по которому Пин может пробежать и не быть пойманным няней.
4 0 0 0 1 1 0 1 1
1 2 4 3
3 0 0 0 1 0 2
No solution