template<class Vertex>
class BfsVisitor {
 public:
    BfsVisitor() {
        p = new std::unordered_map<Vertex, Vertex>();
        v = NULL;
    }
    void ExamineVertex(const Vertex& vertex) {
        if (v == NULL) {
            v = new Vertex(vertex);
            return;
        }
        *v = vertex;
    }
    void DiscoverVertex(const Vertex& vertex) {
        if (v == NULL) {
            p->insert({ vertex, vertex });
            return;
        }
        p->insert({ vertex, *v });
    }
 
    size_t DistanceTo(const Vertex& target) const {
        size_t path = 0;
        for (Vertex i = target;  i != p->at(i); i = p->at(i))
            path++;
        return path;
    }
    Vertex Parent(const Vertex& vertex) const {
        return p->at(vertex);
    }
 
    ~BfsVisitor() {
        delete v;
        delete p;
    }
 
 private:
     Vertex* v;
     std::unordered_map<Vertex, Vertex>* p;
};