Background

The Beast Realm is an extreme world where the strong eat the weak, occupied by animal spirits, and also a world controlled by several organizations—the Strong Fang Group, the Ghostly Heroes Group, the Alliance of Animalistic Desire, and so on.

Among these animal spirits, there are also some spirits of primates, that is, human spirits. They are weak but nimble, and survive as complete slaves in an entertainment facility called the Primate Garden.

But human spirits also have faith. They prayed to the gods, and the gods responded, granting humans an idol of faith. However, at first the human spirits only worshiped the divinity behind the idol, but gradually they began to believe in the idol itself. As a result, naturally, the idol began to control humans, turning the Primate Garden into a vicious, out-of-control organization.

The Beast Realm also became chaotic because of the Primate Garden’s riot. In order to defeat the idol, the Ghostly Heroes Group hopes to involve the humans on the surface and use human hands to destroy the Primate Garden. So the animal spirits came to the surface, that is, Gensokyo, and led Reimu’s group to go to Hell together.

Problem Description

Brief statement

For a positive integer $n$ ($n$ is $529$ or $625$), let $A=\{1,2,\cdots,n\}$. A family of $m \ge 2$ subsets $B_1,B_2,\cdots,B_m(|B_i| \geq 3)$ of $A$ is called good if, for every 3-element subset $C$ of $A$, there exists exactly one $i$ such that $C$ is a subset of $B_i$. Construct a good family of subsets such that $m$ is as small as possible (and does not exceed the scoring parameter given in the statement).

Original statement

Reimu, who went deeper into the Beast Realm, encountered the leader of the Haniwa legion, Taketou Ankuma Yumi, who blocked her way.

The Haniwa legion consists of $n$ warriors, numbered $1,2,\dots,n$. The number of warriors is $529$ or $625$. As a legion, to achieve the best offense and defense, there are $m$ groups of cooperation relations among the Haniwa, $B_1,B_2,\dots,B_m$. Each group contains several distinct (but at least $3$) Haniwa warriors, but the same Haniwa warrior may appear in multiple different groups.

However, Reimu does not know these cooperation relations in advance, and because the Haniwa legion works together very well, it is hard for her to defeat them by force. With the help of the animal spirits, Reimu discovered that these Haniwa satisfy the following property: if you choose any $3$ Haniwa from the legion, there exists exactly one $i$ such that these three Haniwa are a subset of $B_i$. Based on this property, since Ankuma Yumi has limited energy and cannot maintain too many cooperation groups at the same time, $m$ is a positive integer with $m \ge 2$, and it is also required that $m \le m_{ans}$.

Now Reimu tells you the total number of warriors in the Haniwa legion. Please tell her one possible set of cooperation relations of the Haniwa legion to help her defeat Taketou Ankuma Yumi and enter the Primate Garden.

Input Format

The first line contains one positive integer $n$, with the meaning described above. It is guaranteed that $n=529$ or $625$.

Output Format

Output a positive integer $m$ in the first line, indicating the total number of sets used in your construction. It must satisfy $m\ge 2$.

Then output $m$ lines. Each line contains several integers. The first integer $s$ indicates the size of your constructed $B_i$, which must satisfy $n\ge s>0$. The next $s$ integers describe the elements in $B_i$, separated by spaces.

4

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

5

7
4 1 2 3 4
3 1 2 5
3 1 3 5
3 1 4 5
3 2 3 5
3 2 4 5
3 3 4 5

Hint

Sample 1 explanation

The sample is only for understanding the statement. In the actual testdata, $n$ will only be $529$ or $625$.

Since $m>1$, the result cannot be $\{\{1,2,3,4\}\}$. Also, because $|B_i|< 3$ makes $B_i$ useless, the only solution is to list all 3-element subsets of $\{1,2,3,4\}$, i.e. $\{\{1,2,3\},\{1,2,4\},\{1,3,4\},\{2,3,4\}\}$.

Constraints and notes

$$\def\arraystretch{1.5} \begin{array}{|c|c|c|c|}\hline \textbf{Subtask} & \bm{n=} & \bm{m_{\text{ans}}=} & \textbf{分值} \cr\hline 1 & 529 & 1.25\times 10^4 & 75 \cr\hline 2 & 625 & 1.60\times 10^4 & 25 \cr\hline \end{array}$$

If your output solution is invalid, you will not get the score for that test point.

Only when your constructed solution satisfies the requirements, and the value of $m$ does not exceed $m_{\text{ans}}$, can you obtain the score for that test point.

Translated by ChatGPT 5