// -*- c++ -*-
#include <iostream>
#include <fstream>

#include <sage_graph.h>
//#include <smart_graph.h>
#include <lemon/dimacs.h>
#include <lemon/time_measure.h>
#include <lemon/for_each_macros.h>
#include <bfs_dfs.h>

using namespace lemon;

int main() {
  typedef SageGraph Graph; 
  typedef Graph::Node Node;
  typedef Graph::NodeIt NodeIt;
  typedef Graph::Edge Edge;
  typedef Graph::EdgeIt EdgeIt;
  typedef Graph::OutEdgeIt OutEdgeIt;

  Graph g;
  Node s, t;
  Graph::EdgeMap<int> cap(g);
  //readDimacsMaxFlow(std::cin, g, s, t, cap);
  readDimacs(std::cin, g);

  Graph::NodeMap<OutEdgeIt> pred(g);

  Timer ts;
  /*
  {
    ts.reset();
    Graph::NodeMap<bool> reached(g);
    reached.set(s, true);
    pred.set(s, INVALID);
    std::queue<Node> bfs_queue;
    bfs_queue.push(t);
    while (!bfs_queue.empty()) {
      Node v=bfs_queue.front();	
      bfs_queue.pop();
      OutEdgeIt e;
      for(g.first(e,v); g.valid(e); g.next(e)) {
	Node w=g.target(e);
	if (!reached[w]) {
	  bfs_queue.push(w);
	  reached.set(w, true);
	  pred.set(w, e);
	}
      }
    }

    std::cout << ts << std::endl;
  }
  */

  {
    ts.reset();
    Graph::NodeMap<bool> bfs_reached(g);
    Graph::NodeMap<Edge> bfs_pred(g); 
    Graph::NodeMap<int> bfs_dist(g);
      
    Bfs< Graph, Graph::NodeMap<bool>, 
      Graph::NodeMap<Edge>, Graph::NodeMap<int> > 
      bfs(g,bfs_reached, bfs_pred, bfs_dist );
    bfs.run(s);
    /*
    pred.set(s, INVALID);
    while (!bfs.finished()) { 
      ++bfs; 
      if (g.valid(bfs) && bfs.isBNodeNewlyReached()) 
	pred.set(bfs.bNode(), bfs);
    }
    */
    std::cout << ts << std::endl;
  }

  return 0;
}