Alien Invasion on Mars

Aliens are planning an invasion on Mars. Mars is modeled as an undirected simple graph with n vertices (i.e., no self‐loops or multiple edges are allowed). The aliens attack in rounds controlled by the current degree of a vertex. Specifically, they proceed in rounds: in round 0 they simultaneously attack all vertices whose current degree is 0, then in round 1 they attack all vertices (in the remaining graph) with current degree 1, then round 2 for those with degree 2, and so on up to round n-1.

Important: The degree counts are dynamic. When a vertex is attacked (i.e. removed), all adjacent vertices decrease their degree by 1 immediately. A vertex may thus have a degree different from its initial degree at the time of later rounds. Note that each round targets vertices whose current degree equals the round number, and once a round passes the same degree value is not considered again.

Your task is to design the edge set of the graph (that is, choose which edges to include) so that the number of vertices that never get attacked (i.e. survive all rounds) is maximized.

For example, consider the following observation:

• An isolated vertex (degree 0) is attacked in round 0.
• A simple two‐vertex graph (one edge) has both vertices of degree 1, so they are attacked in round 1.
• A star graph with at least 3 vertices, where the center has degree at least 2 and the leaves (degree 1) are attacked in round 1, will leave the center (whose degree drops to 0 after round 1) surviving in later rounds.

After analysis one can show that the maximum number of survivors you can achieve is \(\lfloor n/3 \rfloor\) by partitioning the vertex set into groups of at least 3 vertices and forming a star in each group. If n < 3, no vertex can survive.

Input Format:
A single integer n (\(1 \leq n \leq 10^5\)), the number of vertices of the graph.

Output Format:
On the first line, output an integer representing the maximum number of survivors that can be achieved. On the second line, output an integer m — the number of edges in your constructed graph. Then output m lines, each containing two integers u and v (1-indexed) indicating an edge between vertices u and v.

Note: Your graph must be simple (no self-loops or multiple edges) and your construction must achieve the maximum number of survivors, which is \(\lfloor n/3 \rfloor\).

inputFormat

The input consists of a single integer n on one line – the number of vertices.

outputFormat

Output the maximum number of survivors, followed by the number of edges m in your constructed graph, and then m lines each containing two space-separated integers representing an edge.

sample

1

0
0