该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

宁宁现在在建设大楼！

在宁宁的规划中，大楼有 $n$ 层，从下到上依次为第 $1,2, \cdots , n$ 层，她还要建设 $m$ 个电梯，每个电梯一定会停在第 $1$ 层和第 $n$ 层，她可以选择让这些电梯停在中间某些层（也可以不停）。她希望建设的这 $m$ 个电梯满足：对于任意不同的两层 $x, y$，存在一个电梯使 $x, y$ 可以直达（中间不经过任何可以停的层）。为了降低建造成本，她希望电梯数 $m$ 尽量小。

宁宁她不太聪明，于是她转过来求助你，希望你能告诉她 $m$ 的最小值并给出构造。

你不需要最小化停的总层数。但还是为了节约资源，你需要使得停的总层数不超过 $2 \times 10^{6}$ 。

输入格式

一行一个正整数 $n$ $(2\leq n\leq 1000)$ 。

输出格式

第一行一个正整数 $m$ ，表示最少需要的电梯数。

接下来 $m$ 行，每行表示一个电梯的停层状况。具体来说，对于第 $i$ 行，你需要输出一个序列 $a_{i,1}, a_{i,2}, \cdots, a_{i,k_{i}}$ ，使得 $1 = a_{i,1} < a_{i,2} < \cdots < a_{i,k_{i}} = n$ ，且 $\sum_{i=1}^{n} k_{i} \leq 2 \times 10^{6}$ 。表示第 i 个电梯会停在 $a_{i,1}, a_{i,2}, \cdots, a_{i,k_{i}}$ 层。

输出量较大，建议采用较快的输出方式。

4

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

解释 #1

可以证明 $m$ 的最小值为 $4$。

第 1,2 层可以通过电梯 3,4 直达，第 1,3 层可以通过电梯 1 直达，第 1,4 层可以通过电梯 2 直达，第 2,3 层可以通过电梯 3 直达，第 2,4 层可以通过电梯 4 直达，第 3,4 层可以通过电梯 1,3 直达。