지하철

시간 제한1초메모리 제한512 MB

요약

정확히 K개의 조상-자손 쌍이 존재하도록 최소 개수의 노드로 트리를 만들고 각 노드의 부모를 출력한다.

문제

정수 K가 주어진다. 노드 쌍 (X, Y) 중 X가 Y의 조상인 쌍이 정확히 K개가 되도록, 노드 수가 최소인 트리를 만들어라.

입력은 표준 입력으로 주어지며, 한 개의 정수 K가 들어 있다. K는 해당 성질을 만족하는 쌍의 개수이다.

출력은 표준 출력으로 주어지며, N+1개의 줄로 만들어진 트리를 나타낸다. 노드 번호는 0부터 시작한다.

첫째 줄에는 트리의 노드 수 N이 들어간다.

다음 N개의 줄에는 각각 두 수 X와 T가 공백 하나를 사이에 두고 들어간다. 이때 노드 T는 노드 X의 직계 조상이다. 노드 X에 직계 조상이 없으면 T는 -1이다.