Farmer John 的家族農場已傳承數代,牛群的家族根源也可追溯到同一農場的數代之前。他查閱舊紀錄,想知道目前牛群中乳牛之間的親緣關係。請幫助他!
輸入格式
第一行包含 $N$($1 \leq N \leq 100$),隨後是兩頭乳牛的名字。名字是至多 $10$ 個大寫字母($A \ldots Z$)組成的字串。他想知道這一行兩頭乳牛的關係。
接下來 $N$ 行各包含兩個名字 $X$ 和 $Y$,表示 $X$ 是 $Y$ 的母親。
輸出格式
輸出一行,表示輸入第一行兩頭乳牛的關係(為方便起見,以下範例稱她們為 BESSIE 和 ELSIE)。可能的關係如下:
若 BESSIE 和 ELSIE 母親相同,輸出
SIBLINGS。BESSIE 可能是 ELSIE 的直系後代,即 ELSIE 是 BESSIE 的母親、祖母、曾祖母、高祖母等。此時輸出
ELSIE is the (relation) of BESSIE,其中 (relation) 是相應關係,如great-great-grand-mother。若 ELSIE 是 BESSIE 某位祖先的孩子(且 ELSIE 本身並非 BESSIE 的祖先或姊妹),則 ELSIE 是 BESSIE 的姨母。若她是 BESSIE 祖母的孩子,輸出
ELSIE is the aunt of BESSIE;若是曾祖母的孩子,輸出ELSIE is the great-aunt of BESSIE;若是高祖母的孩子,輸出ELSIE is the great-great-aunt of BESSIE,依此類推。若她們以其他方式有親緣關係(即有共同祖先),則為表親,直接輸出
COUSINS。若她們沒有共同祖先,或彼此都不是對方的直系後代,輸出
NOT RELATED。
下圖說明以上關係,這些是唯一需要考慮的類型。有些關係如「姪女」(姊妹的女兒)無需考慮,因為若 BESSIE 是 ELSIE 的姪女,則 ELSIE 是 BESSIE 的姨母。
範例
輸入格式 1
7 AA BB MOTHER AA GGMOTHER BB MOTHER SISTER GMOTHER MOTHER GMOTHER AUNT AUNT COUSIN GGMOTHER GMOTHER
輸出格式 1
BB is the great-aunt of AA
題目作者:Brian Dean