Subway

Time limit1sMemory limit512 MB

Summary

Build a tree with the fewest nodes so that exactly K ordered ancestor-descendant pairs exist, and output the parent of every node.

Level: Medium7 of 10
Topics: Tree, Greedy, Math, Implementation
Solved: No attempts yet

Problem

Given an integer K, build a tree with the minimum number of nodes such that exactly K pairs of nodes (X, Y) have X as an ancestor of Y.

Input

The input is read from the console and contains a single integer K, the number of pairs with the specified property.

Output

The output is written to the console and contains N+1 lines describing the tree. Nodes are indexed from 0.

The first line contains N, the number of nodes in the tree.

Each of the following N lines contains two numbers X and T separated by a space: node T is the direct ancestor of node X. If node X has no direct ancestor, T is -1.

Examples2

Example 1
Input
```
2
```
Expected output
```
3
0 -1
1 0
2 0
```
Example 2
Input
```
4
```
Expected output
```
4
0 -1
1 0
2 0
3 2
```