#include <map>
#include <memory>

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

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

    size_t DistanceTo(const Vertex& target) const {
        size_t dist = 0;
        Vertex p = target;
        while (true) {
            if (p == 0 && (*tree).at(p) == 0) {
                return dist;
            }
            dist++;
            p = (*tree).at(p);
        }
    }
    Vertex Parent(const Vertex& vertex) const {
        return (*tree).at(vertex);
    }

 private:
    std::shared_ptr<std::map<Vertex, Vertex>> tree {nullptr};
    // Vertex current_parent= 0;
};