Cow Family Tree

Farmer John has inherited an ancient family farm where the dairy cows’ ancestry can be traced back through generations. Recently, he discovered old records and is now curious about the direct familial relations among his cows. Specifically, given a set of parent–child relationships, determine whether one cow is an ancestor of the other.

Formally, you are given N records, each containing two cow names: the first cow is the parent of the second. Then, a query containing two cow names is provided. If the first cow is an ancestor of the second, compute the number of generations d between them. If d = 1, output that the first cow is the parent of the second. If d = 2, output that the first cow is the grandparent of the second. For d \ge 3, output that the first cow is the \(great-\) repeated \((d-2)\) times followed by grandparent of the second cow. Similarly, if the second cow is an ancestor of the first, output the corresponding relationship. If neither cow is a direct ancestor of the other, output "NOT RELATED".

In mathematical notation, if cow A is an ancestor of cow B with a generational gap of d (i.e. there is a sequence A \(\rightarrow\) ... \(\rightarrow\) B with exactly d edges and A ≠ B), then:

\[ \text{Relationship}(d)=\begin{cases} \text{parent} & d=1,\\ \text{grandparent} & d=2,\\ \text{great-}\underbrace{\text{great-}\cdots\text{great-}}_{d-2\text{ times}}\text{grandparent} & d\ge3. \end{cases} \]

Your task is to print a statement of the form "X is the [relationship] of Y", where X is the ancestor and Y is the descendant, or "NOT RELATED" if there is no direct ancestry relationship.

inputFormat

The input begins with an integer N (1 ≤ N ≤ 1000), representing the number of parent–child records. Then follow N lines, each containing two strings separated by a space, where the first string is the name of a parent and the second is the name of their child. Finally, a single line contains two distinct cow names separated by a space representing the queried pair.

outputFormat

Output a single line. If one cow is a direct ancestor of the other, output a sentence of the form:

X is the [relationship] of Y

where the [relationship] is defined as above. Otherwise, output NOT RELATED.

sample

4
Martha Hilda
Hilda Gertrude
Gertrude Bessie
Elsie Mildred
Martha Bessie

Martha is the great-grandparent of Bessie