OI题库

如果您不想使用繁体字阅读,您可以使用OpeeCC进行转换.

Bessie透過牛棚的大門向外望去。發現今天是一個美麗的春季早晨。她想，“我真的好想好想沐浴著春風，走在草地之中，感受嫩草溫柔地撫摸四蹄的感覺。”她知道一旦她離開了牛棚，她將沿著一條小徑走一段路，然後就會出現一個三岔路口，她必須在兩條小徑中選擇一條繼續走下去。然後她又會遇到更多的三岔路口，進行更多的選擇，直到她到達一個青翠的牧場為止。

她決定坐一個選擇使得她在去吃早草的路途中可以走過最多的小徑。給你這些小徑的描述，要求Bessie最多可以走過多少條小徑。假定Bessie一出牛棚就有2條路徑，Bessie需要從中選擇一條。

農場中有P-1 (1 <= P <= 1,000) 個分岔節點（範圍是1..P），引向P片草地，它們之間由小徑連接。對任意一個節點來說，只有一條從牛棚（被標記為節點1）開始的路徑可以到達。

考慮下面的圖。線段表示小徑，"%"表示草地。右邊的圖中的"#"表示一條到達草地的高亮的路徑。

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

從分岔節點9到達的草地是兩個可以讓Bessie走過最多小徑的草地之一。在去吃早草的路上Bessie將走過7條不同的小徑。這些草地是離牛棚也就是節點1最“遠”的。

由3個整數來表示每一個節點：Cn, D1和D2，Cn是節點的編號(1 <= Cn <= P-1); D1和D2是由該節點引出的兩條小徑的終點(0 <= D1 <= P-1; 0 <= D2 <= P-1)。如果D1為0，表示這條小徑引向的是一片牧草地；D2也一樣。


輸入格式:

* 第1行: 一個單獨的整數: P

* 第2到第P行: 第i+1行有3個由空格隔開的整數，表示一個分岔節點Cn, D1和D2。

樣例輸入 (文件 stroll.in):

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

輸入細節:

這個輸入表示題目描述中的例子。

輸出格式:

* 第一行: 一個單獨的整數，表示Bessie去最遠的草地的路上最多可以走過的小徑的數目。

樣例輸出 (文件 stroll.out):

7

輸出細節:

1-2-5-6-7-8-9-P是最長的一條路徑之一。