버그가 있는 DFS

당신은 Depth First Search(DFS)라는 그래프 탐색 알고리즘을 공부하고 있다. 그런데 버그 때문에 이 알고리즘은 표준 DFS와 조금 다르게 동작한다. 노드가 $N$개($1$번부터 $N$번까지 번호가 붙어 있음)인 그래프에서 버그가 있는 DFS(BDFS)의 동작은 다음과 같다.

BDFS():
  let S be an empty stack
  let FLAG be a boolean array of size N which are all false initially
  let counter be an integer initialized with 0

  push 1 to S

  while S is not empty:
    pop the top element of S into u
    FLAG[u] = true

    for each v neighbour of u in ascending order:
      counter = counter + 1
      if FLAG[v] is false:
        push v to S

  return counter

버그 때문에 이 알고리즘은 표준 DFS보다 느려지며, 이는 BDFS()의 반환값으로 확인할 수 있다. 이 동작을 살펴보기 위해, BDFS()가 $K$를 반환하는 단순 무방향 그래프를 만들거나, 그런 그래프가 없음을 판단하려 한다.

한 줄에 정수 $K$($1 \le K \le 10^9$)가 주어진다.

BDFS()가 $K$를 반환하는 단순 무방향 그래프를 만들 수 없다면 한 줄에 -1 -1을 출력한다.

그렇지 않다면 다음 형식으로 그래프를 출력한다. 첫 줄에는 노드 수 $N$과 무방향 간선 수 $M$을 출력한다. 이어지는 $M$개의 줄에는 노드 $u$와 $v$를 잇는 무방향 간선을 한 줄에 하나씩 출력한다. 간선의 순서는 자유롭다. 그래프는 다음 조건을 만족해야 한다.

• $1 \le N \le 32768$
• $1 \le M \le 65536$
• 모든 간선에 대해 $1 \le u, v \le N$
• 단순 그래프이다. 즉 다중 간선과 자기 루프가 없다.

$N$과 $M$을 최소화할 필요는 없다. BDFS()가 $K$를 반환하는 그래프가 존재한다면, 위 조건을 모두 만족하는 그래프가 존재함이 증명되어 있다. 해가 여러 개라면 그중 아무것이나 출력하면 된다.