Determine Whether Two Horses Are Related (Pedigree Graph)

Problem: Determine Whether Two Horses Are Related (Pedigree/Ancestry) Given a set of pedigree relationships and two horses a and b, determine whether they are biologically related. Definition Each relationship encodes a directed ancestry relation: parent -> child. Two horses are considered related if any of the following holds: a is an ancestor of b, or b is an ancestor of a; or a and b share at least one common ancestor (i.e., their ancestor sets intersect). Input relations: a collection of pairs (parent, child). Two horse identifiers a and b (either strings or integers). You may choose any reasonable data structure to represent relations (edge list, adjacency map, tree structure, etc.). Output Return true/false indicating whether a and b are related. Constraints / Edge Cases Multiple parents may exist (e.g., a horse can have two parents), so the structure can be a DAG rather than a single tree. If a == b, return true. If a or b does not appear in the pedigree, you may treat it as not related and return false (confirm with interviewer). Examples relations = [(1,2),(1,3),(2,4)], a=4, b=3 -> true (common ancestor 1) relations = [(1,2),(3,4)], a=2, b=4 -> false Example Input 3 1 2 1 3 2 4 4 3 Output true