/*************************************************************************
 *                                                                       *
 *                    XI Olimpiada Informatyczna                         *
 *                                                                       *
 *   Rozwiązanie zadania: Wschód-Zachód                                  *
 *   Plik:                wscingen.cpp                                   *
 *   Autor:               Piotr Sankowski                                *
 *   Uwagi:               Program do generowania testów                  * 
 *************************************************************************/

#include <vector>
#include <iostream>
#include <fstream>
#include <algorithm>
#include <deque>

using namespace std;

class RandomSet : protected vector<int>{
  int n;
  int s;
  int mySize;

  void rearange(){
    int j = 0;
    for (int i=0; i<vector<int>::size() ; i++){
      if (operator[](i)!=0){
	if (i!=j){
	  operator[](j) = operator[](i);
	  operator[](i) = 0;
	}
	j++;
      };
    };
    while (back() == 0)
      pop_back();
    s = 0;
  };

public:
  RandomSet(int _n) : n(_n), s(0), mySize(0) {
  };

  void insert(int x){
    push_back(x);
    mySize++;
    s++;
  };

  int size() const{
    return mySize;
  };

  int remove(){
    if (s>::sqrt(n))
      rearange();
    s++;
    int i;
    do{
      i = lrand48() % vector<int>::size();
    } while (operator[](i) == 0);
    int wynik = operator[](i);
    operator[](i) = 0;
    mySize--;
    //cout << "R " << wynik << " " << mySize << " " << vector<int>::size() << endl;
    return wynik;
  };
};

class FIFOSet : protected deque<int>{

public:
  FIFOSet(int _n) {
  };

  void insert(int x){
    push_back(x);
  };

  int size() const{
    return deque<int>::size();
  };

  int remove(){
    int wynik = front();
    pop_front();
    return wynik;
  };
};



template <class SideSet>
class DaneWsc{
protected:
  const static int Wewnetrzne = 0;
  const static int Wschodnie = 1;
  const static int Zachodnie = 2;
  const static int Obydwa = 3;

  int w;
  int z;
  int p;
  
  int n;

  typedef pair<int,int> Krawedz;

  vector<Krawedz> krawedzie;

  vector<int> strona;

  vector<int> pociagi;

  void dodajKrawedz(int miasto1, int miasto2){
    krawedzie.push_back(Krawedz(miasto1, miasto2));
  };

public:

  void genPociagi(){
    RandomSet mozliwe(w);
    for (int i=1; i<=w ; i++)
      mozliwe.insert(i);
    for (int i=0; i<p ; i++){
      pociagi.push_back(mozliwe.remove());
    };
  };

  void genKrawedzie(SideSet &sideSet, int minDeg, int dDeg){
    
    while (sideSet.size()>1){
      int nowe = dodajMiasto(Wewnetrzne);
      int d = minDeg + lrand48()%dDeg;
      if (d>sideSet.size()){
	d = sideSet.size();
      };
      
      for (int i=0 ; i<d ; i++){
	dodajKrawedz(nowe, sideSet.remove());
      };
      sideSet.insert(nowe);
    };
  };

    int dodajMiasto(int stronaMiasta){
      n++;
      strona[n] = stronaMiasta;
      return n;
    }

  DaneWsc(int _w, int _z, int _p, int minDeg, int dDeg) : w(_w), z(_z), p(_p), n(0), strona((w+z)*2) {
    SideSet wschodnie(w+z);
    SideSet zachodnie(w+z);
    for (int i=1; i<=w ; i++){
      wschodnie.insert(dodajMiasto(Wschodnie));
    };
    for (int i=1; i<=z ; i++){
      zachodnie.insert(dodajMiasto(Zachodnie));
    };
    genPociagi();
    genKrawedzie(wschodnie, minDeg, dDeg);
    genKrawedzie(zachodnie, minDeg, dDeg);
    dodajKrawedz(wschodnie.remove(), zachodnie.remove());
  };

#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define REP(i,n) FOR(i, 0, (n)-1)

  DaneWsc(int w, int z, int n, int p) : w(w), z(z), p(p), n(n) {
    FOR(a,1,w)
      dodajKrawedz(a, w+z+a);
    FOR(a,1,w-1)
      dodajKrawedz(a+1, w+z+a);
    FOR(a,2*w+z+1,n)
      dodajKrawedz(a-1, a);
    FOR(a,w+1,w+z)
      dodajKrawedz(n, a);
    genPociagi();
  };

  DaneWsc() : w((1<<15)+1), z((1<<15)+1), p((1<<15)+1), n(1000000) {
    int size = (1<<15);
    FOR(p,1,16)
    {
    	int rozm = 1<<p;
	REP(a, size/rozm)
	{
	    REP(b, rozm-1)
	    {
	    	int pkt = 1+w+z+(p-1)*size+a*rozm+b;
		dodajKrawedz(pkt, pkt+1);
	    }
	    if (p>1)
	    {
	    	int pkt = 1+w+z+(p-1)*size+a*rozm;
		dodajKrawedz(pkt, pkt-size);
		dodajKrawedz(pkt+rozm-1, pkt-size+rozm-1);
	    }
	}
    }
    REP(a, size)
    	dodajKrawedz(1+a, 1+w+z+a);
    int last = 1+w+z+15*size-1;
    FOR(a,last,n-2)
      dodajKrawedz(a, a+1);
    dodajKrawedz(1+size, n-20);
    dodajKrawedz(n-40, n);
    REP(a,z)
      dodajKrawedz(n,1+w+a);
    genPociagi();
  };

