eolymp
bolt
Try our new interface for solving problems
Məsələlər

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

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

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

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

Первая строка содержит 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

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 128 MiB
Giriş verilənləri #1
7 AA BB
MOTHER AA
GGMOTHER BB
MOTHER SISTER
GMOTHER MOTHER
GMOTHER AUNT
AUNT COUSIN
GGMOTHER GMOTHER
Çıxış verilənləri #1
BB is the great-aunt of AA
Mənbə 2018 USACO US Open, Бронза