## COCI '19 Contest 6 #3 Konstrukcija

View as PDF

Points: 20 (partial)
Time limit: 1.0s
Memory limit: 512M

Problem types

Let be a directed acyclic graph. If are distinct vertices of such that there is a path from to , there is a path from to , …, and there is a path from to , we say that array is an ordered array starting at and ending at . Note that between neighbouring elements and of ordered array it isn't necessary to exist a direct edge, it is enough for the path to exist from to .

For this definition of an ordered array , we define its length . Therefore, the length of an ordered array is equal to the number of vertices it holds. Note that the ordered array can have a length of when holding a single vertex which represents both its beginning and its end.

Also, for an ordered array we can define its sign as . For vertices and of , let's denote with a set of all ordered arrays that start in and end in .

Finally, we define the tension between nodes and as . Therefore, the tension between nodes and equals the sum of signs of all ordered arrays that start in and end in .

An integer is given. Your task is to construct a directed acyclic graph with at most vertices and at most edges for which holds. Number in the previous expression denotes the number of vertices in a graph. Vertices of a graph should be indexed using positive integers from to .

#### Input Specification

The first line contains an integer from the task description.

#### Output Specification

In the first line you should output the number of vertices and the number of edges of the constructed graph. Let's denote the number of vertices of that graph with , and the number of edges with .

In the -th of the next lines you should output two distinct integers and , which represent the -th edge which is directed from vertex with index towards vertex with index . Each edge must appear only once in the output.

Also, the absolute value of tension between each two nodes in the graph must be less or equal to . If there are multiple solutions, output any of them.

115
215
320

#### Sample Input 1

0

#### Sample Output 1

6 6
1 4
1 5
4 3
5 3
3 2
2 6

#### Explanation of Sample Output 1

The constructed graph has vertices. Ordered arrays that start in and end in are: . Their lengths are (in order): , so their signs are . Therefore, the tension between and is equal to .

#### Sample Input 2

1

#### Sample Output 2

1 0

#### Sample Input 3

2

#### Sample Output 3

6 8
1 2
1 3
1 4
1 5
5 4
2 6
3 6
4 6