新年的拯救计划
DoubleDog现在锁定了 $n$ 只SingleDog，决心去拯救它们。
为了能够快速到达这$n$只SingleDog的处所，DoubleDog们希望跳蚤国帮助修建一些道路，把$n$只SingleDog的处所联通。一条道路可以直接连接任意两只SingleDog的处所，所以只需要$n-1$条道路就可以让它们联通。
但是糟糕的天气可能会破坏一些道路。为了能够使得DoubleDog的计划尽可能地成功，跳蚤国王决定同时修建$m$个方案。每个方案都包含$n-1$条道路，任意一个方案都可以连通$n$只SingleDog的处所。
由于技术上的限制，跳蚤们给出了一个限制：这$m$个方案中任意两个方案不能存在两条相同的道路。
现在跳蚤国王想知道：最多能够选择多少个方案呢？
跳蚤国王把这个问题交给了你，请你求出这个最大的$m$，并告诉跳蚤国王这$m$个方案。
输入格式
一行一个正整数 $ n $ 表示SingleDog的数量，标号从$1$开始。
输出格式
输出的第一行是一个正整数 $ m $ ，表示最多能选出多少个方案。
接下来 $ m $ 行，每行 $ 2(n - 1) $ 个数，其中第 $ 2i - 1 $ 和第 $ 2i $ 个数表示该方案的一条道路。
你需要保证，这$m$行中任意一行的 $ (n-1) $条道路可以连通这$n$只SingleDog的处所，并且这$m(n-1)$条道路互不相同。（道路$(u,v)$和道路$(v,u$)被视为相同的道路）
如果本题有多组解，输出任意一组均可。
3
1
1 2 3 2
4
2
1 2 2 3 3 4
1 3 1 4 2 4
限制与约定
本题采用捆绑测试，对于每个子任务，只有通过其中全部数据才可以获得分数。
对于 $ 100\% $ 的数据，$ 3 \le n \le 2000 $ 。
| 子任务编号 | $n\le$ | 约定 | 分值 |
|---|---|---|---|
| $1$ | $6$ | $17$ | |
| $2$ | $100$ | $10$ | |
| $3$ | $2000$ | $n$是素数 | $44$ |
| $4$ | $2000$ | $29$ |
时间限制：$\texttt{1s}$
空间限制：$\texttt{512MB}$