問題文

Indeed 社は、Speed と Price を重視している。
Price を重視しているため、世界中に存在する Indeed 社の開発拠点は次のようなネットワークでつながれている。

1. 一部の通信路は単方向通信しかできない。
2. 全ての通信路の向きを無視した場合、任意の $2$ 拠点間において、通信路をたどって行けるようなパスがちょうど一つ存在する。

以上の条件を満たすグラフは木構造になる。
Speedも重視しているため、社員らは通信できる拠点のなかで最も中継する拠点数が多い $2$ 拠点を知りたがっている。
そのような $2$ 拠点間において、中継する拠点数はいくつになるだろうか。

入力例1

5
1 2 2
1 3 2
2 4 1
3 5 1

5
1 2 2
1 3 2
2 4 1
3 5 1

出力例1

2

2

入力例2

8
2 1 1
2 5 1
8 2 1
3 8 1
4 2 2
7 4 1
4 6 1

8
2 1 1
2 5 1
8 2 1
3 8 1
4 2 2
7 4 1
4 6 1

出力例2

3

3