using System;

using System.Collections.Generic;

using System.Linq;

using System.Net.Sockets;

using System.Security.Policy;

using System.Text;

using System.Threading.Tasks;

​

namespace pr1

{

    class Person

    {

        public Name FullName { get; set; }

        public Address Address { get; set; }

    }

​

    class Name

    {

        public string FirstName { get; set; }

        public string LastName { get; set; }

    }

​

    public class Address {

        public string Street { get; set; }

        public string City { get; set; }

    }

​

    internal class Program

    {

        public void Init(Person[] persons)

        {

        }

​

        int FindMinRelation( Person pA, Person pB)

        {

            return -1;

        }

        static void Main(string[] args)

        {

            var people = new List<(string, string)>

        {

            ("John", "123 Fake st."),

            ("John", "456 Fake st."),

            ("Alice", "456 Fake st."),

            ("Bob", "789 Fake st."),

            ("Alice", "789 Fake st."),

            ("Alice2", "456 Fake st."),

            ("Alice3", "456 Fake st."),

        };

​

            var result = ShortestPath(people, ("John", "123 Fake st."), ("Bob", "789 Fake st."));

            Console.WriteLine(result);

        }

​

        public static int ShortestPath(List<(string, string)> people, (string, string) a, (string, string) b)

        {

            // build dictionaries in O(n) time

            var names = new Dictionary<string, List<(string, string)>>();

            var addresses = new Dictionary<string, List<(string, string)>>();

            foreach (var p in people)

            {

                var (p_name, p_address) = p;

​

                if (!names.ContainsKey(p_name))

                    names[p_name] = new List<(string, string)>();

                names[p_name].Add(p);

​

                if (!addresses.ContainsKey(p_address))

                    addresses[p_address] = new List<(string, string)>();

                addresses[p_address].Add(p);

            }

​

            // a has distance 0 to self

            var queue = new Queue<((string, string), int)>();

            queue.Enqueue((a, 0));

​

            var visited = new HashSet<(string, string)>();

            var namesUsed = new HashSet<string>();

            var addressesUsed = new HashSet<string>();

​

            // loop iterates O(n) times, because each person can only be polled

            // twice from the queue, except a, who can be polled three times

            while (queue.Count > 0)

            {

                var (p, distance) = queue.Dequeue();

                if (p.Equals(b)) return distance;

                if (visited.Contains(p)) continue;

                visited.Add(p);

​

                var (p_name, p_address) = p;

                if (!namesUsed.Contains(p_name))

                {

                    namesUsed.Add(p_name);

                    // each person can only be added to the queue once by name

                    foreach (var q in names[p_name])

                        queue.Enqueue((q, distance + 1));

                }

                if (!addressesUsed.Contains(p_address))

                {

                    addressesUsed.Add(p_address);

                    // each person can only be added to the queue once by address

                    foreach (var q in addresses[p_address])

                        queue.Enqueue((q, distance + 1));

                }

            }

​

            // b not found

            return -1;

        }

    }

}

​