Minimal Bus Route Planning

In this problem, you are given an integer (n) representing the number of bus routes. There are also (m) bus stops numbered from (1) to (m). Your task is to plan the routes by choosing a subset of stops for each route such that all the following conditions are satisfied:

1. Each route must pass through at least two stops.
2. Each bus stop can be used by at most 3 routes.
3. For any two distinct routes (i) and (j) ((i \neq j)), there must exist a third route (k) (with (k \neq i) and (k \neq j)) such that route (k) is associated with both route (i) and route (j) (i.e. there is at least one stop that both (k) and (i) pass and at least one stop that both (k) and (j) pass).

Additionally, you are required to choose the smallest possible (m) (i.e. the minimal number of stops) for which a valid planning scheme exists, and output one valid plan.

A useful observation is that since each route must visit at least two stops, the total number of route appearances is at least (2n). As each stop can appear at most 3 times, we have [ 3m \ge 2n \quad \Longrightarrow \quad m \ge \lceil \frac{2n}{3} \rceil. ]

In this problem a valid (and minimal) solution is to take [ m = \lceil \frac{2n}{3} \rceil. ]

Then, for (i=1,2,\ldots,n), we define the stops for route (i) as

[ S(i)=\Big{;\big((i-1)\bmod m\big)+1, ;\big(i\bmod m\big)+1\Big}. ]

It can be verified that with this assignment:

• Each route gets exactly 2 stops (and so condition 1 is satisfied),
• The frequency of any bus stop (i.e. how many routes use it) does not exceed 3 (condition 2), and
• For any two routes (i) and (j) (even if they share the same pair of stops) one may find a third route (k) such that (S(i)\cap S(k)\neq \emptyset) and (S(j)\cap S(k)\neq \emptyset) (condition 3). For example, when two routes share the identical pair the stop frequencies ensure that at least one other route uses one of those stops.

The output format is as follows. The first line of the output contains the minimal (m). Then (n) lines follow. The (i)-th line describes route (i) by first outputting the number of stops on that route (which is 2) and then the list of stops in increasing order.

inputFormat

The input consists of a single integer (n) ((3 \le n \le 10^5)), representing the number of bus routes. It is guaranteed that a valid solution exists.

outputFormat

First, print the minimal number (m = \lceil \frac{2n}{3} \rceil) of bus stops. Then print (n) lines; the (i)-th line should contain 2 integers: the two distinct stops (in increasing order) that route (i) passes.

sample

3

2
2 1 2
2 1 2
2 1 2