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