시간 제한메모리 제한제출정답맞은 사람정답 비율
2 초 512 MB1000.000%

문제

You are given a positive integer $K \le 60$. Construct a graph with at most $20$ vertices with the following property: there are exactly $K$ unordered pairs of vertices $(u, v)$ such that there is a Hamiltonian path between $u$ and $v$ in this graph.

It can be shown that, under these constraints, the solution always exists.

Recall that a Hamiltonian path is a path between two vertices of a graph that visits each vertex exactly once.

입력

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

출력

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 your graph respectively.

In each of the next $m$ lines, output two integers $u$ and $v$ ($1 \le u, v \le n$, $u \neq v$), representing the edge $(u, v)$ of your graph. All edges have to be distinct.

예제 입력 1

1

예제 출력 1

2 1
1 2

예제 입력 2

2

예제 출력 2

4 4
1 2
1 3
2 3
3 4

예제 입력 3

3

예제 출력 3

3 3
1 2
2 3
3 1