루트에서 리프까지

P개의 노드와, P-1개의 간선으로 이루어진 트리가 있다. 해당 트리는 1번 노드를 루트 노드로 한다.

각 노드의 정보는 세 개의 정수 Cn, D1, D2로 주어진다.

Cn은 노드 번호.
D1과 D2는 해당 노드에 연결된 두 자식 노드의 번호.
- 만약 D1이 0이라면 해당 간선은 존재하지 않음을 의미; D2도 마찬가지이다.
- 둘 다 0이라면 해당 노드는 리프 노드임을 의미한다.

루트 노드인 1번 노드에서부터 각 리프 노드까지의 경로는 유일하며 그러한 경로들 중 가장 긴 경로의 길이를 알아보자.

입력

첫 번째 줄: 정수 P (1 \le P\le 1000)

2번부터 P번까지: 각 줄마다 세 개의 공백으로 구분된 정수 Cn, D1, D2가 주어집니다. (1 \le Cn \le P-1; 0 \le D1, D2 \le P-1)

출력

1번 노드에서 리프 노드로 가는 경로 중 가장 많은 노드를 지나가는 경로의 길이를 출력한다.

예제1

태그

출처

USACO October 2009 Gold 5

루트에서 리프까지 1초 1024MB