#include <iostream>

 #include <graph.h>

 #include <bfs.h>

 using namespace NEGRO;

 using namespace std;

 class IGraph 

 {

 public:

   //  struct NodeType {bfs_node_data<TestGraph> bfs;};

   struct NodeType {bool isVis;};

   vector<NodeType> nodes;

   class NodeIterator 

   {

   public:

     IGraph *G;

     int n;

     NodeIterator &operator ++() { n++; return *this;}

     NodeType &operator *() const { return G->nodes[n];}

     NodeType *operator ->() const { return &(G->nodes[n]);}

     bool isValid() const {return n<=5000;}

     int Index() {return n;} //csak a kiirashoz kell

     NodeIterator() {}

     NodeIterator(IGraph &Gr) {G=&Gr;n=1;} //Bfs class prefer this.

   };

   void GetFirst(NodeIterator &i) {i.G=this;i.n=1;}

   class OutEdgeIterator 

   {    

   public:

     IGraph *G;

     int f,t;

     int gcd() { int a=f;int b=t;int c;while((c=a%b)) {a=b;b=c;} ; return b;}

     OutEdgeIterator &operator ++() {while(++t<=5000&&gcd()==1);return *this;}

     bool isValid() const {return t<=5000;}

     NodeIterator From() const {NodeIterator i; i.G=G;i.n=f;return i;}

     NodeIterator To() const {NodeIterator i; i.G=G;i.n=t;return i;}

     NodeIterator Anode() const {return From();}

     NodeIterator Bnode() const {return To();}

     OutEdgeIterator() {}

     OutEdgeIterator(IGraph &Gr,NodeIterator &n)  //Bfs class prefer this.

     {G=&Gr;f=n.n;t=0;operator++();}

   };

   typedef OutEdgeIterator EdgeIterator;

   void GetFirst(OutEdgeIterator &i,const NodeIterator &n)

   {i.G=this;i.f=n.n;i.t=0;++i;}

   IGraph() : nodes(5001) {}

 };

 class IMaps_t

 {

 public:

 //     class_element_map<IGraph::NodeIterator,

 //   		    IGraph::NodeType,

 //   		    bool,

 //   		    &IGraph::NodeType::isVis> visited;

   struct _visited_map_t {

     typedef bool value_type;

     void Put(const IGraph::NodeIterator &n,const value_type &t) { n->isVis=t; }

     value_type Get(const IGraph::NodeIterator &n) const { return n->isVis; }

   } visited;

   struct _tree_map_t {

     typedef IGraph::EdgeIterator value_type;

     void Put(const IGraph::NodeIterator &n,const value_type &t)

     { cout << t.From().Index() << "->" << t.To().Index() << '\n'; }

   } tree;

   do_nothing_map dist;   //node->int (W)

   do_nothing_map priority; //node->int (W)

 };

 // New style bfs traits

 class BFS_T 

 {

 public:

   typedef IGraph Graph;

   typedef IGraph::OutEdgeIterator SearchEdgeIterator;

   struct visited_map_t {

     typedef bool value_type;

     void Put(const IGraph::NodeIterator &n,const value_type &t) { n->isVis=t; }

     value_type Get(const IGraph::NodeIterator &n) const { return n->isVis; }

   };

   struct tree_map_t {

     typedef IGraph::EdgeIterator value_type;

     void Put(const IGraph::NodeIterator &n,const value_type &t)

     { cout << t.From().Index() << "->" << t.To().Index() << '\n'; }

   };

   typedef do_nothing_map dist_map_t;   //node->int (W)

   typedef do_nothing_map priority_map_t; //node->int (W)

 };

 int main()

 {

   IGraph IG;

 //   //Function-syte calling

 //   IMaps_t IMaps;

 //   IGraph::NodeIterator in;

 //   IG.GetFirst(in);

 //   ++in;

 //   bfs_fn(IG,in,IMaps);  

   //Class-style calling:

   IGraph::NodeIterator in;

   IG.GetFirst(in);

   ++in;

   Bfs<BFS_T> bfs;

   bfs.SetG(IG);

   bfs.Init(in);

   bfs.Run();

 }