Hamiltonian

Time limit2sMemory limit512 MB

Summary

Given K up to 60, build a graph with at most 20 vertices that has exactly K unordered vertex pairs joined by a Hamiltonian path. The output is the graph's edge list.

Level: Hard8 of 10
Topics: Implementation, Graph, Bit manipulation
Solved: No attempts yet

Problem

Given a positive integer $K \le 60$ , construct a graph with at most $20$ vertices that has exactly $K$ unordered pairs of vertices $(u, v)$ such that a Hamiltonian path exists between $u$ and $v$ . It can be shown that a solution always exists under these constraints. A Hamiltonian path is a path between two vertices that visits each vertex exactly once.

Input

The only line of the input contains a single integer $K$ ( $1 \le K \le 60$ ).

Output

On the first line, output two integers $n$ and $m$ ( $2 \le n \le 20$ , $0 \le m \le \frac{n(n-1)}{2}$ ), the number of vertices and the number of edges. In each of the next $m$ lines, output one edge $(u, v)$ ( $1 \le u, v \le n$ , $u \neq v$ ). All edges must be distinct.

Examples3

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