EduBrick

M. Обход бункеров

2000 мс · 256 МБ · всё или ничего

Во дворе nn бункеров, заданных точками. Нужно обойти все бункеры по одному разу и вернуться в начальный, двигаясь между ними по прямым. Маршрут не должен дважды проходить через одну точку: звенья не пересекаются и не касаются друг друга — кроме общих концов у соседних звеньев.

Начинать можно с любого бункера. Если маршрута не существует, так и сообщите.

Формат ввода

В первой строке — число nn (1≤n≤20001 \le n \le 2000). В следующих nn строках — целые координаты бункеров (∣x∣,∣y∣≤109|x|, |y| \le 10^9). Никакие два бункера не совпадают.

Формат вывода

Выведите nn номеров бункеров в порядке обхода или строку No solution, если маршрута нет.

Примеры

ввод
4
0 0
0 1
1 0
1 1
вывод
1 3 4 2
ввод
3
0 0
0 1
0 2
вывод
No solution
Разбор идеи от автора задачи. Сначала попробуйте сами.
Войдите, чтобы отправлять решения.