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

我们定义由这种树产生的“字典”为：可以通过连接树中任意顶点（不一定是根节点）到叶子节点（不一定在叶子节点结束）的路径上的边所对应的字母而构成的所有单词的集合。

他们需要构建这样一棵树，使得其字典包含给定的单词集合作为其超集。在所有满足上述条件的树中，这棵树的顶点数必须最少。任何具有相同最少顶点数的树均可。你的任务是帮助他们完成这项工作。

例如，在上图所示的树中，以 1 为根，从 7 到 5 的路径读作 “north”，从 16 到 12 的路径读作 “eastern”，从 29 到 2 的路径读作 “european”，从 3 到 25 的路径读作 “regional”，从 1 到 31 的路径读作 “contest”。

输入格式

输入文件的第一行包含给定集合中单词的数量 $n$ ($1 \le n \le 50$)。接下来的 $n$ 行包含不同的非空单词，每行一个单词，由小写英文字母组成。每个单词的长度最多为 10 个字符。

输出格式

第一行输出树中的顶点数 $m$。接下来的 $m$ 行包含树顶点的描述，每行一个描述。顶点按照其描述行出现的顺序从 1 到 $m$ 进行编号。如果对应的顶点是树根，则其描述行应包含一个整数 0；否则，其描述行应包含其父节点的索引以及连接到父节点的边上的字母，中间用空格隔开。

样例

输入 1

5
north
eastern
european
regional
contest

输出 1

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

说明

该样例输出对应于题目描述中的图片。