Type: Default 4000ms 1024MiB

[2026 CCPC_NC_I D] 电梯

You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Description

宁宁现在在建设大楼!

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

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

你不需要最小化停的总层数。但是为了节约资源,你需要使得停的总层数不超过 2×1062\times 10^6。

Format

Input

一行一个正整数 nn (2≤n≤10002\le n\le 1000)。

Output

第一行一个正整数 mm,表示最少需要的电梯数。

接下来 mm 行,每行表示一个电梯的停层状况。具体来说,对于第 ii 行,你需要输出一个序列 ai,1,ai,2,⋯ ,ai,kia_{i,1},a_{i,2},\cdots,a_{i,k_i},使得 1=ai,1<ai,2<⋯<ai,ki=n1=a_{i,1}<a_{i,2}<\cdots<a_{i,k_i}=n,且 ∑i=1mki≤2×106\sum_{i=1}^{m} k_i \le 2\times 10^6。表示第 ii 个电梯会停在 ai,1,ai,2,⋯ ,ai,kia_{i,1},a_{i,2},\cdots,a_{i,k_i} 层。

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

Samples

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

Note

可以证明 mm 的最小值为 44。

第 1,21,2 层可以通过电梯 3,43,4 直达,第 1,31,3 层可以通过电梯 11 直达,第 1,41,4 层可以通过电梯 22 直达,第 2,32,3 层可以通过电梯 33 直达,第 2,42,4 层可以通过电梯 44 直达,第 3,43,4 层可以通过电梯 1,31,3 直达。