You love doing graph theory problems. You've recently stumbled upon a classical problem : Count the number of 4-cliques in an undirected graph.
Given an undirected simple graph G, a 4-clique of G is a set of 4 nodes such that all pairs of nodes in this set are directly connected by an edge.
This task would be too easy for you, wouldn't it? Thus, your task here is to find an undirected simple graph G with exactly k 4-cliques. Can you solve this task?
输入描述:
The first line of input contains a single integer k (1 ≤ k ≤ 106).
输出描述:
On the first line, output two space-separated integers, n, m (1 ≤ n ≤ 75, 1 ≤ m ≤ n * (n - 1) / 2). On the next m lines, output two space-separated integers denoting an edge of the graph u, v (1 ≤ u, v ≤ n), where u and v are the endpoints of the edge.
Your graph must not contain any self-loops or multiple edges between the same pair of nodes. Any graph that has exactly k 4-cliques and satisfies the constraints will be accepted. It can be proven that a solution always exist under the given constraints.
示例1
输出
复制
4 6
1 2
1 3
1 4
2 3
2 4
4 3
说明
In the sample, the whole graph is a 4-clique.