P6999 [NEERC 2013] Dictionary

Petr和Dmitry正在研究一种新的数据压缩方案。他们的任务是压缩一组给定的单词。为了压缩给定的一组单词，他们必须建立一个有根的树。这棵树的每一个边缘都有一个字母。 让我们定义一个由这种树生成的字典，它是一组单词，可以通过在树的任何顶点（不一定是根节点）的任何路径上的边上连接字母，从根向下到叶子（但不一定在叶节点上完成）来构造。 男孩们必须用字典来构造这样一棵树，字典是一组单词的超集，他们被给予压缩。满足上述条件的树之间的顶点数应该最小。任何具有相同顶点数的树都可以。你的任务是帮助他们。 例如，上图中的一棵树的根标记为1，从7到5的路径表示north，从16到12的路径表示eastern，从29到22的路径表示european，从3到25的路径表示regional，从1到31的路径表示contest。

第一行是一个数字n（0

在第一行输出树中的顶点数m。每行树应包含一行描述的顶点。顶点按其相应描述行的顺序从1索引到n。如果对应的顶点是树根，则其描述行应包含单个整数0，否则其描述行应包含其父节点的索引和父节点边缘上的字母，用空格隔开。

Time limit: 1 s, Memory limit: 128 MB.