피터슨 폴리글롯

페테르손은 새로운 언어를 배우는 것을 좋아하지만, 가장 즐기는 취미는 새로운 언어를 만드는 것이다. 언어는 단어의 집합이고, 단어는 소문자 라틴 문자의 나열이다.

페테르손은 매일 아침 새로운 언어를 하나씩 만든다. 언어 전체를 저장하기는 어려워서, 그는 broom이라는 자료구조를 만들어 언어를 저장한다. broom은 간선에 문자가 표시된 루트 트리다. 처음에는 루트 정점 하나만 있다. 새 단어를 추가할 때 페테르손은 루트에서 출발해 글자를 하나씩 차례로 처리한다. 현재 정점이 $u$이고 $u$에서 현재 글자가 표시된 간선이 있으면 그 간선을 따라간다. 없으면 $u$에서 새 정점 $v$로 가는 간선을 만들어 현재 글자를 표시하고, 그 간선을 따라간다. broom의 크기는 정점의 개수다.

저녁이 되면 페테르손은 아침에 만든 언어를 이해하지 못한다. 너무 어려워서 그는 언어를 단순하게 만들려고 한다. 언어를 단순화한다는 것은 단어 일부에서 일부 글자를 지우는 것이다. 형식적으로 페테르손은 양의 정수 $p$를 고르고, 길이가 $p$ 이상인 모든 단어에서 $p$번째 글자를 지운다. 글자 번호는 1부터 시작한다. 단순화는 단어를 최소 하나 바꿔야 하므로, 길이가 $p$ 이상인 단어가 적어도 하나 있어야 한다. 페테르손은 단순화한 언어의 broom 크기가 가능한 한 작기를 원하므로, 크기가 최소가 되도록 $p$를 고른다.

페테르손을 도와 가능한 broom 크기의 최솟값과 고를 정수 $p$를 구하라. 최솟값을 주는 $p$가 여러 개라면 가장 작은 값을 출력한다.

첫째 줄에 broom의 크기인 정수 $n$ ($2 \le n \le 3 \cdot 10^5$)이 주어진다. 이어지는 $n - 1$개의 줄에는 각각 정수 $u_i$, $v_i$와 문자 $x_i$가 주어진다. 이는 $u_i$에서 $v_i$로 가는, 문자 $x_i$가 표시된 간선을 나타낸다. 정점은 1부터 $n$까지 번호가 매겨져 있고, 정점 1이 루트이다. 모든 $x_i$는 소문자 라틴 문자이다. 간선들은 페테르손의 언어로 만들어진 올바른 broom을 나타낸다.

첫째 줄에 단순화한 뒤 broom의 최소 크기를 출력한다. 둘째 줄에는 고른 정수 $p$를 출력한다. 적합한 $p$가 여러 개라면 가장 작은 값을 출력한다.

언어가 단어 $s_1, s_2, \ldots, s_m$으로 이루어져 있다고 하자. $S$를 단어 길이의 총합, 즉 $S = \sum_i |s_i|$라 하고, $L$을 최대 단어 길이, 즉 $L = \max_i |s_i|$라 하자.

두 번째 테스트 데이터의 언어는 "piece", "of", "pie", "pretty", "prefix" 단어로 broom을 만들 수 있다. 이 언어를 $p = 2$로 단순화하면 "pece", "o", "pe", "petty", "pefix"로 이루어진 언어가 되고, 이 언어가 가장 작은 크기의 broom을 준다.