409256: GYM103469 H Hamiltonian

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

2 1
1 2

2

4 4
1 2
1 3
2 3
3 4

3

3 3
1 2
2 3
3 1