public class Solution
    {

        private int VisitNode(Queue<Payload> q,
            Dictionary<string, Node> nodes,
            Dictionary<string, int> visited,
            Dictionary<string, int> otherVisited)
        {
            var payload = q.Dequeue();
            foreach(var p in nodes[payload.Word].Relationship)
            {
                if (otherVisited.ContainsKey(p))
                {
                    return payload.Depth + otherVisited[p];
                }
                if (!visited.ContainsKey(p))
                {
                    q.Enqueue(payload.Clone(p));
                }
                visited[p] = payload.Depth + 1;
            }
            return -1;
        }
        public int LadderLength(string beginWord, string endWord, IList<string> wordList)
        {
            Dictionary<string, Node> nodes = new Dictionary<string, Node>();
            wordList.Add(beginWord);
            // Create a graph
            foreach(var current in wordList)
            {
                Node currentNode = null;
                if (!nodes.ContainsKey(current))
                {
                    currentNode = new Node(current);
                    nodes.Add(current, currentNode);
                } else
                {
                    currentNode = nodes[current];
                }

                foreach(var candidate in wordList)
                {
                    if (IsTransformable(current, candidate))
                    {
                        currentNode.Add(candidate);
                    }
                }
            }

            if (!nodes.ContainsKey(endWord)) return 0;

            // Traverse with BFS
            Queue<Payload> sq = new Queue<Payload>();
            sq.Enqueue(new Payload
            {
                Depth = 1,
                Word = beginWord
            });
            Queue<Payload> eq = new Queue<Payload>();
            eq.Enqueue(new Payload
            {
                Depth = 1,
                Word = endWord
            });

            Dictionary<string, int> startVisited = new Dictionary<string, int>();
            Dictionary<string, int> endVisited = new Dictionary<string, int>();
            startVisited[beginWord] = 1;
            endVisited[endWord] = 1;

            while(sq.Count != 0 && eq.Count != 0)
            {
                // Start queue
                int ans = VisitNode(sq, nodes, startVisited, endVisited);
                if (ans > -1)
                {
                    return ans;
                }

                // End queue
                ans = VisitNode(eq, nodes, endVisited, startVisited);
                if (ans > -1)
                {
                    return ans;
                }
            }
            // Once you found the target it is the shortest depth.
            return 0;
        }

        internal static bool IsTransformable(string a, string b)
        {
            int counter = 0;
            for (int i = 0; i < a.Length; i++)
            {
                if (a[i] == b[i]) counter++;
            }
            return ((a.Length - counter) == 1);
        }
    }

    public class Payload
    {
        string _word;
        public string Word
        { get; set; }
        public int Depth { get; set; }

        public Payload Clone(string word)
        {
            var payload = new Payload();
            payload.Word = word;
            payload.Depth = this.Depth + 1;
            return payload;
        }
    }

    public class Node
    {
        private HashSet<string> _relationship = new HashSet<string>();
        public string Value { get; set; }

        public Node(string value)
        {
            Value = value;
        }

        public void Add(string relation)
        {
            _relationship.Add(relation);
        }

        public HashSet<string> Relationship => _relationship;

    }