彼得森喜欢学习新语言,但他最喜欢的爱好是创造新语言。语言是单词的集合,单词是小写拉丁字母的序列。
彼得森每天早上都会说新的语言。存储整个语言是一项艰巨的任务,因此彼得森发明了新的数据结构来存储他的语言,称为扫帚。扫帚是有根的树,边缘标有字母。最初,扫帚由唯一的顶点 - 扫帚的根部表示。当彼得森想要向语言中添加新单词时,他站在词根处,一一处理新单词的字母。考虑彼得森站在顶点 u 处。如果从 u 开始有一条边标有当前字母,则 Peterson 会穿过这条边。否则 Peterson 添加从 u 到新顶点 v 的新边,用当前字母标记它并穿过新边。扫帚的大小是扫帚中顶点的数量。
工作日结束后的晚上,彼得森无法理解他今天早上所说的语言。这对于无聊的彼得森来说太难了,他试图让它变得更简单。语言的简化是从该语言的某些单词中删除一些字母的过程。形式上,Peterson 取一些正整数 p 并从该语言的所有长度至少为 p 的单词中删除第 p 个字母。单词中的字母从 1 开始索引。Peterson 认为简化应该改变至少一个单词,即必须有至少一个长度至少为 p 的单词。 Peterson 试图使他的语言尽可能简单,因此他希望选择 p 以使他的简化语言的扫帚尺寸尽可能小。
彼得森对这个任务非常恼火,所以他向你寻求帮助。编写一个程序来找出扫帚的最小可能尺寸和整数 p。
输入
输入的第一行包含整数 n (2 ≤ n ≤ 3·105) — 扫帚的大小。
接下来的 n - 1 行描述扫帚:其中第 i 行包含整数 ui、vi 和字母 xi - 描述从 ui 到 vi 的边缘,并用字母 xi 标记。
顶点编号为 1 到 n。所有 xi 均为小写拉丁字母。顶点 1 是扫帚的根部。
边缘描述了由彼得森语言制成的正确扫帚。
输出
输出的第一行应包含扫帚简化后的最小可能尺寸。输出的第二行应包含可供选择的整数 p。如果有多个合适的 p 值,则打印最小的一个。
示例
输入 #1
5 1 2 c 2 3 a 3 4 t 2 5 t
输出 #1
3 2
输入 #2
16 1 2 o 2 3 f 1 4 p 4 5 i 5 6 e 6 7 c 7 8 e 4 9 r 9 10 e 10 11 t 11 12 t 12 13 y 10 14 f 14 15 i 15 16 x
输出 #2
12 2
注意
第二个示例测试中的 Broom 可以使用语言“piece”、“of”、“pie”、“pretty”、“prefix”构建。 p = 2 的简化获得了单词“pece”、“o”、“pe”、“petty”、“pefix”的语言。这种语言为我们提供了尽可能最小尺寸的扫帚。