← 返回题目列表

Codeforces · 819/E

E. B 先生和飞往月球

中文机器翻译题面 查看原题

为了飞向月球,B先生只需要解决以下问题。

存在一个具有 n 个顶点的完全间接图。您需要用几个长度为 3 和 4 的简单循环覆盖它,以便每条边恰好位于 2 个循环中。

我们确信B先生很快就会解决问题并飞向月球。你会?

输入

唯一一行包含单个整数 n (3 ≤ n ≤ 300)。

输出

如果没有答案,则打印-1。

否则,在第一行打印 k (1 ≤ k ≤ n2) — 解决方案中的循环数。

在接下来的 k 行中,按照以下格式打印一个循环的描述:首先打印整数 m (3 ≤ m ≤ 4) — 循环的长度,然后打印 m 个整数 v1, v2, ..., vm (1 ≤ vi ≤ n) — 按遍历顺序循环中的顶点。每条边应该正好处于两个周期内。

示例

输入 #1

3

输出 #1

2
3 1 2 3
3 1 2 3

输入 #2

5

输出 #2

6
3 5 4 2
3 3 1 5
4 4 5 2 3
4 4 3 2 1
3 4 2 1
3 3 1 5