// -*- 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;

}