中文题面：

描述

在自然语言文本中，字符的相对频率对于密码学来说非常重要。然而，不同语言的统计数字各不相同。以下是几种常见语言按相对频率排序的前$9$个字符：

英语: ETAOINSHR
德语: ENIRSATUD
法语: EAISTNRUL
西班牙语: EAOSNRILD
意大利语: EAIONLRTS
芬兰语: AITNESLOK

与单个字符的相对频率同样重要的是字符对（称为双字符）的相对频率。给定几个文本样本，计算具有最高相对频率的双字符。

输入：

输入包含多个测试用例。每个测试用例在一行中按照上述语法规则描述了一棵树。输入以文件结束符（$EOF$）结束。假设$1<=n<=50$。

输出：

对于每个测试用例，输出一行包含该树对应的$Prufer$编码。编码中的数字用单个空格分隔。行尾不要输出任何空格。

输入数据1

2
Take a look at this!!
!!siht ta kool a ekaT
5
P=NP
 Authors: A. Cookie, N. D. Fortune, L. Shalom
 Abstract: We give a PTAS algorithm for MaxSAT and apply the PCP-Theorem [3]
 Let F be a set of clauses. The following PTAS algorithm gives an optimal
 assignment for F:
0

输出数据1

a 3 0.073171
!! 3 0.073171
a  3 0.073171
 t 2 0.048780
oo 2 0.048780

 a 8 0.037209
or 7 0.032558
.  5 0.023256
e  5 0.023256
al 4 0.018605

来源

ACM国际大学生程序设计竞赛（ACM-ICPC） 德国乌尔姆大学分站赛