/* FILE: randDFSgraph.cpp   last change: 26-Jan-2013   author: Romeo Rizzi
 * This program generates a random graph on top of its DFS tree.
 * Usage syntax:
 *   > randDFSgraph n m  seed
 * Usage example:
 *   > randDFSgraph 10 20 777
 */

#include <iostream>
#include <cstdlib>
#include <ctime>

using namespace std;

const int MAX_N = 100;  // massima numero di nodi;
int n, m; // numero di nodi e numero di archi

bool seen[MAX_N], open[MAX_N];
int LIFOstack[MAX_N], LIFOpos = 0;

int RandNumber(int min, int max) {
  /* returns an integer in [min, max]
   * see Stroustrup "The c++ Programming Language" 3th edition pg. 685
   * for comments on the following manipulation choice.
   * In particular, considerations on the bad quality of low bits come into account.
   */
  return min + (int) ( (max-min +1) * (double( rand()-0.000000000001 ) / RAND_MAX ) );
}


int main(int argc, char** argv) {
  srand(time(NULL));
  n = atoi(argv[1]); m = atoi(argv[2]);
  if(argc > 3) srand( atoi(argv[3]) );

  cout << n << " " << m << endl;
  int mu = m-n+1; // the ciclomatic number (number of non-tree edges)

  for(int i = 0; i < n; i++)  seen[i] = open[i] = false;
  int m_tree = 0, m_cotree = 0;
  int v = 0; seen[v] = true;
  while( m_tree + m_cotree < m ) {
    if( LIFOpos > 3*(m -  m_tree - m_cotree) ) v = LIFOstack[ --LIFOpos ];
    int next = RandNumber(0, n-1);
    while( (next == v) || ( seen[next] && (m_cotree == mu) ) ) next = RandNumber(0, n-1);
    cout << v << " " << next << endl;
    if( seen[next] ) m_cotree++;
    else {
      m_tree++;
      seen[next] = true;
      LIFOstack[ LIFOpos++ ] = v;
      v = next;
    }
  }

  return 0;
}