/* Copyright 1995, 2003, Igor Rivin, all rights reserved */
/* genbipartite(num_red, deg1, deg2) generates a random bipartite
   graph with num_red red vertices and num_red * deg1/deg2 blue
   vertices */

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define TRUE 1
#define FALSE 0

#define SWAPV(a, b, t) (t=vec[a], vec[a] = vec[b], vec[b] = t)
#define SWAP(x, y, z) ((z) = (x), (x) = (y), (y) = (z))

/* Random number generator */

int
myrand(k)
int k;
{
  double tempr, tempk, tempres;
  
  tempk = (double)k;
  tempr = (double)rand();
  tempres = tempk * tempr/(RAND_MAX+1.0);
  return ((int)tempres);
}

/* generates a random permutation of vec of length n */

int
randperm(vec, len)
int *vec;
int len;
{
  int i;
  int rand;
  int tmp;
  
  for(i = 0; i<len; ++i)
    {
      rand = i+myrand(len-i);
      SWAPV(i, rand, tmp);
    }
}


void
freeaux(n, deg, aux)
int n;
int deg;
int **aux;
{
  int i;
  
  for (i=0; i<n; ++i)
    free(aux[i]);
  
  free(aux);
}

/* checks if all of the elements of ar between start and start + len - */
/* 1 are distinct. Uses n^2 algorithm, but doesn't matter much for the */
/* cases of interest */

int 
checkaux(ar, el, len)
     int *ar;
     int el;
     int len;
{
  int i;
  
  for (i=0; i< len; ++i)
    if (el == ar[i])
      return TRUE;
  return FALSE;
}

int 
checkdist(ar, len)
     int *ar;
     int len;
{
  int i;
  
  for (i=0; i < len-1; ++i)
    if(checkaux(ar+i+1, ar[i], len-i-1))
      return TRUE;
  return FALSE;
}

/* n is the number of blue vertices; the number of red vertices is n * */
/* deg1/deg2 */
    
void 
initialize(n, deg1, deg2, ar)
int n, deg1, deg2;
int *ar;
{
  int i, j, k;
  int bad = TRUE;

  while(bad)
    {
      bad = FALSE;
      for (i = 0, j=0; i < n; ++i, j+= deg1)
	for(k=0; k<deg1; ++k)
	  ar[j+k] = i;
      randperm(ar, n * deg1);
      for (i=0; i<n * deg1 - 1; i += deg2)
	if(bad = checkdist(ar + i, deg2))
	  break;
    }
}

int
main(argc, argv)
int argc;
char *argv[];
{
  int deg1, deg2, num, num2;
  int *graph;
  int i, j, k;
  
  num = atoi(argv[1]);
  deg1 = atoi(argv[2]);
  deg2 = atoi(argv[3]);
  num2 = (num * deg1)/deg2;

  srand(time(NULL));
  
  graph = (int *) malloc(num * deg1 * sizeof(int));
  
  initialize(num, deg1, deg2, graph);
  
  printf("%d\n", num + num2);
  for (i = 0, j = 0; i< num * deg1 - 1; ++j, i+= deg2)
    for (k=0; k< deg2; ++k)
      {
      printf("%d\t%d\t%d\n", j+num, graph[i+k], 1);
      printf("%d\t%d\t%d\n", graph[i+k], j+num, 1);
    }

  for (i = 0; i<num+num2; ++i)
    printf("%d\t%d\t%d\n", i, i, num+num2);

  exit(0);
}