Description

You need to design bus routes for a city.

There are a total of $n$ routes and $m$ stations. Both are numbered starting from $1$.

Your main task is to decide which stations each route should pass through. In other words, for each route, you may choose any subset of stations, and the route will pass through all stations in this subset.

Two routes are defined to be related if and only if they pass through at least one common station, i.e., their sets of stations intersect.

A route plan must satisfy the following constraints:

1. A route cannot pass through only one station, so each route must pass through at least two stations.

2. A station has limited capacity, so each station can be used by at most three routes.

3. To keep traffic smooth, for any two different routes $i, j(i \not = j)$, there exists a third route $k (k \not = i, k \not = j)$ such that $k$ is related to both $i$ and $j$.

Given $n$, find the minimum $m$ and output a specific plan.

Input Format

One line containing a positive integer $n$, with the meaning as described in the statement.

Output Format

The first line outputs a positive integer $m$, which is the number of stations used in your plan.

In the next $n$ lines, on the $i$-th line output a positive integer $c$ and several positive integers $a _1, a _2, \cdots, a _c$, representing the number of stations passed by route $i$ in your plan and the indices of those stations.

4

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

Hint

"Sample 1 Explanation"

As shown in the figure.

First, it is easy to see that it satisfies Conditions 1 and 2 in the statement. Now consider Condition 3.

First consider routes $1, 2, 4$. You can see that these three routes form a triangle: for any two routes, the remaining one is related to both of them.

Then consider route $3$ together with routes $1, 2, 4$ respectively. It is easy to verify that for any $x \in \{1, 2, 4\}$, there exists another route $y \in \{1, 2, 4\}, y \not = x$ that is related to both $3$ and $x$, which satisfies the condition.

"Special Judge Notes and Scoring Rules"

Please read the output format carefully.

If your output has any of the following issues, you will receive $0$ points:

• The output format is incorrect, e.g., missing line breaks, printing strange characters, not printing the number of stations, etc.
• Some route passes through the same station more than once, or some station index is not within $[1, m]$.
• Any of the three constraints in the statement is not satisfied.
• The output file is too large, or $m$ is too large. If your $m$ is greater than $10 ^6$, you will directly receive $0$ points. If the output file is too large, it may cause TLE or OLE. It is recommended to keep the output size within 25 Mb.

If you are not judged as $0$ points, your score will be determined by the size of your $m$.

For each test point, there are $10$ judging parameters $w _1, w _2, \cdots, w _{10}$. If your output $m$ is less than or equal to $k$ of these parameters, then you will get $k \times 10\%$ of the score for that test point.

These $10$ parameters are not publicly visible, meaning your program cannot know them during execution.

"Constraints"

This problem uses bundled testdata. Your score for a subtask is the minimum score among all test points in that subtask.

• Subtask 1 (20 points): $n \le 10$. Here we guarantee that all $10$ scoring parameters are $10 ^6$.
• Subtask 2 (40 points): $n \le 200$.
• Subtask 3 (40 points): no special restrictions.

For all testdata, it holds that $3 \le n \le 4 \times 10 ^3$, and $ans + 5 \le w _1 \le w _2 \le \cdots \le w _{10} = 10 ^6$, where $ans$ denotes the standard answer.

Please note the condition $w _{10} = 10^6$.

Translated by ChatGPT 5