#include <map>
#include <memory>

template<class Vertex>
class BfsVisitor {
 private:
    std::shared_ptr<std::map<Vertex, Vertex>> graph {nullptr};
 public:
    BfsVisitor() {
        graph.reset( new std::map<Vertex, Vertex>);
        (*graph)[-1] = 0;
    }

    void ExamineVertex(const Vertex& vertex) {
        (*graph)[-1] = vertex;
    }
    void DiscoverVertex(const Vertex& vertex) {
        (*graph)[vertex] = (*graph)[-1];
    }

    size_t DistanceTo(const Vertex& target) const {
        Vertex box = target;
        size_t length = 0;
        while (true) {
            if (box == 0 && (*graph).at(box) == 0) {
                return length;
            }
            box = (*graph).at(box);
            length++;
        }
    }
    Vertex Parent(const Vertex& vertex) const {
        return (*graph).at(vertex);
    }
};