#include <cstdlib>

 #include <iostream>

 #include <sstream>

 #include <lemon/smart_graph.h>

 #include <lemon/bpugraph_adaptor.h>

 #include <lemon/bipartite_matching.h>

 #include <lemon/graph_utils.h>

 #include <lemon/xy.h>

 #include <lemon/graph_to_eps.h>

 #include <lemon/time_measure.h>

 using namespace std;

 using namespace lemon;

 typedef SmartBpUGraph Graph;

 BPUGRAPH_TYPEDEFS(Graph);

 int _urandom_init() {

   int seed = time(0);

   srand(seed);

   return seed;

 }

 int urandom(int n) {

   static int seed = _urandom_init();

   ignore_unused_variable_warning(seed);

   return (int)(rand() / (1.0 + RAND_MAX) * n);

 }

 int main() {

   for (int k = 1; k < 100; ++k) {

     int n = k * 100;

     int m = (100 - k) * 100;

     int e = 20000;

     int s = 100;

     Timer nt(false), st(false);

     for (int i = 0; i < s; ++i) {

       Graph graph;

       vector<Node> aNodes;

       vector<Node> bNodes;  

       for (int i = 0; i < n; ++i) {

         Node node = graph.addANode();

         aNodes.push_back(node);

       }

       for (int i = 0; i < m; ++i) {

         Node node = graph.addBNode();

         bNodes.push_back(node);

       }

       for (int i = 0; i < e; ++i) {

         Node aNode = aNodes[urandom(n)];

         Node bNode = bNodes[urandom(m)];

         graph.addEdge(aNode, bNode);

       }

       {

         MaxBipartiteMatching<Graph> bpmatch(graph);

         nt.start();

         bpmatch.init();

         bpmatch.start();

         nt.stop();

       }

       {

         typedef SwapBpUGraphAdaptor<Graph> SGraph;

         SGraph sgraph(graph);

         MaxBipartiteMatching<SGraph> bpmatch(sgraph);

         st.start();

         bpmatch.init();

         bpmatch.start();

         st.stop();

       }

     }

     cout << k * 100 << ' ' << nt.realTime() << ' ' << st.realTime() << endl;

   }

   return 0;

 }