eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Семейное дерево

Семейное дерево

Фермер Джон имеет стадо из нескольких поколений коров. Анализируя записи ФД хочет установить, в каком родстве коровы находятся друг к другу. Помогите ему.

Входные данные

Первая строка содержит n (1n100) за которым следуют имена двух коров. имена - строки не более чем из 10 символов (больших латинских букв - A..Z). ФД интересуется родством этих двух коров.

Каждая из следующих n строк содержит имена двух коров X и Y, означающих, что корова X - мама коровы Y.

Выходные данныеn

Выведите одну строку, указывающую родство между двумя коровами, указанными в первой входной строке. Для простоты назовём их сейчас Беси и Эльза - для последующих примеров. Возможны следующие типы родства:

  • Вы должны вывести "SIBLINGS" если Беси и Эльза имеют одну и ту же маму.

  • Беси может быть прямой наследницей Эльзы, тогда Эльза может быть mother, grand-mother, great-grand-mother, great-great-grand-mother, и так далее для Беси. В этом случае вы должны вывести: "ELSIE is the (родство) of BESSIE", где (родство) например "great-great-grand-mother".

  • Если Эльза не предшественница или сестра Беси, но она ребёнок предшественницы Беси, тогда Эльза является тётей для Беси. Вы должны вывести "ELSIE is the aunt of BESSIE" если Эльзя - ребёнок для grand-mother Беси, "ELSIE is the great-aunt of BESSIE" если эльза ребёнок great-grand-mother Беси, "ELSIE is the great-great-aunt of BESSIE" если Эльза ребёнок great-great-grand-mother Беси и так далее.

  • Если Беси и Эльза состоят в других родственных отношениях, например, если у них есть общий предшественник, то они кузины и Вы должны вывести "COUSINS".

  • Вы должны вывести "NOT RELATED", если у Беси и Эльзы нет общего предка и никто не является наследником друг друга.

Следующая диаграмма помогает иллюстрировать отношения, описанные выше. Заметим, что некоторые из них Вы не рассматриваете, например "niece" (дочь сестры), поскольку если Беси "niece" для Эльзы, то Эльза "aunt" для Беси.

prb10383.gif

Ліміт часу 1 секунда
Ліміт використання пам'яті 128 MiB
Вхідні дані #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
Джерело 2018 USACO US Open, Бронза