#include <unordered_map>
#include <iostream>
#include <unordered_set>
#include <vector>
#include <queue>
#include <exception>
#include <map>
#include <memory>
#include <utility>

template <class Vertex>
class BfsVisitor {
 private:
  class Vert {
   public:
    std::map < int, std::pair < int, int >> vertex;
    int a;
    int b = 0;
  };
  std::shared_ptr<Vert> vrt;

 public:
  BfsVisitor() {
  vrt = std::make_shared<Vert>();
  vrt->a = 0;
  vrt->b = 0;
  }

  void ExamineVertex(const Vertex &vr) {
    vrt->a = vr;
    vrt->b = vrt->vertex[vr].second + 1;
  }

  void DiscoverVertex(const Vertex &vr) {
    if (vr == 0) {
      vrt->vertex.insert(std::make_pair(0,
      std::make_pair(0, 0)));
    } else if (vrt->vertex.find(vr) != vrt->vertex.end()) {
        if (vrt->b < vrt->vertex[vr].second) {
        vrt->vertex[vr].first = vrt->a;
        vrt->vertex[vr].second = vrt->b;
        }
    } else {
      vrt->vertex.insert(std::make_pair(vr, std::make_pair(vrt->a,
      vrt->b)));
    }
  }

  size_t DistanceTo(const Vertex &trg) const {
    return vrt->vertex[trg].second;
  }

  Vertex Parent(const Vertex &vr) const {
      return vrt->vertex[vr].first;
  }
};