Peterson Polyglot

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

Peterson makes a new language every morning. Storing a whole language is hard, so Peterson invented a data structure called a broom to store them. A broom is a rooted tree whose edges are marked with letters. Initially the broom is a single vertex, the root. To add a new word, Peterson starts at the root and processes the letters one by one. Suppose Peterson is at vertex $u$. If there is an edge from $u$ marked with the current letter, he follows that edge. Otherwise he adds a new edge from $u$ to a new vertex $v$, marks it with the current letter, and follows the new edge. The size of a broom is the number of its vertices.

In the evening, Peterson cannot understand the language he made that morning. It is too difficult, so he tries to simplify it. Simplifying a language means erasing some letters from some of its words. Formally, Peterson picks a positive integer $p$ and erases the $p$-th letter from every word whose length is at least $p$. Letters are indexed starting from 1. The simplification must change at least one word, so at least one word must have length at least $p$. Peterson wants the simplified language to have the smallest possible broom, so he chooses $p$ to minimize the size of the resulting broom.

Help Peterson find the smallest possible broom size and the integer $p$ to choose. If several values of $p$ give the minimum, print the smallest one.

The first line contains an integer $n$ ($2 \le n \le 3 \cdot 10^5$), the size of the broom. Each of the next $n - 1$ lines contains integers $u_i$, $v_i$ and a letter $x_i$, describing an edge from $u_i$ to $v_i$ marked with $x_i$. Vertices are numbered from 1 to $n$, and vertex 1 is the root. Every $x_i$ is a lowercase Latin letter. The edges describe a valid broom built from Peterson's language.

The first line contains the minimum possible size of the broom after simplification. The second line contains the integer $p$ to choose. If several suitable values of $p$ exist, print the smallest one.

Let the language consist of words $s_1, s_2, \ldots, s_m$. Let $S$ be the total length of the words, that is, $S = \sum_i |s_i|$. Let $L$ be the maximum word length, that is, $L = \max_i |s_i|$.

The broom for the language in the second test case can be built from the words "piece", "of", "pie", "pretty", and "prefix". Simplifying it with $p = 2$ gives the words "pece", "o", "pe", "petty", and "pefix". This language gives the broom with the smallest possible size.