A11004. Mister B and Flight to the Moon
编程题
普及/提高-
知识点
题目描述
In order to fly to the Moon Mister B just needs to solve the following problem.
There is a complete indirected graph with $n$ vertices. You need to cover it with several simple cycles of length $3$ and $4$ so that each edge is in exactly $2$ cycles.
We are sure that Mister B will solve the problem soon and will fly to the Moon. Will you?
There is a complete indirected graph with $n$ vertices. You need to cover it with several simple cycles of length $3$ and $4$ so that each edge is in exactly $2$ cycles.
We are sure that Mister B will solve the problem soon and will fly to the Moon. Will you?
输入格式
The only line contains single integer $n$ ( $3<=n<=300$ ).
输出格式
If there is no answer, print -1.
Otherwise, in the first line print $k$ ( $1<=k<=n^{2}$ ) — the number of cycles in your solution.
In each of the next $k$ lines print description of one cycle in the following format: first print integer $m$ ( $3<=m<=4$ ) — the length of the cycle, then print $m$ integers $v_{1},v_{2},...,v_{m}$ ( $1<=v_{i}<=n$ ) — the vertices in the cycle in the traverse order. Each edge should be in exactly two cycles.
Otherwise, in the first line print $k$ ( $1<=k<=n^{2}$ ) — the number of cycles in your solution.
In each of the next $k$ lines print description of one cycle in the following format: first print integer $m$ ( $3<=m<=4$ ) — the length of the cycle, then print $m$ integers $v_{1},v_{2},...,v_{m}$ ( $1<=v_{i}<=n$ ) — the vertices in the cycle in the traverse order. Each edge should be in exactly two cycles.
输入输出样例
输入 #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