2013年7月18日 星期四

939 - Genes

基因遺傳實驗室 (GEL) 研究許多遺傳疾病數年了,也收集大量疾病的資料,對於每個人可以得知道基因是否為顯性(dominant)、隱性(recessive)或者是不存在(non-existent),基於研究資料可以得知從父母的疾病是否會遺傳給他們的孩子。然而,檢查這些推論是乏味且繁瑣的, GEL 希望你寫個自動處理的程序給他們。

想法很簡單,你將會有父子關係,以及固定的推論,計算所有人的基因是否有這段基因,如果有的話,則決定是否為顯性還是隱性。如果推論有所錯誤的話,這將會給研究人員改善推論的線索,測資中不會存在解不出來或錯誤的推論。

給定父子關係,以及部分人的基因狀態,計算所有資料中的人的基因狀態。
推論的方式如下:
  • 孩子有這段基因  if and only if 父母皆有這段基因、或者父母其中一人有顯性基因。
  • 孩子的基因是顯性 if and only if 父母都是顯性基因、或者其中一個人是顯性另一個人是隱性。

Input

第一行將會有一個整數 N (1 <= N <= 3100),表示接下來會有多少行的描述。
接下來會有 N 行,每行上兩個非空字串,每個字串最多 20 個字元,且不會包含空字元。

第一個字串是這個人的名字,而第二個字串會是
  1. "non-existent", "recessive", "dominant" 或
  2. 他的孩子名字
第一種表示這個人的基因狀態,第二種則表示父子關係。

所有的人名都是獨特的,且不會有人的名字為 "non-existent", "recessive",  "dominant",對於每個人要不存在兩個父母,要不沒有父母。

Output

對於每組測資,輸出每個人的基因狀態,按照字典順序輸出。
第一個字串為人名,第二個字串為基因狀態,中間以一個空白隔開。

Sample Input


7
John dominant
Mary recessive
John Susan
Mary Susan
Peter non-existent
Susan Marta
Peter Marta

Sample Output


John dominant
Marta recessive
Mary recessive
Peter non-existent
Susan dominant

沒有留言:

張貼留言