Problem Description

Indeed Corporation values Speed and Price. Due to their emphasis on Price, the development bases of Indeed around the world are connected in a network as follows:

1. Some communication paths can only be used for unidirectional communication.
2. If the direction of all communication paths is ignored, there is exactly one path that allows communication between any two bases.

The graph satisfying these conditions forms a tree structure. Since they also value Speed, the employees want to know the two bases that can communicate with the most number of intermediate bases. What is the number of intermediate bases between such two bases?

Input Format

The input is given in the following format:

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

• The first line contains the number of bases $ n $ ($2\ \leq\ n\ \leq\ 100{,}000$).
• The next $ n-1 $ lines contain the information about the communication paths between bases.
• $1\ \leq\ a_i,\ b_i\ \leq\ n,$ $a_i\ \neq\ b_i$
• $t_i\ =\ 1$ means there is a unidirectional communication path from $ a_i $ to $ b_i $.
• $t_i\ =\ 2$ means there is a bidirectional communication path between $ a_i $ and $ b_i $.

Output Format

Output the desired value in one line.

Sample Input and Output

Sample Input #1

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

Sample Output #1

2

Sample Input #2

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

Sample Output #2

3

Notes/Hints

None

见题面 Input 部分

见题面 Output 部分