  DaneWsc(int w) : w(w), z(w), p(w), n(1000000) {
    FOR(a,1,w)
      dodajKrawedz(a, 1+w+z+lrand48()%(n-5-w-z));
    FOR(a,w+1,w+z)
      dodajKrawedz(n-1, a);
    FOR(a,w+z+1,n-2)
      dodajKrawedz(a, a+1);
    dodajKrawedz(1,n);
    genPociagi();
  };

  DaneWsc(char *) : w(3), z(4), p(3), n(7+3*50+2+4*50) {
    FOR(a, 1, 3)
      dodajKrawedz(a, a+7);
    FOR(a, 7+1, 7+3*49)
      dodajKrawedz(a, a+3);
    FOR(a, 7+3*49+1, 7+3*50)
      dodajKrawedz(a, 7+3*50+1);
    dodajKrawedz(7+3*50+1, 7+3*50+2);
    FOR(a, 7+3*50+2+1, 7+3*50+2+4)
      dodajKrawedz(7+3*50+2, a);
    FOR(a, 7+3*50+2+1, 7+3*50+2+4*49)
      dodajKrawedz(a, a+4);
    FOR(a, 3+1, 7)
      dodajKrawedz(a, a+4+3*50+2+4*49);
    genPociagi();
  };

  DaneWsc<SideSet> add(int maxn){
    while (size()<maxn) {
      int nowe;
      if (lrand48()%2)
	nowe = dodajMiasto(Wschodnie);
      else
	nowe = dodajMiasto(Zachodnie);
      dodajKrawedz(nowe, lrand48()%n + 1);
    };
    return *this;
  };


  friend ostream& operator<<(ostream &os, const DaneWsc &data){
    os << data.n << " " << data.w << " " << data.z << endl;
    vector<int> numery;
    numery.push_back(0);
    for (int i=1 ; i<=data.w ; i++)
      numery.push_back(i);
    for (int i=1 ; i<=data.z ; i++)
      numery.push_back(data.n - data.z + i);
    for (int i=1 ; i<=data.n-data.z-data.w ; i++)
      numery.push_back(data.w+i);

    random_shuffle(numery.begin()+1, numery.begin()+data.w+1);
    random_shuffle(numery.begin()+data.w+1, numery.begin()+data.w+data.z+1);
    random_shuffle(numery.begin()+data.w+data.z+1, numery.begin()+data.n+1);

    vector<int> numeryKrawedzi;
    for (int i=0 ; i<data.krawedzie.size() ; i++)
      numeryKrawedzi.push_back(i);
    random_shuffle(numeryKrawedzi.begin(), numeryKrawedzi.end());

    for (int i=0 ; i<data.krawedzie.size() ; i++)
      os << numery[data.krawedzie[numeryKrawedzi[i]].first] << " " << numery[data.krawedzie[numeryKrawedzi[i]].second] << endl;
    os << data.pociagi.size() << endl;
    for (int i=0 ; i<data.pociagi.size() ; i++)
    {
      os << numery[data.pociagi[i]];
      if (i<data.pociagi.size()-1)
        os << " ";
    }
    os << endl;
  };

  int size() const{
    return n;
  };

};


int main(){
  srand48(12);
  {
    ofstream ofs("wsc1.in");
    ofs << DaneWsc<RandomSet>(5, 5, 4, 2, 2);
  }
  {
    ofstream ofs("wsc2.in");
    ofs << DaneWsc<FIFOSet>(128, 128, 100, 2, 1);
  }
  
  {
    ofstream ofs("wsc3.in");
    ofs << DaneWsc<RandomSet>(5000, 5010, 5000, 4, 4);
  }
  {
    ofstream ofs("wsc4.in");
    ofs << DaneWsc<FIFOSet>(10000, 10100, 10000, 1, 4);
  }
  {
    ofstream ofs("wsc5.in");
    ofs << DaneWsc<FIFOSet>(32768, 32768, 10000, 2, 1);
  }
  {
    ofstream ofs("wsc6.in");
    ofs << DaneWsc<FIFOSet>(50000, 50000, 10000, 2, 8);
  }
  {
    ofstream ofs("wsc7.in");
    ofs << DaneWsc<RandomSet>(45000, 55000, 40000, 1, 3);
  }
  {
    ofstream ofs("wsc8.in");
    ofs << DaneWsc<RandomSet>(100000, 200000, 100000, 1, 10);
  }
  {
    ofstream ofs("wsc9.in");
    ofs << DaneWsc<FIFOSet>(200000, 200000, 100000, 6, 6);
  }
  {
    ofstream ofs("wsc10.in");
    ofs << DaneWsc<RandomSet>(350000, 350000, 100000, 1, 6).add(1000000);
  }
  {
    ofstream ofs("wsc11.in");
    ofs << DaneWsc<RandomSet>(300000, 300000, 1000000, 300000);
  }
  {
    ofstream ofs("wsc12.in");
    ofs << DaneWsc<RandomSet>();
  }
  {
    ofstream ofs("wsc13.in");
    ofs << DaneWsc<RandomSet>(100000);
  }
  {
    ofstream ofs("wsc4ocen.in");
    ofs << DaneWsc<RandomSet>("ocen");
  }
 
};
