#include <iostream>
#include <map>

template <class Vertex>
class BfsVisitor {
private:
    bool b = true;
    Vertex current_vertex;
    std::map<Vertex, std::pair<size_t, Vertex>>* graph;

public:
    BfsVisitor() { graph = new std::map<Vertex, std::pair<size_t, Vertex>>; }

    void ExamineVertex(const Vertex& vertex) { current_vertex = vertex; }

    void DiscoverVertex(const Vertex& vertex) {
        if (b) {
            graph->insert({vertex, {0, vertex}});
            b = false;
            return;
        }

        size_t dist = graph->at(current_vertex).first + 1;
        graph->insert({vertex, {dist, current_vertex}});
    }

    size_t DistanceTo(const Vertex& vertex) { return graph->at(vertex).first; }

    Vertex Parent(const Vertex& vertex) { return graph->at(vertex).second; }
};