The Leisurely Stroll

Bessie steps out of the barn on a beautiful spring day and wants to enjoy the longest possible walk to the pastures before breakfast. Starting at the barn (node $1$), she walks along a path until she reaches a choice-node, where she picks one of two paths. She keeps choosing at each choice-node until a path finally leads her to a pasture.

Bessie wants to make the set of choices that lets her walk over the greatest number of cow paths on the way to a pasture. Given the layout of the paths, determine how many cow paths she traverses when she walks to the furthest pasture.

The farm has $P$ ($1 \le P \le 1000$) pastures, reached through $P-1$ choice-nodes numbered $1 \dots P-1$ and connected by paths. From the barn (node $1$) there is exactly one route to any choice-node or pasture, so the paths form a tree rooted at the barn.

The picture below shows the paths (lines), the pastures (%), and, on the right, one highlighted (#) route to a pasture:

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

The pasture reached through choice-node $9$ is one of two pastures that let Bessie walk over seven different cow paths on the way to breakfast; these are the furthest pastures from the barn (node $1$).

Each choice-node is described by three integers $C_n$, $D_1$, and $D_2$. $C_n$ is the node number ($1 \le C_n \le P-1$); $D_1$ and $D_2$ are the two destinations reachable from that node ($0 \le D_1 \le P-1$, $0 \le D_2 \le P-1$). A destination of $0$ means that direction leads to a pasture; any other value is the number of the choice-node reached in that direction.

• Line $1$: a single integer $P$.
• Lines $2 \dots P$: line $i+1$ contains three space-separated integers describing one choice-node: $C_n$, $D_1$, and $D_2$.

• Line $1$: a single integer, the largest number of cow paths Bessie can traverse on the way to the furthest pasture.

The route 1-2-5-6-7-8-9-P (ending at a pasture) is one of the longest possible walks.