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

/* gcc -std=gnu99 gengnk.c -o gengnk */

void init_random_generator(){
  struct timespec time;
  clock_gettime(CLOCK_REALTIME, &time);
  srandom(time.tv_nsec ^ time.tv_sec);
}

int uniform(int n){
  return random() % n;          // Linux random() function, low-order bits safe
}

bool in(int* tab, int len, int value){
  for(int i=0; i<len; i++)
    if(tab[i] == value)
      return true;
  return false;
}

int random_vertex_avoiding(int n, int* neighbors, int v, int i){
  int x;
  do{x = uniform(n);} while(x == v || in(neighbors, i, x));
  return x;
}

int main(int argc, char** argv){
  init_random_generator();
  bool binary_mode = false;
  
  if(argc < 3){
    printf("usage: %s n k [filename]\n", argv[0]);
    return EXIT_FAILURE;
  }
  
  int n = atoi(argv[1]), k = atoi(argv[2]);
  if(n < k+1){
    printf("error: n < k+1 \n");
    return EXIT_FAILURE;
  }

  int** graph = (int**)malloc(sizeof(int*)*n);
  for(int v=0; v<n; v++)
    graph[v] = (int*)malloc(sizeof(int)*k);
  int* indegree = (int*)calloc(n,sizeof(int));

  for(int v=0; v<n; v++)
    for(int i=0; i<k; i++){
      graph[v][i] = random_vertex_avoiding(n, graph[v], v, i);
      indegree[graph[v][i]]++;
    }

  if(argc < 4){
    printf("%d\n",n);
    for(int v=0; v<n; v++)
      printf("%d %d\n",v,k+indegree[v]);
    
    for(int v=0; v<n; v++)
      for(int i=0; i<k; i++)
        if(v<graph[v][i])
          printf("%d %d\n",v,graph[v][i]);
        else if(!in(graph[graph[v][i]], k, v))            // skip multiple edges
          printf("%d %d\n",graph[v][i],v);
  }
  else{
    FILE* f = fopen(argv[3], "wb");
    fwrite(&n, sizeof(int), 1, f);
    for(int v=0; v<n; v++){
      fwrite(&v, sizeof(int), 1, f);
      int g = k+indegree[v];
      fwrite(&g, sizeof(int), 1, f);
    }
    
    for(int v=0; v<n; v++)
      for(int i=0; i<k; i++)
        if(v<graph[v][i]){
          fwrite(&v, sizeof(int), 1, f);
          fwrite(&graph[v][i], sizeof(int), 1, f);
        }
        else if(!in(graph[graph[v][i]], k, v)){
          fwrite(&graph[v][i], sizeof(int), 1, f);
          fwrite(&v, sizeof(int), 1, f);
        }
     fclose(f);
  }
  
  free(indegree);
  for(int v=0; v<n; v++)
    free(graph[v]);
  free(graph);

  return EXIT_SUCCESS;
}