#include <map>

template<typename Vertex>
class BfsVisitor {
 public:
    BfsVisitor() {
        dist = std::map<Vertex, int>();
        parent = std::map<Vertex, Vertex>();
        current_vert = (Vertex)(-1);
    }

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

    void DiscoverVertex(const Vertex &vertex) {
        if (current_vert == (Vertex)(-1)) {
            dist[vertex] = 0;
            parent[vertex] = vertex;
        } else {
            dist[vertex] = dist[current_vert] + 1;
            parent[vertex] = current_vert;
        }
    }

    size_t DistanceTo(const Vertex &target) const {
        return dist.at(target);
    }

    Vertex Parent(const Vertex &vertex) const {
        return parent.at(vertex);
    }

 private:
    static std::map<Vertex, int> dist;
    static std::map<Vertex, Vertex> parent;
    static Vertex current_vert;
};

template <typename T>
std::map<T, int> BfsVisitor<T>::dist = std::map<T, int>();

template <typename T>
std::map<T, T> BfsVisitor<T>::parent = std::map<T, T>();

template <typename T>
T BfsVisitor<T>::current_vert = T();