#include <list>

 #include <iterator>

 	  //resG->flow[sym]+=a;

 	  //resG->flow[sym]-=a;

 	return *this; 

       }

     };

     void getFirst(OutEdgeIt& e, NodeIt v) const { 

       e=OutEdgeIt(*this, v); 

     }

     void getFirst(EachNodeIt& v) const { G.getFirst(v); }

     template< typename It >

     It first() const { 

       It e;      

       getFirst(e);

       return e; 

     }

     template< typename It >

     It first(NodeIt v) const { 

       It e;

       getFirst(e, v);

       return e; 

     }

     NodeIt tail(EdgeIt e) const { return G.aNode(e.sym); }

     NodeIt head(EdgeIt e) const { return G.bNode(e.sym); }

     NodeIt aNode(OutEdgeIt e) const { return G.aNode(e.sym); }

     NodeIt bNode(OutEdgeIt e) const { return G.bNode(e.sym); }

     int id(NodeIt v) const { return G.id(v); }

     template <typename S>

     class NodeMap {

       typename Graph::NodeMap<S> node_map; 

     public:

       NodeMap(const ResGraph<Graph, Number, FlowMap, CapacityMap>& _G) : node_map(_G.G) { }

       NodeMap(const ResGraph<Graph, Number, FlowMap, CapacityMap>& _G, S a) : node_map(_G.G, a) { }

       void set(NodeIt nit, S a) { node_map.set(nit, a); }

       S get(NodeIt nit) const { return node_map.get(nit); }

       S& operator[](NodeIt nit) { return node_map[nit]; } 

       const S& operator[](NodeIt nit) const { return node_map[nit]; } 

     };

   };

   template<typename Graph, typename Number, typename FlowMap, typename CapacityMap>

   class ResGraph2 {

     typedef typename Graph::NodeIt NodeIt;

     typedef typename Graph::EachNodeIt EachNodeIt;

     //typedef typename Graph::SymEdgeIt OldSymEdgeIt;

     typedef typename Graph::OutEdgeIt OldOutEdgeIt;

     typedef typename Graph::InEdgeIt OldInEdgeIt;

     const Graph& G;

     FlowMap& flow;

     const CapacityMap& capacity;

   public:

     ResGraph2(const Graph& _G, FlowMap& _flow, 

 	     const CapacityMap& _capacity) : 

       G(_G), flow(_flow), capacity(_capacity) { }

     class EdgeIt; 

     class OutEdgeIt; 

     friend class EdgeIt; 

     friend class OutEdgeIt; 

     class EdgeIt {

       friend class ResGraph2<Graph, Number, FlowMap, CapacityMap>;

     protected:

       const ResGraph2<Graph, Number, FlowMap, CapacityMap>* resG;

       //OldSymEdgeIt sym;

       OldOutEdgeIt out;

       OldInEdgeIt in;

       bool out_or_in; //1, iff out

     public:

       EdgeIt() : out_or_in(1) { } 

       Number free() const { 

 	if (out_or_in) { 

 	  return (resG->capacity.get(out)-resG->flow.get(out)); 

 	} else { 

 	  return (resG->flow.get(in)); 

 	}

       }

       bool valid() const { 

 	return out_or_in && out.valid() || in.valid(); }

       void augment(Number a) const {

 	if (out_or_in) { 

 	  resG->flow.set(out, resG->flow.get(out)+a);

 	} else { 

 	  resG->flow.set(in, resG->flow.get(in)-a);

 	}

       }

     };

     class OutEdgeIt : public EdgeIt {

       friend class ResGraph2<Graph, Number, FlowMap, CapacityMap>;

     public:

       OutEdgeIt() { }

     private:

       OutEdgeIt(const ResGraph2<Graph, Number, FlowMap, CapacityMap>& _resG, NodeIt v) { 

       	resG=&_resG;

 	out=resG->G.template first<OldOutEdgeIt>(v);

 	while( out.valid() && !(free()>0) ) { ++out; }

 	if (!out.valid()) {

 	  out_or_in=0;

 	  in=resG->G.template first<OldInEdgeIt>(v);

 	  while( in.valid() && !(free()>0) ) { ++in; }

 	}

       }

     public:

       OutEdgeIt& operator++() { 

 	if (out_or_in) {

 	  NodeIt v=resG->G.aNode(out);

 	  ++out;

 	  while( out.valid() && !(free()>0) ) { ++out; }

 	  if (!out.valid()) {

 	    out_or_in=0;

 	    in=resG->G.template first<OldInEdgeIt>(v);

 	    while( in.valid() && !(free()>0) ) { ++in; }

 	  }

 	} else {

 	  ++in;

 	  while( in.valid() && !(free()>0) ) { ++in; } 

 	}

     //AugGraph res_graph;    

     //typedef typename AugGraph::NodeMap<bool> ReachedMap;

     //typename AugGraph::NodeMap<AugEdgeIt> pred; 

     //typename AugGraph::NodeMap<int> free;

 /*

   template <typename Graph>

   class IteratorBoolNodeMap {

     typedef typename Graph::NodeIt NodeIt;

     typedef typename Graph::EachNodeIt EachNodeIt;

     class BoolItem {

     public:

       bool value;

       NodeIt prev;

       NodeIt next;

       BoolItem() : value(false), prev(), next() {}

     };

     NodeIt first_true;

     //NodeIt last_true;

     NodeIt first_false;

     //NodeIt last_false;

     const Graph& G; 

     typename Graph::NodeMap<BoolItem> container;

   public:

     typedef bool ValueType;

     typedef NodeIt KeyType;

     IteratorBoolNodeMap(const Graph& _G) : G(_G), container(G), first_true(NodeIt()) { 

       //for (EachNodeIt e=G.template first<EacNodeIt>(); e.valid(); ++e) {

       //BoolItem b=container.get(e);

       //b.me=e;

       //container.set(b);

       //} 

       G.getFirst(first_false);

       NodeIt e_prev;

       for (EachNodeIt e=G.template first<EacNodeIt>(); e.valid(); ++e) {

 	container[e].prev=e_prev;

 	if (e_prev.valid()) container[e_prev].next=e;

 	e_prev=e;

       }

     }

     //NodeMap(const Graph& _G, T a) : 

     //  G(_G), container(G.node_id, a) { }

     //FIXME

     void set(NodeIt nit, T a) { container[G.id(nit)]=a; }

     T get(NodeIt nit) const { return container[G.id(nit)]; }

     //void resize() { container.resize(G.node_id); }

     //void resize(T a) { container.resize(G.node_id, a); }

   };

 */

   template <typename Graph, typename Number, typename FlowMap, typename CapacityMap>

   class MaxFlow2 {

     typedef typename Graph::NodeIt NodeIt;

     typedef typename Graph::EdgeIt EdgeIt;

     typedef typename Graph::EachEdgeIt EachEdgeIt;

     typedef typename Graph::OutEdgeIt OutEdgeIt;

     typedef typename Graph::InEdgeIt InEdgeIt;

     const Graph& G;

     std::list<NodeIt>& S;

     std::list<NodeIt>& T;

     FlowMap& flow;

     const CapacityMap& capacity;

     typedef ResGraph<Graph, Number, FlowMap, CapacityMap > AugGraph;

     typedef typename AugGraph::OutEdgeIt AugOutEdgeIt;

     typedef typename AugGraph::EdgeIt AugEdgeIt;

     typename Graph::NodeMap<bool> SMap;

     typename Graph::NodeMap<bool> TMap;

   public:

     MaxFlow2(const Graph& _G, std::list<NodeIt>& _S, std::list<NodeIt>& _T, FlowMap& _flow, const CapacityMap& _capacity) : G(_G), S(_S), T(_T), flow(_flow), capacity(_capacity), SMap(_G), TMap(_G) { 

       for(typename std::list<NodeIt>::const_iterator i=S.begin(); 

 	  i!=S.end(); ++i) { 

 	SMap.set(*i, true); 

       }

       for (typename std::list<NodeIt>::const_iterator i=T.begin(); 

 	   i!=T.end(); ++i) { 

 	TMap.set(*i, true); 

       }

     }

     bool augment() {

       AugGraph res_graph(G, flow, capacity);

       bool _augment=false;

       NodeIt reached_t_node;

       typedef typename AugGraph::NodeMap<bool> ReachedMap;

       BfsIterator4< AugGraph, AugOutEdgeIt, ReachedMap > res_bfs(res_graph);

       for(typename std::list<NodeIt>::const_iterator i=S.begin(); 

 	  i!=S.end(); ++i) {

 	res_bfs.pushAndSetReached(*i);

       }

       //res_bfs.pushAndSetReached(s);

       typename AugGraph::NodeMap<AugEdgeIt> pred(res_graph); 

       //filled up with invalid iterators

       typename AugGraph::NodeMap<int> free(res_graph);

       //searching for augmenting path

       while ( !res_bfs.finished() ) { 

 	AugOutEdgeIt e=AugOutEdgeIt(res_bfs);

 	if (e.valid() && res_bfs.isBNodeNewlyReached()) {

 	  NodeIt v=res_graph.tail(e);

 	  NodeIt w=res_graph.head(e);

 	  pred.set(w, e);

 	  if (pred.get(v).valid()) {

 	    free.set(w, std::min(free.get(v), e.free()));

 	  } else {

 	    free.set(w, e.free()); 

 	  }

 	  if (TMap.get(res_graph.head(e))) { 

 	    _augment=true; 

 	    reached_t_node=res_graph.head(e);

 	    break; 

 	  }

 	}

 	++res_bfs;

       } //end of searching augmenting path

       if (_augment) {

 	NodeIt n=reached_t_node;

 	Number augment_value=free.get(reached_t_node);

 	while (pred.get(n).valid()) { 

 	  AugEdgeIt e=pred.get(n);

 	  e.augment(augment_value); 

 	  n=res_graph.tail(e);

 	}

       }

       return _augment;

     }

     void run() {

       while (augment()) { } 

     }

     Number flowValue() { 

       Number a=0;

       for(typename std::list<NodeIt>::const_iterator i=S.begin(); 

 	  i!=S.end(); ++i) { 

 	for(OutEdgeIt e=G.template first<OutEdgeIt>(*i); e.valid(); ++e) {

 	  a+=flow.get(e);

 	}

 	for(InEdgeIt e=G.template first<InEdgeIt>(*i); e.valid(); ++e) {

 	  a-=flow.get(e);

 	}

       }

       return a;

     }

   };