Genetic Reconstruction

You are studying a new species and want to check that your collected data is correct.

There are several creatures. For each one, you know its eye color, written as one of the lowercase English letters from "a" to "t".

You suspect that a single gene controls eye color. Each creature has two alleles, and each allele is a lowercase English letter. The eye color is the allele that comes first alphabetically of the two.

You also know the parents of each creature. Either both parents are known or both are missing. A creature inherits one allele from each parent, and any of the four combinations is possible. For example, a parent with alleles "ak" (eye color "a") and another parent with alleles "em" (eye color "e") can have a child with alleles "ae" (eye color "a"), "am" (eye color "a"), "ek" (eye color "e"), or "km" (eye color "k").

Given the number of creatures, the parent information, and the eye color of each creature, determine whether the data is consistent with this hypothesis.

The first line contains a single integer $n$ ($1 \le n \le 20$), the number of creatures. The creatures are numbered from 1 to $n$.

Each of the next $n$ lines contains two integers $p_1$ and $p_2$ and a character $c$. Here $p_1$ and $p_2$ are the parents of the creature, with $1 \le p_1, p_2 \le n$ and $p_1 \ne p_2$, or $p_1 = p_2 = 0$ if the parents are unknown. The character $c$ is the eye color of the creature, one of "a" to "t".

Both parents are known or both are unknown. Each parent number is less than the number of the creature. No creature is its own ancestor or descendant.

If the information is consistent, print the alleles of each creature, one creature per line, with no spaces. If several solutions exist, print the alphabetically smallest one, compared creature by creature from the first to the last. Otherwise, print -1.