#include <iostream>

#include <graph.h>

#include <bfs.h>

using namespace NEGRO;

using namespace std;

typedef Graph<int,int> TestGraph;

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

int main()

{

  TestGraph G;

  TestGraph::NodeIterator tn,n2;

  for(int i=1;i<=5000;i++)

    {

      *(tn=G.AddNode())=i;

      if(i==2) n2=tn;

    }

  for(TestGraph::NodeIterator n(G);n.isValid();++n)

    for(TestGraph::NodeIterator m(G);m.isValid();++m)

      if(gcd(*n,*m)>1) G.AddEdge(n,m);

  Bfs<default_bfs_T<TestGraph> > bfs;

  bfs.SetG(G);

  bfs.Init(n2);

  bfs.Run();

  for(TestGraph::NodeIterator n(G);n.isValid();++n)

    cout << Get(bfs.tree_map,n).From() << "->" << Get(bfs.tree_map,n).To()

	 << '\n';

}