#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>> ver;
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->ver[vr].second + 1;
}

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

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

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