#2761 Three Tree

10  1 s   128 MB  

Description

정점의 개수가 N 인 트리가 있다. 트리의 각 정점의 번호는 1 부터 N 사이의 서로 다른 정수이다. 한 트리에 존재하는 길이가 3 인 단순 경로의 수를 S 라 하자.

<길이가 3인 단순 경로가 두 개 존재하는 트리 예시>

예를 들어서, 위의 그림처럼 트리가 있을 경우 길이가 3 인 단순 경로는 [1, 2, 3, 4], [5,2,3,4]로 두 개가 존재한다. 트리에서 단순 경로의 수를 세는 것은 쉬운 문제이다.

그렇다면 트리에 존재하는 단순 경로의 수 S 가 주어질 때에, 실제로 S 개의 길이 3 짜리 단순 경로를 가지는 트리를 복원해보자. 가능한 트리의 종류가 여러 가지인 경우 그 중 아무것이나 출력한다. , 트리를 이루는 정점의 개수는 500 개 이하여야 한다.

Input

첫 줄에 문제에서 요구하는 길이가 3 인 단순 경로의 수 S 가 주어진다. S 1 10,000 사이의 정수이다.

Output

출력의 첫 줄에는 정점의 개수 을 출력한다. N 은 500 이하의 자연수여야 한다그 후 (N-1)개의 줄에 걸쳐서한 줄에 하나의 간선을 이루는 두 정점의 번호를 출력한다.

Sample Input

Sample Output

1
4
1 2
2 3
3 4

Source

shake 2016! 본선