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

template <class Vertex>
class BfsVisitor {
 private:
class Vert {
 public:
  std::map<int, std::pair<int, int> Vert;
  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->Vert[vr].second + 1;
}

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

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

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