题目描述

你正在研究一个新物种，并希望验证收集到的信息是否正确。

有若干个生物。对于每个生物，你知道它的眼睛颜色。眼睛颜色用前 20 个小写英文字母之一表示，即 a 到 t。

你提出如下假设：存在一个控制眼睛颜色的基因，每个生物有两个等位基因。每个等位基因用一个小写英文字母表示。一个生物最终表现出的眼睛颜色，是它两个等位基因中字典序较小的那个。

此外，你还知道每个生物的两个父母。某些生物的父母信息可能缺失；若缺失则两个父母都未知，否则两个父母都已知。一个生物会从每个父母处各继承一个等位基因，四种组合都有可能。

例如，一个父母的等位基因为 ak，另一个父母的等位基因为 em，则孩子可能得到：

• ae，眼睛颜色为 a；
• am，眼睛颜色为 a；
• ek，眼睛颜色为 e；
• km，眼睛颜色为 k。

给出所有生物的父母信息和眼睛颜色，请判断这些信息是否与上述假设一致。如果一致，还需要输出字典序最小的一组等位基因方案。

字典序比较按生物编号从小到大依次比较每个生物的等位基因字符串。

输入格式

第一行包含一个整数 $n$，表示生物数量。

生物编号为 $1,2,\ldots,n$。

接下来 $n$ 行，第 $i$ 行包含两个整数 $p_1,p_2$ 和一个字符 $c$。

• 若 $p_1=p_2=0$，表示第 $i$ 个生物父母未知；
• 否则 $1 \le p_1,p_2 \le n$，且 $p_1\ne p_2$，表示两个父母编号；
• 字符 $c\in\{\texttt{a},\ldots,\texttt{t}\}$，表示该生物的眼睛颜色。

保证若父母已知，则两个父母的编号都小于当前生物编号，因此不会出现祖先环。

输出格式

如果信息一致，输出 $n$ 行，第 $i$ 行输出第 $i$ 个生物的两个等位基因，中间不加空格。

如果有多种可行方案，只输出字典序最小的一种。

如果信息不一致，输出：

-1

样例 #1

输入 #1

3
0 0 a
0 0 b
1 2 c

输出 #1

ac
bc
cc

样例 #2

输入 #2

3
0 0 c
0 0 c
2 1 a

输出 #2

-1