시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 512 MB158765945.385%

문제

S과 주어졌을 때, 다음 두 조건을 만족하는 트리를 만드는 프로그램을 작성하시오.

  • 트리의 노드의 개수는 1보다 크거나 같고, 500보다 작거나 같다.
  • 길이가 3인 단순 경로의 개수는 S개이다.

단순 경로란 같은 정점을 두 번 이상 반복하지 않는 경로를 말한다.

경로에서 방향은 상관없다. A-B-C-D는 D-C-B-A와 같은 경로이다.

입력

첫째 줄에 S가 주어진다. (1 ≤ S ≤ 10,000)

출력

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

둘째 줄부터 N-1개의 줄에 간선의 양 끝 점을 공백으로 구분해서 출력한다.

정점의 번호는 0보다 크거나 같고, N-1보다 작거나 같아야 한다.

예제 입력 1

1

예제 출력 1

4
0 1
1 2
2 3

예제 입력 2

2

예제 출력 2

5
0 1
1 2
2 3
3 4

예제 입력 3

6

예제 출력 3

7
0 1
1 2
0 3
3 4
0 5
5 6

출처