# Buggy DFS

## Problem Description

You are currently studying a graph traversal algorithm called the Depth First Search (DFS). However, due to a bug, your algorithm is slightly different from the standard DFS. The following is an algorithm for your Buggy DFS (BDFS), assuming the graph has $ N $ nodes (numbered from $ 1 $ to $ N $ ).

```
<pre class="verbatim"><br></br>  BDFS():<br></br>    let S be an empty stack<br></br>    let FLAG be a boolean array of size N which are all false initially<br></br>    let counter be an integer initialized with 0<br></br><br></br>    push 1 to S<br></br><br></br>    while S is not empty:<br></br>      pop the top element of S into u<br></br>      FLAG[u] = true<br></br><br></br>      for each v neighbour of u in ascending order:<br></br>        counter = counter + 1<br></br>        if FLAG[v] is false:<br></br>          push v to S<br></br><br></br>    return counter<br></br>
```

You realized that the bug made the algorithm slower than standard DFS, which can be investigated by the return value of the function BDFS(). To investigate the behavior of this algorithm, you want to make some test cases by constructing an undirected simple graph such that the function BDFS() returns $ K $ , or determine if it is impossible to do so.

## Input Format

A single line consisting of an integer $ K $ ( $ 1 \leq K \leq 10^9 $ ).

## Output Format

If it is impossible to construct an undirected simple graph such that the function BDFS() returns $ K $ , then output -1 -1 in a single line.

Otherwise, output the graph in the following format. The first line consists of two integers $ N $ and $ M $ , representing the number of nodes and undirected edges in the graph, respectively. Each of the next $ M $ lines consists of two integers $ u $ and $ v $ , representing an undirected edge that connects node $ u $ and node $ v $ . You are allowed to output the edges in any order. This graph has to satisfy the following constraints:

- $ 1 \leq N \leq 32\,768 $
- $ 1 \leq M \leq 65\,536 $
- $ 1 \leq u, v \leq N $ , for all edges.
- The graph is a simple graph, i.e. there are no multi-edges nor self-loops.

Note that you are not required to minimize the number of nodes or edges. It can be proven that if constructing a graph in which the return value of BDFS() is $ K $ is possible, then there exists one that satisfies all the constraints above. If there are several solutions, you can output any of them.

## Sample #1

### Sample Input #1

```
8
```

### Sample Output #1

```
3 3
1 2
1 3
2 3
```

## Sample #2

### Sample Input #2

```
1
```

### Sample Output #2

```
-1 -1
```

## Sample #3

### Sample Input #3

```
23
```

### Sample Output #3

```
5 7
4 5
2 3
3 1
2 4
4 3
2 1
1 5
```

## Hint

Explanation for the sample input/output #1

The graph on the left describes the output of this sample. The graph on the right describes another valid solution for this sample.

 ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF2045L/f1ba627a6dee4a42828d91349340ced7a2cb28cd.png)Explanation for the sample input/output #3

The following graph describes the output of this sample.

 ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF2045L/e5b77af5c2622d444d81c6aab8c41cda5b753182.png)

## Limit



Time Limit
1.00s

Memory Limit
1000.00MB

Tags: constructive algorithms
Difficulty: 3000