题目描述

给定 $n$，构造一张 $n$ 个点的简单有向无环图，使得距离为 $2$ 的点对的个数不少于 $\dfrac{n(n-1)}2-n\left\lceil\log_2n\right\rceil$。

点对 $(u,v)$ 之间的距离指 $u$ 到 $v$ 的最短路长度。若 $u$ 无法到达 $v$，则距离为 $100^{100}$。

输入格式

一行一个正整数 $n$。

输出格式

第一行一个整数 $m(0\le m\le \frac{n(n-1)}{2})$，表示你构造的图的边数。

之后 $m$ 行，每行两个数 $u,v$，表示你的构造的图中的一条边。你需要保证你构造的图是一张简单有向无环图，即没有重边也没有环。

3

2
1 2
2 3

提示

样例解释

样例中唯一距离为 $2$ 的点对是 $(1,3)$，容易证明不存在满足条件的点对个数比 $1$ 大的方案。

数据范围

$1\le n\le 2000$。

评分方式

若你的程序给出的图不为简单有向无环图，你该测试点的得分将为 $0$。

否则设你的程序给出的图中距离为 $2$ 的点对数为 $x$。若 $x\ge\dfrac{n(n-1)}2-n\left\lceil\log_2n\right\rceil$，你将获得该测试点的满分；若 $\left\lfloor\dfrac{n-1}{2}\right\rfloor\times \left\lceil\dfrac{n-1}{2}\right\rceil\le x < \dfrac{n(n-1)}2-n\left\lceil\log_2n\right\rceil$，你将获得该测试点 $20\%$ 的分数。