#include "magiccity.h"
#include <cassert>
#include <cstdio>
#include <utility>
#include <vector>

int main() {
  int K;
  assert(1 == scanf("%d", &K));
  fclose(stdin);

  std::pair<std::vector<int>, std::vector<std::pair<int, int>>> result =
      construct(K);
  const std::vector<int> &T = result.first;
  const std::vector<std::pair<int, int>> &E = result.second;
  int N = (int)T.size();
  int M = (int)E.size();

  printf("%d %d\n", N, M);
  for (int i = 0; i < N; i++) {
    printf("%d%c", T[i], " \n"[i + 1 == N]);
  }
  if (N == 0) {
    printf("\n");
  }
  for (int j = 0; j < M; j++) {
    const int U = E[j].first;
    const int V = E[j].second;
    printf("%d %d\n", U, V);
  }
  fclose(stdout);
  return 0;
}
