問題文

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

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

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

入力

入力は以下の形式で与えられる。

$n$ $a_1$ $b_1$ $t_1$ $a_2$ $b_2$ $t_2$ $...$ $a_{n-1}$ $b_{n-1}$ $t_{n-1}$

• $1$ 行目には、拠点の数 $n$ ( $2 \\leq n \\leq 100{,}000$) が与えられる。
• $2$ 行目から続く $n-1$ 行には、拠点間を繋ぐ通信路の情報が与えられる。
• $1 \\leq a_i, b_i \\leq n,$ $a_i \\neq b_i$
• $t_i = 1$ のとき、$a_i$ から $b_i$ へと単方向通信に使える通信路が存在することを意味する。
• $t_i = 2$ のとき、$a_i$ と $b_i$ の間に双方向通信に使える通信路が存在することを意味する。

出力

求める値を一行で出力せよ。

入力例1

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

出力例1

2

入力例2

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

出力例2

3