题目描述

Petr and Dmitry are working on a novel data compression scheme. Their task is to compress a given set of words. To compress a given set of words they have to build a rooted tree. Each edge of the tree is marked with exactly one letter.

Let us define a dictionary that is produced by this kind of tree as a set of words that can be constructed by concatenating letters on edges on any path from any vertex in the tree (not necessarily root) and going away from root down to the leaves (but not necessarily finishing on a leaf).

Boys have to construct such a tree with a dictionary that is a superset of the set of words that they are given to compress. This tree should have the smallest number of vertices between trees that satisfy the above condition. Any tree with the same number of vertices will do. Your task is to help them.

For example, in a tree on the picture above with the root marked as $1$ , a path from $7$ to $5$ reads north, a path from $16$ to $12$ reads eastern, a path from $29$ to $2$ reads european, a path from $3$ to $25$ reads regional, and a path from $1$ to $31$ reads contest.

输入格式

The first line of the input file contains the number of words in a given set $n (1 \le n \le 50)$ . The following $n$ lines contain different non-empty words, one word per line, consisting of lowercase English letters. The length of each word is at most $10$ characters.

输出格式

On the first line output the number of vertices in the tree $m$ . The following $m$ lines shall contain descriptions of tree vertices, one description per line. Vertices are indexed from $1$ to $n$ in the order of their corresponding description lines. If the corresponding vertex is a tree root, then its description line shall contain a single integer number $0$ , otherwise its description line shall contain an index of its parent node and a letter on the edge to its parent node, separated by a space.

题目大意

题目描述

Petr和Dmitry正在研究一种新的数据压缩方案。他们的任务是压缩一组给定的单词。为了压缩给定的一组单词，他们必须建立一个有根的树。这棵树的每一个边缘都有一个字母。

让我们定义一个由这种树生成的字典，它是一组单词，可以通过在树的任何顶点（不一定是根节点）的任何路径上的边上连接字母，从根向下到叶子（但不一定在叶节点上完成）来构造。

男孩们必须用字典来构造这样一棵树，字典是一组单词的超集，他们被给予压缩。满足上述条件的树之间的顶点数应该最小。任何具有相同顶点数的树都可以。你的任务是帮助他们。

例如，上图中的一棵树的根标记为1，从7到5的路径表示north，从16到12的路径表示eastern，从29到22的路径表示european，从3到25的路径表示regional，从1到31的路径表示contest。

输入格式

第一行是一个数字n（0<n<50） 接下来n行都是一个长度小于10的字符串

输出格式

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

5
north
eastern
european
regional
contest

31
0
7 n
2 o
18 t
4 h
29 e
17 a
7 s
8 t
9 e
10 r
11 n
6 u
13 r
14 o
15 p
16 e
3 r
18 e
19 g
20 i
21 o
22 n
23 a
24 l
1 c
26 o
27 n
28 t
6 s
30 t

提示

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