#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))); 
      } 
} //fa

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

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