public abstract class LevelGraph : IGraph<(int x, int y), AtomicReference<Direction>>, IDisjointSetUnion<(int x, int y)>
    {

        private readonly Dictionary<(int x, int y), AtomicReference<Direction>> nodes;
        private readonly Dictionary<(int x, int y), HashSet<(int x, int y)>> connections;

        private readonly Dictionary<(int x, int y), (int x, int y)> parents;

        public LevelGraph()
        {
            this.nodes = new();
            this.connections = new();

            this.parents = new();
        }

        protected virtual void Clear()
        {
            nodes.Clear();
            connections.Clear();

            parents.Clear();
        }

        // #################### IGraph ####################

        public bool AddNode((int x, int y) key, AtomicReference<Direction> node)
        {
            if (IsNode(key))
                return false;

            nodes[key] = node;
            connections[key] = new HashSet<(int x, int y)>();

            return true;
        }

        public bool AddConnection((int x, int y) key1, (int x, int y) key2)
        {
            if (!IsNode(key1) || !IsNode(key2))
                return false;

            if (IsConnectedDirectly(key1, key2))
                return false;

            connections[key1].Add(key2);
            connections[key2].Add(key1);

            return true;
        }


        public bool TryGetNode((int x, int y) key, out AtomicReference<Direction> node) => nodes.TryGetValue(key, out node);

        public bool IsNode((int x, int y) key) => TryGetNode(key, out var _);


        public bool IsConnectedDirectly((int x, int y) k1, (int x, int y) k2) => connections[k1].Contains(k2);

        public bool IsConnectedIndirectly((int x, int y) k1, (int x, int y) k2) => GraphDistance(k1, k2) != -1;


        public IEnumerable<(int x, int y)> GetConnectedNodes((int x, int y) key)
        {
            if (connections.TryGetValue(key, out var neighbors))
                return neighbors;

            return Enumerable.Empty<(int, int)>();
        }

        // #################### IDisjointSetUnion ####################

        public (int x, int y) GetRoot((int x, int y) key)
        {
            if (!parents.ContainsKey(key))
                parents[key] = key;

            if (!parents[key].Equals(key))
                parents[key] = GetRoot(parents[key]);

            return parents[key];
        }


        public bool IsUnioned((int x, int y) k1, (int x, int y) k2) => GetRoot(k1).Equals(GetRoot(k2));

        public void Union((int x, int y) k1, (int x, int y) k2)
        {
            var root1 = GetRoot(k1);
            var root2 = GetRoot(k2);

            if (!IsUnioned(root1, root2))
                parents[root2] = root1;
        }

        // #################### Extend IGraph ####################

        public bool AddConnection((int x, int y) key1, Direction direction)
        {
            if (!direction.IsValid())
                return false;

            (int x, int y) key2 = direction.Move(key1.x, key1.y);
            if (AddConnection(key1, key2))
            {
                nodes[key1].Value |= direction;
                nodes[key2].Value |= direction.Opposite();

                return true;
            }

            return false;
        }

        public int GraphDistance((int x, int y) k1, (int x, int y) k2)
        {
            if (!IsNode(k1) || !IsNode(k2))
                return -1;

            var visited = new HashSet<(int x, int y)>();

            var queue = new Queue<((int x, int y), int distance)>();
            queue.Enqueue((k1, 0));

            while (queue.Count > 0)
            {
                var (current, distance) = queue.Dequeue();
                if (current.Equals(k2))
                    return distance;

                if (!visited.Add(current))
                    continue;

                foreach (var neighbor in GetConnectedNodes(current))
                {
                    if (!visited.Contains(neighbor))
                        queue.Enqueue((neighbor, distance + 1));
                }
            }

            return -1;
        }

    }