Employee Hierarchy Relationship Determination

You are given a company organizational hierarchy represented as a set of direct reporting relationships and a target pair of employees. Each reporting relationship is given as a pair of strings (manager, subordinate). Given the target pair (employee1, employee2), determine the relationship of employee1 relative to employee2 according to the following definitions:

• Manager: employee1 is the immediate manager of employee2 (i.e. employee2 directly reports to employee1).
• Direct Report: employee1 directly reports to employee2.
• Indirect Report: employee1 reports to employee2 through one or more intermediate managers (chain length > 1).
• Colleague: employee1 and employee2 share the same immediate manager.
• None: if none of the above relationships hold.

The reporting relationships form a directed tree (or forest) structure. Use a breadth-first search (BFS) strategy to determine if a chain of command exists between two employees.

inputFormat

The input is read from standard input (stdin) and has the following format:

<number_of_relationships>
<manager1> <subordinate1>
<manager2> <subordinate2>
... (a total of number_of_relationships lines)
<employee1> <employee2>

Here, the first integer indicates the number of direct reporting relationships. Each of the next lines contains two strings separated by a space. The final line contains the target pair of employee names.

outputFormat

Output a single line to standard output (stdout) containing one of the following strings: Manager, Direct Report, Indirect Report, Colleague, or None, according to the relationship of the first employee to the second.

3
Alice Bob
Bob Charlie
Alice David
Bob Alice

Direct Report