ぶどうの粒は \(\displaystyle M = \frac{N(N-1)}{2}\) 個あります。また、明らかに \(\displaystyle Q \le \lfloor \frac{M}{2} \rfloor\) です。

もし、 \(\displaystyle Q = \lfloor \frac{M}{2} \rfloor\) が達成可能かつ構成できれば問題は解決します。そして、実際にこれは達成可能です。いくつかの構成方法がありますが、以下のような手法が明快でしょう。

上図のように各ぶどうの粒を \(1\) 回ずつ通るパスを作ります。 そして、通った順に \(1, 2\) 粒目、\(3, 4\) 粒目 … というように食べれば良いです。最終的に何も余らないか、\(1\) 粒余るため、これは \(\displaystyle Q = \lfloor \frac{M}{2} \rfloor\) を達成しています。

実装例

n = int(input())

g = []
for i in range(1, n + 1):
    l = n - i + 1
    c = list(range(1, l + 1))
    if i % 2 == 1: c = c[::-1]
    g.extend((i, j) for j in c)

print(len(g) // 2)
for i in range(0, len(g) - 1, 2):
    print(*g[i], *g[i+1])