CF778C.Peterson Polyglot

Peterson loves to learn new languages, but his favorite hobby is making new ones. Language is a set of words, and word is a sequence of lowercase Latin letters.

Peterson makes new language every morning. It is difficult task to store the whole language, so Peterson have invented new data structure for storing his languages which is called broom. Broom is rooted tree with edges marked with letters. Initially broom is represented by the only vertex — the root of the broom. When Peterson wants to add new word to the language he stands at the root and processes the letters of new word one by one. Consider that Peterson stands at the vertex u. If there is an edge from u marked with current letter, Peterson goes through this edge. Otherwise Peterson adds new edge from u to the new vertex v, marks it with the current letter and goes through the new edge. Size of broom is the number of vertices in it.

In the evening after working day Peterson can't understand the language he made this morning. It is too difficult for bored Peterson and he tries to make it simpler. Simplification of the language is the process of erasing some letters from some words of this language. Formally, Peterson takes some positive integer p and erases p-th letter from all the words of this language having length at least p. Letters in words are indexed starting by 1. Peterson considers that simplification should change at least one word, i.e. there has to be at least one word of length at least p. Peterson tries to make his language as simple as possible, so he wants to choose p such that the size of the broom for his simplified language is as small as possible.

Peterson is pretty annoyed with this task so he asks you for help. Write a program to find the smallest possible size of the broom and integer p.

彼得森热爱学习新语言，但他最钟爱的爱好是创造新语言。一种语言是由若干单词组成的集合，而一个单词则是由小写拉丁字母构成的序列。

彼得森每天早晨都会创造一门新语言。由于完整地存储整门语言十分困难，彼得森发明了一种名为“扫帚（broom）”的新数据结构来存储他的语言。“扫帚”是一棵有根树，其边被标记为字母。初始时，“扫帚”仅包含一个顶点——即它的根节点。当彼得森希望向语言中添加一个新单词时，他从根节点出发，逐个处理该单词中的字母。假设当前彼得森位于顶点 $u$：若存在一条从 $u$ 出发、标记为当前字母的边，则他沿该边移动；否则，他从 $u$ 向一个新顶点 $v$ 添加一条新边，并将该边标记为当前字母，然后沿这条新边移动。“扫帚”的大小定义为其中顶点的总数。

在工作日结束后的傍晚，彼得森已无法理解他当天早晨所创造的语言。这对他这个感到无聊的人来说实在太难了，于是他试图将其简化。语言的简化操作是指从该语言的某些单词中删除某些字母。形式化地说，彼得森选定某个正整数 $p$，然后对所有长度不小于 $p$ 的单词，删去其第 $p$ 个字母（单词中字母的下标从 $1$ 开始计数）。彼得森认为，简化操作必须至少改变一个单词，即至少存在一个长度不小于 $p$ 的单词。彼得森希望让自己的语言尽可能简单，因此他希望选择一个 $p$，使得其简化后语言所对应的“扫帚”大小最小。

彼得森对这项任务感到非常厌烦，因此他请求你帮忙。请编写一个程序，找出可能的最小“扫帚”大小以及对应的整数 $p$。

The first line of input contains integer n (2 ≤ n ≤ 3·105) — the size of the broom.

Next n - 1 lines describe the broom: i-th of them contains integers u__i, v__i and letter x__i — describing the edge from u__i to v__i marked with letter x__i.

Vertices are numbered from 1 to n. All x__i are lowercase latin letters. Vertex 1 is the root of the broom.

Edges describe correct broom which is made from Peterson's language.

输入的第一行包含一个整数 $ n $（$ 2 \leq n \leq 3 \cdot 10^5 $）—— 表示扫帚树的大小。

接下来的 $ n-1 $ 行描述该扫帚树：第 $ i $ 行包含两个整数 $ u_i $、$ v_i $ 和一个字母 $ x_i $，表示一条从顶点 $ u_i $ 指向顶点 $ v_i $ 的边，其上标记的字母为 $ x_i $。

顶点编号为 $ 1 $ 到 $ n $。所有 $ x_i $ 均为小写拉丁字母。顶点 $ 1 $ 是扫帚树的根节点。

这些边构成一棵合法的扫帚树，且该扫帚树由 Peterson 语言生成。

The first line of output should contain the minimum possible size of the broom after its simplification. The second line of output should contain integer p to choose. If there are several suitable p values, print the smallest one.

输出的第一行应包含简化后扫帚的最小可能大小。
输出的第二行应包含需选择的整数 $p$。如果存在多个合适的 $p$ 值，请输出其中最小的一个。

Broom from the second sample test can be built using language "piece", "of", "pie", "pretty", "prefix". Its simplification with p = 2 obtains the language of words "pece", "o", "pe", "petty", "pefix". This language gives us the broom with minimum possible size.

第二个样例测试中的扫帚（broom）可由单词“piece”、“of”、“pie”、“pretty”、“prefix”构成。当参数 $p = 2$ 时，对该语言进行简化，得到新语言：单词“pece”、“o”、“pe”、“petty”、“pefix”。该语言可构造出尺寸最小的扫帚。