유전자 복원

새로운 종을 연구하면서 수집한 자료가 올바른지 확인하려고 합니다.

생물이 여러 마리 있으며, 각 생물의 눈 색깔을 알고 있습니다. 눈 색깔은 "a"부터 "t"까지의 영어 소문자 중 하나로 주어집니다.

눈 색깔을 정하는 유전자가 하나 있다고 가정합니다. 각 생물은 대립유전자 두 개를 지니며, 대립유전자는 영어 소문자 한 글자입니다. 생물의 눈 색깔은 두 대립유전자 중 알파벳 순서가 앞선 것입니다.

각 생물의 부모 정보도 알고 있습니다. 부모는 두 명 모두 알려져 있거나 두 명 모두 알려져 있지 않습니다. 생물은 부모에게서 대립유전자를 하나씩 물려받으며, 가능한 조합은 네 가지 모두입니다. 예를 들어 대립유전자가 "ak"인 부모(눈 색깔 "a")와 "em"인 부모(눈 색깔 "e")의 자식은 대립유전자가 "ae"(눈 색깔 "a"), "am"(눈 색깔 "a"), "ek"(눈 색깔 "e"), "km"(눈 색깔 "k") 중 하나일 수 있습니다.

생물의 수, 부모 정보, 각 생물의 눈 색깔이 주어졌을 때, 이 자료가 위의 가정과 일치하는지 판단합니다.

첫째 줄에 생물의 수를 나타내는 정수 $n$ ($1 \le n \le 20$)이 주어집니다. 생물은 1번부터 $n$번까지 번호가 매겨져 있습니다.

이후 $n$개의 줄에는 각각 정수 두 개 $p_1$, $p_2$와 문자 하나 $c$가 주어집니다. $p_1$, $p_2$는 해당 생물의 부모 번호이며, $1 \le p_1, p_2 \le n$이고 $p_1 \ne p_2$입니다. 부모를 모르는 경우에는 $p_1 = p_2 = 0$입니다. $c$는 해당 생물의 눈 색깔이며 "a"부터 "t"까지 중 하나입니다.

부모는 두 명 모두 주어지거나 두 명 모두 주어지지 않습니다. 부모의 번호는 해당 생물의 번호보다 작습니다. 어떤 생물도 자신의 조상이나 자손이 될 수 없습니다.

정보가 모순되지 않으면, 각 생물의 대립유전자를 한 줄에 한 생물씩, 공백 없이 출력합니다. 해답이 여러 개이면 첫 번째 생물부터 차례로 비교했을 때 사전 순으로 가장 앞서는 해답을 출력합니다. 모순되면 -1을 출력합니다.