题目背景

猪王喝醉了，忘记了别人的名字。

题目描述

猪国的名字很有特点，它们都是一些回文串。

不仅如此，猪国的名字都来源于一棵 $n$ 个点的命名树。命名树的每条边上都写着一个猪国字符，可以用 $[1, 10^3]$ 之间的整数表示。

猪国的名字都是命名树上某一条简单路径的边上所写字符所构成的字符串。

猪王今天喝醉了，他忘记了别人的名字。这时他想知道，对于一棵确定的命名树，名字最长可以有多长？

一句话题意：求树上最长回文串的长度，字符在边上，字符集为 $[1, 10^3]$ 中的整数。

输入格式

从文件 name.in 中读入数据。

一行一个正整数 $n$，表示命名树的大小。

接下来 $n − 1$ 行，每行三个正整数 $x, y, z$，表示命名树上有一条 $x$ 连向 $y$、写了字符 $z$ 的边。

输出格式

输出到文件 name.out 中。

一行一个整数，表示可能的最长名字的长度。

样例

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

2

数据范围与提示