2 sec, 256 M
You are given a regular N-gon. You must visit all it’s vertices only once and return into the start vertex. You may move on N-gon diagonals and edges only. No any segments of your path could be parallel. The length of the path must be as long as possible.
Input. The only input line contains a natural number N (3 ≤ N ≤ 42).
Output. If you can’t solve the task, output “Sorry, I am from ITMO” without quotas. Otherwise output N vertices in the visiting order splitting them with spaces. If there are some right paths, output your favorite one.
|3||2 1 3|
|4||Sorry, I am from ITMO|
Idea – Roman Igorevich Cheplyaka
and Oleg Alexandrovich Petrov
KBIS Software Developer