#include <cstddef>
#include <vector>
#include <map>
#include <utility>

template<class Vertex>
class BfsVisitor {
 public:
  void ExamineVertex(const Vertex &vertex) {
    current_vertex = vertex;
  }
  void DiscoverVertex(const Vertex &vertex) {
    if (current_vertex == -1) {
      parents->insert(std::make_pair(vertex, vertex));
      distance->insert(std::make_pair(vertex, 0));
    } else {
      parents->insert(std::make_pair(vertex, current_vertex));
      distance->insert(std::make_pair
      (vertex, distance->at(current_vertex) + 1));
    }
  }

  size_t DistanceTo(const Vertex &target) const {
    return distance->at(target);
  }
  Vertex Parent(const Vertex &vertex) const {
    return parents->at(vertex);
  }

 private:
  std::map<Vertex, int> *distance = new std::map<Vertex, int>;
  std::map<Vertex, Vertex> *parents = new std::map<Vertex, Vertex>;;
  Vertex current_vertex = -1;
};