#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; }

    void SetG(IGraph &G) {}

  } 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'; }

    void SetG(IGraph &G) {}

  } 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; }

    void SetG(IGraph &G) {}

  };

  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'; }

    void SetG(IGraph &G) {}

  };

  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();

}