한 줄 표기법

$N$개의 수가 모두 서로 다르다는 조건은 기호 !=를 여러 번 쓴 하나의 식으로 나타낼 수 있다. 예를 들어 A, B, C가 모두 서로 다르다는 조건은 (A != B) && (B != C) && (C != A)이고, 이를 한 줄로 이어 쓴

A != B != C != A

를 A, B, C의 한 줄 표기법이라고 하자.

하지만 다섯 수 A, B, C, D, E가 모두 서로 다르다는 조건을

A != B != C != D != E

로 쓰는 것은 올바른 한 줄 표기법이 아니다. 다섯 수가 모두 다름을 나타내려면 쌍 10개가 각각 다름을 말해야 하고, 그러려면 !=가 적어도 10개 필요하기 때문이다. 일반적으로 $N$개의 수가 모두 다름을 한 줄 표기법으로 나타내려면 !=가 적어도 $C(N, 2)$개 필요하다. 여기서 $C(N, 2)$는 서로 다른 $N$개 중에서 2개를 뽑는 경우의 수이다.

정확히 말하면 a1, a2, ..., aN의 한 줄 표기법은 이 이름을 늘어놓은 수열 $x_1$, $x_2$, ..., $x_k$이고, 이웃한 두 항 사이마다 !=를 써서 한 줄로 적은 것이다. 서로 다른 두 이름 $u$, $v$의 모든 쌍에 대해 $x_t = u$이고 $x_{t+1} = v$이거나 $x_t = v$이고 $x_{t+1} = u$인 위치 $t$가 있어야 한다. 표기법의 길이는 !=의 개수, 즉 $k - 1$이다.

홀수 $N$이 주어진다. a1, a2, ..., aN의 한 줄 표기법 중 가장 짧고, 그중 사전순으로 가장 앞서는 것을 출력하라. 이때 !=는 공백 하나로 대신한다. 예를 들어 $N = 3$이면 a1 a2 a3 a1이 정답이다. a3 a1 a2 a3도 길이가 같은 한 줄 표기법이지만 사전순으로 뒤에 오므로 정답이 아니다.

힌트: 한 줄 표기법에 필요한 !=의 최소 개수 $C(N, 2)$는 꼭짓점이 $N$개인 완전 그래프의 간선 수와 같다.

첫째 줄에 홀수 $N$이 주어진다. $1 < N < 500$이다.

첫째 줄에 가장 짧은 한 줄 표기법 중 사전순으로 가장 앞서는 것을 출력한다. 이름은 a1, a2처럼 쓰고 공백 하나로 구분한다. 사전순은 첨자의 수열을 앞에서부터 비교해서 정하고, 첨자는 수로 비교한다. 즉 a2가 a10보다 앞선다.