#include <map>

template<Vertex>
  class BfsVisitor {
   public:
      void ExamineVertex(const Vertex& vertex) {
          current_vertex_ = vertex;
      }
      void DiscoverVertex(const Vertex& vertex) {
          if (!root_is_found_) {
              root_is_found_ = true;
              current_vertex_ = vertex;
          }
          parent_[vertex] = current_vertex_;
      }
      size_t DistanceTo(const Vertex& target) const {
          size_t counter = 0;
          Vertex current_target = target;
          while (true) {
              Vertex parent_of_target = parent_[current_target];
              if (parent_of_target == current_target) {
                  return counter;
              } else {
                  ++counter;
                  current_target = parent_of_target;
              }
          }
      }
      Vertex Parent(const Vertex& vertex) const {
          return parent_[vertex];
      }
   private:
      map<Vertex, Vertex> parent_;
      Vertex current_vertex_;
      bool root_is_found_ = false;
  }