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

/* gcc -std=gnu99 maxdeg-gnk.c -o maxdeg-gnk */

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 [m]\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 m = 1;
  if(argc >= 4) 
    m = atoi(argv[3]);
  
  int* neighbors = (int*)malloc(sizeof(int)*k);
  int* indegree = (int*)malloc(sizeof(int)*n);
  
  for(int i=0; i<m; i++){
    int max = 0;
    
    for(int v=0; v<n; v++)
      indegree[v] = 0;
      
    for(int v=0; v<n; v++)
      for(int i=0; i<k; i++){
        neighbors[i] = random_vertex_avoiding(n, neighbors, v, i);
        indegree[neighbors[i]]++;
      }
     
    /* Degrees
    for(int v=0; v<n; v++) 
      printf("%d\n",k+indegree[v]); */
      
    for(int v=0; v<n; v++)      
      if(k+indegree[v] > max)
        max = k+indegree[v];
     
    printf("%d\n",max);
    fflush(stdout);
  }

  free(indegree);
  free(neighbors);

  return EXIT_SUCCESS;
}