424. Beautiful graph
Time limit per test: 0.25
second(s)
Memory limit: 262144
kilobytes
input: standard
output: standard
Misha is currently interested in undirected graphs that contain no two simple cycles sharing exactly one edge and contains no loops. Let's call them
beautiful graphs. He wants to find the maximal beatiful graph, that is the beautiful graph that contains the most edges among all beautiful graphs with at most
n vertices. But Misha is going to leave on vacation, so he asked you to help him with this problem.
Input
The input file contains a single integer
n (1 ≤
n ≤ 100) — the maximum number of vertices your graph can contain.
Output
Output the number of vertices
V (1 ≤
V ≤
n) and the number of edges
E of your graph to the first line of the output file, separated with a space. Then output
E lines with two integer numbers each, again separated with a space. The two numbers should be the numbers of the vertices connected by the corresponding edge. The vertices of the graph are numbered from 1 to
V. You can output edges in any order. If there are several maximal graphs, output any.
Example(s)
sample input

sample output

1

1 0

sample input

sample output

2

2 1
1 2

sample input

sample output

3

3 3
1 2
2 3
1 3
