## Description

Goal

Given a set of parents and children, determine how pairs of people are related, if at all.

Details

The input to the program consists of two parts. The first line consists of two integers ƒ and q, which

are the number of nuclear families and queries that follow. The next ƒ lines each describe one

nuclear family. These lines are of the form m ƒ ther mother chd1 chd2 . . . chdm, where m

is the number of children in the nuclear family and the remaining elements are names. The last q

lines are pairs of names.

A name is any sequence of non-space characters.

Some definitions for ascertaining relationships:

• p is a 0-descendent of q if p is a child of q.

• p is a k-descendent of q if p is a child of some person r and r is a (k − 1)-descendent of q.

• p is a 0-ancestor of q if p is a parent of q.

• p is a k-ancestor of q if p is a parent of some person r and r is a (k − 1)-ancestor of q.

If two people p and q are related, then they are related in one of the following manners:

• child

p is a child of q if p is a 0-descendent of q

• grandchild

p is a grandchild of q if p is a 1-descendent of q

• great great . . . great

| {z }

n times

grandchild

This is when p is an (n + 1)-descendent of q

• parent

p is a child of q if p is a 0-ancestor of q

• grandparent

p is a grandparent of q if p is a 1-ancestor of q

• great great . . . great

| {z }

n times

grandparent

This is when p is an (n + 1)-ancestor of q

Data Structures and Objects Project 4 — Family Trees Fall 2017 — CRN 42034

• cousins and siblings

Let r be the closest common ancestor to p and q; that is, no descendent of r is also an

ancestor of both p and q. Suppose that p is an m-descendent of r and q is an n-descendent

of r. Let s = mn(m, n) and let t = |m − n|. Then, p and q are s-cousins t times removed.

0

th-cousins zero times removed are siblings.

For each query p q, output one of the following lines as appropriate:

• child, grandchild, great great . . . great grandchild

If p is a descendent of q

• parent, grandparent, great great . . . great grandparent

If p is an ancestor of q

• sibling

If p and q are 0-cousins zero times removed

• m-cousin

If p and q are m-cousins zero times removed

• m-cousin removed n

If p and q are m-cousins n times removed

• No relation

If p and q are not related

.Limitations

For any query, there will be at most two closest common ancestors; these will be spouses of each

other.

There will be at most 500 unique names.

What to turn in

Turn in your source code and Makefile. If you use Code::Blocks, turn in a tarball of your project

directory.

2 of 3

Data Structures and Objects Project 4 — Family Trees Fall 2017 — CRN 42034

Example Input

13 6

2 bill wilma brenda deb

3 bob.1 diana bob.2 kelly angela

4 mac pearl lloyd bill barb bob.1

2 kelly glenn hilary ashlee

2 bob.2 betty tony nick

1 bob.3 barb bob.4

9 joe.1 nettie ron.1 joe.2 jim.1 bob.3 carol georgia charlie mary.ellen lynette

4 jim.1 mary.ann jim.2 michael bradley brian

3 michael kris max madison mckenna

3 jim.2 connie alex kerri zack

2 ron.1 jackie ron.2 jacob

2 joe.3 helen joe.1 katherine

3 jim.3 emma joe.3 jim.4 george

alex emma

joe.3 ron.2

nick kelly

georgia charlie

deb jacob

tony ashlee

Sample Output

great great great grandchild

great grandparent

0 cousin 1 removed

sibling

no relation

1 cousin