#include <utility>
#include <iostream>
#include <unordered_set>
#include <unordered_map>
#include <vector>
#include <queue>
#include <exception>
#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; }
};