/*
  Copyright (C) 2003, Guillaume-Latapy - LIAFA (University of Paris 7)

  Disclaimer: this code is provided 'as-is', without any express or
  implied warranty. In no event will the authors be held liable for 
  any damages arising from the use of this software.

  Permission is granted to anyone to use this code for any purpose,
  to alter it and redistribute it without restrictions. Just feel
  free to inform us if you plan to use it. If you face any problems
  or find any bug, please contact us using our webpage:
    http://jlguillaume.free.fr/

  --------------------------------------------------

  Generates a random "configuration model" graph, with a prescribed degree
  distribution.
  Generated graph is sent to stdout as a set of links (one per line).
*/

#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <fstream>
#include <vector>

#define EXIT_SUCCESS 0
#define EXIT_FAILURE 1

using namespace std;
using std::cout;
using std::cin;
using std::cerr;


void usage(char *program_name, int status) {
  if (status == EXIT_SUCCESS)
    {
      cout << "Usage: " << program_name << " [file_distrib]" << endl
	   << "  Generates a random Molloy-Reed graph with a prescribed degree distribution" << endl
	   << "  as given either in file_distrib or on stdin." << endl
	   << "  Graph is printed on stdout with one link per line." << endl
	   << "    -h, this usage" << endl
	   << "Remarks:" << endl
	   << "  If file_distrib contains 'k Nk' on each line, then sum(k*Nk) must be even." << endl
	   << "  Resulting graph may contain multiples links or loops." << endl;
    }
  else
    {
      cerr << "Try '" << program_name << " -h' for usage information." << endl;
    }
  exit(status);
}

int swap(int &a, int &b) {
  int tmp=a;
  a=b;
  b=tmp;
}


int
main(int argc, char **argv)
{
  srand(time(NULL));

  if (strcmp(argv[1],"-h")==0)
    usage(argv[0], EXIT_SUCCESS);

  ifstream inFile;
  if (argc==2) {
    inFile.open(argv[1], ifstream::in);
    if (!inFile.is_open()) {
      cerr << argv[0] << ": can't stat source " << argv[1] << endl;
      exit(EXIT_FAILURE);
    }
    cin.rdbuf(inFile.rdbuf()); // Redirect
  }
  
  int vertex = 0;
  vector<int> connections;

  while(cin) {
    int deg, nbvertices;
    cin >> deg >> nbvertices;
    
    if (cin) {
      for (int i=0 ; i<nbvertices ; i++) {
	for (int j=0; j<deg ;j++) {
	  connections.push_back(vertex);
	}
	vertex++;
      }
    }
  }

  if (connections.size()%2!=0) {
    cout << "Sum of degree is not even. Graph cannot be generated." << endl;
    exit(EXIT_SUCCESS);
  }
  
  for(int i=0 ; i<connections.size() ; i+=2) {
    swap(connections[i], connections[rand()%(connections.size()-i)+i]);
    swap(connections[i+1], connections[rand()%(connections.size()-i-1)+i+1]);
    cout << connections[i] << " " << connections[i+1] << endl;
  }
}