#include <map>
#include <memory>

template<class Vertex>
class BfsVisitor {
 public:
  BfsVisitor() {
    tree = std::make_shared<std::pair<Vertex, std::map<Vertex, Vertex>>>();
    tree->first = 0;
  }

  void ExamineVertex(const Vertex& vertex) {
    tree->first = vertex;
  }
  void DiscoverVertex(const Vertex& vertex) {
    tree->second[vertex] = tree->first;
  }

  size_t DistanceTo(const Vertex& target) const {
    size_t dist = 0;
    Vertex tmp = target;
    while (true) {
      if (tmp == 0 && tree->second.at(tmp) == 0) {
        return dist;
      }
      dist++;
      tmp = tree->second.at(tmp);
    }
  }
  Vertex Parent(const Vertex& vertex) const {
    return tree->second.at(vertex);
  }

 private:
  std::shared_ptr<std::pair<Vertex, std::map<Vertex, Vertex>>> tree {nullptr};
};