시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 1024 MB106595366.250%

문제

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$

서브태스크

번호배점제한
120

$N \le 8$

280

No additional constraints.

예제 입력 1

3

예제 출력 1

2
1 2
2 3
1 3
1 2

예제 입력 2

4

예제 출력 2

2
1 2
2 3
3 4
2 4
1 3
1 4

출처

University > KAIST > 2023 KAIST RUN Spring Contest B번

채점 및 기타 정보

  • 예제는 채점하지 않는다.