QOJ.ac

QOJ

Time Limit: 2 s Memory Limit: 256 MB Total points: 100

#21047. 家譜

Statistics

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 的姨母。

fig_familytree_bronze_open18.png

範例

輸入格式 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

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.