28054번 - Clique Partition 서브태스크스페셜 저지다국어

문제

We have a complete graph of size $N$. Find a way to represent the set of edges in this graph as the union of several $N$-vertex trees. Specifically, $K$ denoting the number of trees and $K$ trees $T_1, ..., T_K$ satisfying the following conditions should be output.

• Each tree has vertices numbered from 1ドル$ to $N$ and $N-1$ edges, and must not have cycles. (That is, it must satisfy the tree structure.)
• The union of all trees forms a complete graph.
• $K$ should be a minimum.

입력

Input has only one line containing $N$.

출력

Print out $K$ at the first line. $K$ must be the minimum. After that, print the edges of $T_1$ one by one over the following $(N-1)$ lines. Output all $K$ trees in the same way without any empty lines. Each tree must satisfy the condition of the problem.

제한

• 2ドル \le N \le 1000$

서브태스크

힌트