Bác nông dân John sở hữu một trang trại gia đình được truyền lại qua nhiều thế hệ, cùng một đàn bò có nguồn gốc gia đình cũng có thể được truy ngược qua nhiều thế hệ trên chính trang trại ấy. Khi xem lại các hồ sơ cũ, ông tò mò muốn biết những cô bò trong đàn hiện tại có quan hệ với nhau như thế nào. Hãy giúp ông thực hiện việc này!

Dữ liệu vào

Dòng đầu tiên của dữ liệu vào chứa \(N\) (\(1 \leq N \leq 100\)), theo sau là tên của hai cô bò. Mỗi tên bò là một xâu gồm không quá 10 chữ cái in hoa (\(A \ldots Z\)). Bác nông dân John muốn biết mối quan hệ giữa hai cô bò trên dòng này.

Mỗi dòng trong \(N\) dòng tiếp theo chứa hai tên bò \(X\) và \(Y\), cho biết \(X\) là mẹ của \(Y\).

Dữ liệu ra

In ra một dòng cho biết mối quan hệ giữa hai cô bò được nêu trên dòng đầu tiên của dữ liệu vào. Để đơn giản, trong các trường hợp dưới đây ta gọi hai cô bò này là BESSIE và ELSIE. Các kiểu quan hệ có thể có là:

• In SIBLINGS nếu BESSIE và ELSIE có cùng mẹ.
• BESSIE có thể là hậu duệ trực hệ của ELSIE, nghĩa là ELSIE là mẹ, bà, cụ, kỵ, v.v. của BESSIE. Trong trường hợp này, in ELSIE is the (relation) of BESSIE, trong đó (relation) là quan hệ thích hợp, chẳng hạn great-great-grand-mother.
• Nếu ELSIE là con của một tổ tiên của BESSIE, đồng thời bản thân ELSIE không phải là tổ tiên hoặc chị em của BESSIE, thì ELSIE là cô/dì của BESSIE. In ELSIE is the aunt of BESSIE nếu ELSIE là con của bà của BESSIE, ELSIE is the great-aunt of BESSIE nếu ELSIE là con của cụ của BESSIE, ELSIE is the great-great-aunt of BESSIE nếu ELSIE là con của kỵ của BESSIE, và cứ tiếp tục như vậy.
• Nếu BESSIE và ELSIE có quan hệ theo bất kỳ cách nào khác (tức là họ có chung một tổ tiên), họ là chị em họ và bạn chỉ cần in COUSINS.
• In NOT RELATED nếu BESSIE và ELSIE không có tổ tiên chung, hoặc không cô nào là hậu duệ trực hệ của cô còn lại.

Sơ đồ sau minh họa các mối quan hệ nêu trên; đây là những kiểu quan hệ duy nhất cần xét. Lưu ý rằng một số quan hệ như “cháu gái” (con gái của chị/em gái) là không cần thiết, bởi nếu BESSIE là cháu gái của ELSIE thì ELSIE là cô/dì của BESSIE.

Ví dụ

7 AA BB
MOTHER AA
GGMOTHER BB
MOTHER SISTER
GMOTHER MOTHER
GMOTHER AUNT
AUNT COUSIN
GGMOTHER GMOTHER

BB is the great-aunt of AA

Nguồn

USACO 2018 US Open Contest, Bronze — Family Tree

Tác giả bài toán: Brian Dean.