느긋한 산책

베시(Bessie)는 화창한 봄날 외양간을 나서며, 아침을 먹으러 목초지로 가는 길을 최대한 길게 걷고 싶어 한다. 외양간(노드 $1$)에서 출발한 베시는 길을 따라 걷다가 갈림길(선택 노드)에 이르면 두 갈래 길 중 하나를 고른다. 이렇게 갈림길마다 하나씩 길을 고르며 나아가다 보면, 마지막에는 어떤 길이 목초지로 이어진다.

베시는 목초지에 도착하기까지 가장 많은 길(cow path)을 지날 수 있도록 선택하고 싶어 한다. 길의 구조가 주어질 때, 베시가 가장 먼 목초지까지 걸어갈 때 지나는 길의 수를 구하여라.

농장에는 목초지가 $P$개($1 \le P \le 1000$) 있으며, 이들은 $1 \dots P-1$번으로 번호가 매겨진 $P-1$개의 선택 노드를 통해 이어진다. 외양간(노드 $1$)에서 임의의 선택 노드나 목초지로 가는 경로는 정확히 하나뿐이므로, 길들은 외양간을 뿌리로 하는 트리를 이룬다.

아래 그림은 길(선), 목초지(%), 그리고 오른쪽에 강조 표시(#)된 목초지까지의 한 경로를 나타낸다.

                 %                             %
                /                             /
      2----%   7----8----%          2----%   7####8----%
     / \      /      \             # #      #      #
    1   5----6        9----%      1   5####6        9----%
     \   \    \        \           \   \    \        #
      \   %    %        %           \   %    %        %
       \                             \
        3-----%                       3-----%
         \                             \
          4----%                        4----%
           \                             \
            %                             %

선택 노드 $9$를 거쳐 도착하는 목초지는, 베시가 아침을 먹으러 가는 길에 서로 다른 일곱 개의 길을 지나게 해 주는 두 목초지 중 하나이다. 이 두 곳이 외양간(노드 $1$)에서 가장 먼 목초지이다.

각 선택 노드는 세 정수 $C_n$, $D_1$, $D_2$로 표현된다. $C_n$은 노드 번호이고($1 \le C_n \le P-1$), $D_1$과 $D_2$는 그 노드에서 갈 수 있는 두 목적지이다($0 \le D_1 \le P-1$, $0 \le D_2 \le P-1$). 목적지가 $0$이면 그 방향이 목초지로 이어짐을 뜻하고, 그 외의 값은 그 방향에서 도달하는 선택 노드의 번호이다.

• 첫째 줄: 정수 $P$.
• 둘째 줄부터 $P$번째 줄까지: $i+1$번째 줄에는 선택 노드 하나를 나타내는 세 정수 $C_n$, $D_1$, $D_2$가 공백으로 구분되어 주어진다.

• 첫째 줄: 베시가 가장 먼 목초지까지 갈 때 지날 수 있는 길의 최대 개수를 나타내는 정수 하나.

경로 1-2-5-6-7-8-9-P (마지막 $P$는 목초지)는 가장 긴 경로 중 하나이다.