#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; }
};