트리와 경로의 길이 2

정수 $S$가 주어졌을 때, 길이가 3인 단순 경로가 정확히 $S$개인 트리를 만든다. 트리의 정점 개수 $N$은 1 이상 500 이하여야 한다.

단순 경로는 같은 정점을 두 번 이상 지나지 않는 경로이고, 경로의 길이는 경로에 포함된 간선의 개수이다. 경로의 방향은 구분하지 않는다. A-B-C-D와 D-C-B-A는 같은 경로이다.

조건을 만족하는 트리는 여러 개이므로, 답이 하나로 정해지도록 출력할 트리의 모양을 다음과 같이 제한한다.

정점에는 0번부터 $N-1$번까지 번호를 붙인다. 먼저 간선 (0, 1), (1, 2), (2, 3)으로 이루어진 경로를 만든다. 여기에 잎을 붙이는데, 잎을 붙일 수 있는 정점은 0번, 1번, 3번뿐이고 각각 $p$개, $q$개, $r$개를 붙인다 ($p, q, r \ge 0$). 새로 붙인 잎에는 4번부터 번호를 차례로 매기며, 0번에 붙인 잎, 1번에 붙인 잎, 3번에 붙인 잎 순서로 번호를 준다. 따라서 $N = 4 + p + q + r$이다.

이런 모양의 트리 중 길이가 3인 단순 경로가 정확히 $S$개인 트리를 찾아, 그중 $N$이 가장 작은 것을 출력한다. $N$이 가장 작은 트리가 여러 개면 $(p, q, r)$이 사전순으로 가장 앞서는 것을 출력한다. 주어진 범위의 모든 $S$에 대해 이런 트리가 존재하고, $N$은 항상 500 이하이다.

첫째 줄에 $S$가 주어진다. ($1 \le S \le 10000$)

첫째 줄에 정점의 개수 $N$을 출력한다.

둘째 줄부터 $N-1$개의 줄에 간선의 양 끝 정점 번호를 공백으로 구분해 출력한다. 간선 (0, 1), (1, 2), (2, 3)을 이 순서로 먼저 출력하고, 그다음에 잎 간선을 잎 번호가 작은 것부터 출력한다. 잎 간선은 잎을 붙인 정점의 번호를 먼저 쓰고 잎의 번호를 나중에 쓴다.