There are several creatures. For each one, you know the eye color they have. This is denoted by one of the first $20$ English lowercase letters (from ‘a’ to ‘t’).
You think that there is a gene that controls eye color. Your hypothesis is that each creature has two Alleles. An allele is represented by a lowercase English letter. The resulting eye color of the creature is the allele of the two which comes first alphabetically.
In addition, you’ve identified two parents of each creature. Some parents’ information may be missing; either both parents’ information will be available or both will be missing. A creature inherits one allele from each parent; any of the four combinations is possible. For example, one parent with alleles ‘ak’ (thus eye color ‘a’), and another with alleles ‘em’ (eye color ‘e’), might 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 if this information is consistent with your hypothesis.
The first line of input contains a single integer $n$ ($1 \le n \le 20$), which is the number of creatures in your study. The creatures are numbered from $1$ to $n$.
Each of the next $n$ lines contains two integers $p_1$, $p_2$ ($(1 \le p_1,p_2 \le n, p_1 \ne p_2$) or $p_1=p_2=0$ ) and a character $c$ ($c \in \{ $‘a’$,\ \dotsc \ ,$‘t’$\} $), where $p_1$ and $p_2$ represent the parents of the given creature (or are both $0$ if the parents are unknown), and $c$ is the given creature’s eye color. Note that either both parents will be known or both will be unknown, and that both parents’ numbers will be less than the number of the given creature; no creature can be its own ancestor or descendant.
If the information is consistent, output the alleles for each creature one per line, with no spaces; otherwise output $-1$. If there are multiple possible solutions, output only the one that comes first alphabetically (e.g., the alphabetically first allele pair for first creature, then second, and so on).
| Sample Input 1 | Sample Output 1 |
|---|---|
3 0 0 a 0 0 b 1 2 c |
ac bc cc |
| Sample Input 2 | Sample Output 2 |
|---|---|
3 0 0 c 0 0 c 2 1 a |
-1 |