Description

Bessie looks out of the barn door and sees a beautiful spring morning. She thinks, "I really, really want to stroll through the meadow in the spring breeze and feel the tender grass gently brushing my hooves." She knows that once she leaves the barn, she will follow a trail for a while and then reach a fork with two choices. She will keep encountering more forks and making more choices until she reaches a lush pasture.

She decides to choose a route that lets her walk through as many trails as possible on her way to breakfast. Given the description of these trails, compute the maximum number of trails Bessie can traverse. Assume that right outside the barn there are $2$ outgoing trails, and Bessie must choose one of them.

There are $P-1$ ($1 \le P \le 1000$) branching nodes (numbered $1 \ldots P-1$) leading to $P$ pastures, connected by trails. For any node, there is exactly one path starting from the barn (which is labeled node $1$) that reaches it.

Consider the figure below. Line segments represent trails, and % represents a pasture. In the figure on the right, # highlights a path to a pasture.

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

The pasture reached from branching node $9$ is one of the two pastures that allow Bessie to traverse the most trails. On the way to breakfast, Bessie will traverse $7$ distinct trails. These pastures are the "farthest" from the barn, i.e., node $1$.

Each node is described by three integers $C, D_1, D_2$. Here, $C$ is the node label ($1 \le C < P$), and $D_1$ and $D_2$ are the endpoints of the two outgoing trails from node $C$ ($0 \le D_1, D_2 < P$). If $D_1$ is $0$, that trail leads to a pasture; the same applies to $D_2$.

Input Format

The first line contains a single integer $P$.

Each of the following $P-1$ lines contains three integers $C, D_1, D_2$ describing one node.

Output Format

Output a single integer: the maximum number of trails (edges) Bessie can traverse.

10 
7 8 0 
5 0 6 
9 0 0 
6 0 7 
3 4 0 
2 5 0 
8 0 9 
4 0 0 
1 2 3 

7 

Hint

The input is exactly the map shown in the Description.

1-2-5-6-7-8-9-pasture is one of the longest paths.

Translated by ChatGPT 5