| II Olympiad of classes at the Mechanics and Mathematics Faculty of MSU in programming 2023. |
|---|
| Finished |
Once Senya was walking around Kaliningrad and discovered an interesting graph store called "Ostovok". This store stood out from many ordinary graph stores in that it only sold spanning trees (see definition). Upon entering the store, Senya discovered the only remaining graph on the counter - a complete graph on $$$n$$$ vertices (denoted $$$K_n$$$). Senya decided to buy as many spanning trees as possible, and the store clerk, the full Lady Lucy Decart, was ready to cut any spanning tree from the graph that Senya indicated to her. The cost of a spanning tree is equal to its diameter (see definition). When a spanning tree is cut from the graph, the vertices in the graph remain, but the edges contained in the spanning tree disappear.
It is necessary to find the maximum number of spanning trees that Senya can cut from $$$K_n$$$, and their total cost should be as minimal as possible. In other words, it is necessary to find as many non-intersecting spanning trees as possible, and among all such sets, the one in which the sum of the diameters of the spanning trees is minimal.
A spanning tree of a graph is a tree, a subgraph of the given graph, with the same number of vertices as the original graph.
A tree is a connected graph without cycles. Connectivity means the existence of a path between any pair of vertices.
A subgraph is a part of a graph in which we take some of its vertices and edges. In other words, the graph $$$H$$$ is a subgraph of the graph $$$G$$$ if the vertices and edges of $$$H$$$ are a subset of the vertices and edges of $$$G$$$.
The diameter of a graph is the number equal to the distance between the farthest apart vertices of the graph.
The input consists of a single number $$$n$$$ ($$$2\le n \le 1000$$$) - the number of vertices in the complete graph.
In the first line, output a single number $$$k$$$ - the maximum number of spanning trees that Senya can buy.
Then output $$$k$$$ sets of $$$n-1$$$ lines each, each describing one of the $$$k$$$ spanning trees as $$$n-1$$$ edges.
If there are multiple optimal answers, any of them can be output.
The spanning trees in the output are separated by line breaks for ease of understanding, but it is not necessary to include line breaks between the spanning trees.
2
1 1 2
3
1 1 2 1 3
4
2 1 2 2 3 3 4 1 3 1 4 2 4
Illustrations for examples, edges of the same color form spanning trees.
In the third example, a variant of dividing into two spanning trees, each with a diameter of $$$3$$$, is proposed, i.e. the sum of the diameters is $$$6$$$. It can be proven that a larger number of spanning trees cannot be obtained, and it is impossible to divide the graph $$$K_4$$$ into two spanning trees with a sum of diameters less than $$$6$$$.
