#include <map>

using std::map;

template<typename Vertex>
class BfsVisitor {
 private:
  static bool first_vertex;
  static Vertex current_vertex;
  static map<Vertex, int> dist;
  static map<Vertex, Vertex> parent;

 public:
  BfsVisitor() {
    dist = map<Vertex, int>();
    parent = map<Vertex, Vertex>();
    first_vertex = true;
  }

  void ExamineVertex(const Vertex& vertex) {
    if (first_vertex) {
      first_vertex = false;
      dist[vertex] = 0;
      parent[vertex] = vertex;
      current_vertex = vertex;
      return;
    }
    current_vertex = vertex;
  }

  void DiscoverVertex(const Vertex& vertex) {
    dist[vertex] = dist[current_vertex]+1;
    parent[vertex] = current_vertex;
  }

  size_t DistanceTo(const Vertex& target) const {
    return dist.at(target);
  }
  Vertex Parent(const Vertex& vertex) const {
    return parent.at(vertex);
  }
};
template <typename T>
map<T, int> BfsVisitor<T>::dist = map<T, int>();

template <typename T>
map<T, T> BfsVisitor<T>::parent = map<T, T>();

template <typename T>
bool BfsVisitor<T>::first_vertex = true;

template <typename T>
T BfsVisitor<T>::current_vertex = T();