하이퍼루프

2013년 8월, 캡슐이 관 속을 시속 1000킬로미터로 달리는 새 교통수단 하이퍼루프의 설계안이 공개되었다. 아직 아무도 모르는 사실이 하나 있다. 이 교통수단은 큰 도시가 아니라 작은 지방 도시 두 곳 사이에 가장 먼저 놓인다. 그 뒤를 따라 전국의 도시 $N$개는 서로 다른 두 도시마다 양방향 하이퍼루프 관 하나로 직접 이어진다.

관이 모두 개통되면 관광객을 위한 순회 노선을 여러 개 짜야 한다. 노선 하나는 도시 $N$개를 모두 한 번씩만 들른 뒤 출발한 도시로 돌아오므로 관을 정확히 $N$개 쓴다. 혼잡을 막기 위해 서로 다른 두 노선은 같은 관을 나눠 쓸 수 없다. 관을 지나는 방향이 반대여도 마찬가지다.

$N$이 홀수라서, 관이 하나도 남지 않도록 노선 $(N-1)/2$개를 짤 수 있다. 그 노선을 만들어라.

첫째 줄에 도시의 수 $N$이 주어진다. $N$은 홀수이고 $3 \le N < 2000$이다. 도시에는 1번부터 $N$번까지 번호가 붙어 있다.

노선 $(N-1)/2$개를 한 줄에 하나씩 출력한다. 각 줄에는 그 노선이 들르는 도시 번호 $N$개를 출발 도시부터 차례대로 공백으로 구분해 적는다. 마지막 도시에서 출발 도시로 돌아오는 관은 따로 적지 않는다.

조건을 만족하는 노선 묶음은 여러 가지이므로, 다음 규칙으로 만든 것만 정답으로 인정한다.

$M = (N-1)/2$이라고 하자. 1번 도시를 가운데 두고 나머지 도시 $N-1$개를 원에 배치한다. 자리는 $0$번부터 $N-2$번까지이고, $p$번 자리에는 도시 $p+2$가 있다.

$k = 0, 1, \dots, M-1$에 대해 $k$번 노선은 1번 도시에서 출발해 자리 $c_0, c_1, \dots, c_{N-2}$의 도시를 이 순서대로 들른 뒤 1번 도시로 돌아온다. 여기서

$c_i = \begin{cases} k - i/2 & (i \text{ 가 짝수}) \\ k + (i+1)/2 & (i \text{ 가 홀수}) \end{cases}$

이고, 자리 번호는 모두 $N-1$로 나눈 나머지로 계산한다. 즉 자리는 $k$에서 시작해 앞뒤로 한 칸씩 폭을 넓혀 가며 $k,\; k+1,\; k-1,\; k+2,\; k-2,\; \dots,\; k+(M-1),\; k-(M-1),\; k+M$ 순서로 $N-1$개를 모두 훑는다. 노선은 $k$가 작은 것부터 차례대로 출력한다.