using System;

using System.Collections.Generic;

public class Program

{

    public class Node

    {

        IList<Node> Children;

        Node Mother;

        Node Father;

        int Value;

        public Node(int val, Node mother, Node father)

        {

            Value = val;

            Children = new List<Node>();

            Mother = mother;

            Father = father;

        }

        public void HaveABaby(Node n, Node father)

        {

            Children.Add(n);

            n.Mother = this;

            n.Father = father;

        }

        public bool IsRelated(Node n)

        {

            return IsRelated(n, new Dictionary<Node, int>());

        }

        public bool IsRelated(Node n, Dictionary<Node, int> map)

        {

            if(n == null || map.ContainsKey(this)) return false;

            if(n.Value == Value) return true;

            map[this] = 0;

            foreach(Node current in Children)

            {

                if(current.IsRelated(n, map)) 

                    return true;

                map[current] = 0;

            }

            return (Mother != null && Mother.IsRelated(n, map)) || (Father != null && Father.IsRelated(n, map));

        }

        public bool IsRelated_Better(Node n)

        {

            if(n == null) return false;

            if(n == this) return true;

            // Keep a list of visited nodes (track each (sub)tree separately

            Dictionary<Node, int> map1 = new Dictionary<Node, int>();

            Dictionary<Node, int> map2 = new Dictionary<Node, int>();

            // Breadth-first search, so use two queues for the two concurrent searches

            Queue<Node> queue1 = new Queue<Node>();

            Queue<Node> queue2 = new Queue<Node>();

            // Start by adding ourself and the target node

            queue1.Enqueue(this);

            queue2.Enqueue(n);

            // Simultaneously search from this node and n to find a common ancestor, if any

            Node current1 = null, current2 = null;

            current1 = queue1.Dequeue();

            current2 = queue2.Dequeue();

            while(current1 != null || current2 != null)

            {

                if(current1 != null)

                {

                    if(map2.ContainsKey(current1)) return true;

                    if(current1.Mother != null) queue1.Enqueue(current1.Mother);

                    if(current1.Father != null) queue1.Enqueue(current1.Father);            

​

                    map1[current1] = 0;

                    try { current1 = queue1.Dequeue(); } catch { current1 = null; }

                }                   

                if(current2 != null)

                {

                    if(map1.ContainsKey(current2)) return true;                 

                    if(current2.Mother != null) queue2.Enqueue(current2.Mother);

                    if(current2.Father != null) queue2.Enqueue(current2.Father);            

                    map2[current2] = 0;

                    try { current2 = queue2.Dequeue(); } catch { current2 = null; }

                }

            }

            return false;

        }

    }

    //           0            6

    //         /   \         / \

    //        1     2       7   8

    //       / \   / 

    //      3   4 5

    //

    //

    public static void Main()

    {

        List<Node> nodes = new List<Node>();

        for(int i = 0; i < 10; i++) nodes.Add(new Node(i, null, null));

        nodes[0].HaveABaby(nodes[1], null);

        nodes[0].HaveABaby(nodes[2], null);

        nodes[1].HaveABaby(nodes[3], null);

        nodes[1].HaveABaby(nodes[4], null);

        nodes[2].HaveABaby(nodes[5], null);

        nodes[6].HaveABaby(nodes[7], null);

        nodes[6].HaveABaby(nodes[8], null);

        // Everything in the first tree is related, forwards and backwards

        for(int j = 0; j <=5; j++)

        {

            for(int k = 0; k <= 5; k++)

            {

                Console.WriteLine(nodes[j].IsRelated(nodes[k]) ? "Pass" : "Fail");

                Console.WriteLine(nodes[j].IsRelated_Better(nodes[k]) ? "Pass" : "Fail");

            }

        }

        // First tree not related to second tree

        for(int j = 0; j <=5; j++)

        {

            for(int k = 6; k <= 8; k++)

            {

                Console.WriteLine(nodes[j].IsRelated(nodes[k]) ? "Fail" : "Pass");

                Console.WriteLine(nodes[j].IsRelated_Better(nodes[k]) ? "Fail" : "Pass");

            }

        }

        // Second tree related to all others in second tree

        for(int j = 6; j <=8; j++)

        {

            for(int k = 6; k <= 8; k++)

            {

                Console.WriteLine(nodes[j].IsRelated(nodes[k]) ? "Pass" : "Fail");

                Console.WriteLine(nodes[j].IsRelated_Better(nodes[k]) ? "Pass" : "Fail");

            }

        }

    }

}