#include <cassert>
#include <ctime>
#include <iostream>
#include <numeric>
#include <random>
#include <set>
#include <vector>

using namespace std;

#define ALL(c) c.begin(), c.end()
#define SZ(c) (int)c.size()

mt19937 rnd;
void gen();

int main() {
  assert(freopen("test.in", "r", stdin));
  assert(freopen("test.out", "w", stdout));
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  cerr.precision(3);
  cerr << fixed;
  int start = (int)clock();
  rnd = mt19937(time(NULL));
  gen();
  double run_time = (double)(clock() - start) / CLOCKS_PER_SEC;
  cerr << "TIME: " << run_time << '\n';
  return 0;
}

const int N = 1e5 + 7;

int n, m;
vector<pair<int, int>> edges;
vector<int> g[N];

int par[N], sz[N];

void build(int n) {
  iota(par, par + n, 0);
  fill(sz, sz + n, 1);
}

int find(int x) { return x == par[x] ? x : par[x] = find(par[x]); }

bool join(int x, int y) {
  x = find(x);
  y = find(y);
  if (x != y) {
    if (sz[x] > sz[y]) {
      swap(x, y);
    }
    par[x] = y;
    sz[y] += sz[x];
  }
  return x != y;
}

bool check() {
  build(n);
  int cnt = 0;
  for (auto a : edges) {
    cnt += join(a.first, a.second);
  }
  return cnt == n - 1;
}

void build_complete_graph() {
  for (int v = 0; v < n; ++v) {
    for (int u = 0; u < v; ++u) {
      edges.push_back({v, u});
    }
  }
}

void build_big_graph() {
  const int C = 8;
  set<pair<int, int>> e;
  int attempt = 1;
  do {
    cerr << "ATTEMPT #" << attempt++ << '\n';
    while (SZ(e) != max(m, C * n)) {
      int v = rnd() % (n - 1) + 1;
      int u = rnd() % v;
      if (!e.count({v, u}) && !e.count({u, v})) {
        e.insert({v, u});
      }
    }
    edges.clear();
    for (auto a : e) {
      edges.push_back(a);
    }
  } while (!check());
}

int tin[N], ct = 1;
int up[N];
vector<int> biconnected_edges;

void dfs(int v, int last, int id) {
  up[v] = tin[v] = ct++;
  for (int i : g[v]) {
    int u = (edges[i].first ^ edges[i].second ^ v);
    if (!tin[u]) {
      dfs(u, v, i);
      up[v] = min(up[v], up[u]);
    } else if (u != last) {
      up[v] = min(up[v], tin[u]);
    }
  }
  if (up[v] != tin[v] && last != v) {
    biconnected_edges.push_back(id);
  }
}

void build_biconnected_edges() {
  biconnected_edges.clear();
  for (int v = 0; v < n; ++v) {
    g[v].clear();
  }
  for (int i = 0; i < SZ(edges); ++i) {
    auto [v, u] = edges[i];
    g[v].push_back(i);
    g[u].push_back(i);
  }
  ct = 1;
  fill(tin, tin + n, 0);
  dfs(0, 0, -1);
}

void gen() {
  cin >> n >> m;
  assert(m >= n - 1 && m <= n * 1LL * (n - 1) / 2);
  // build_complete_graph();
  build_big_graph();
  while (SZ(edges) > m) {
    build_biconnected_edges();
    int i = biconnected_edges[rnd() % SZ(biconnected_edges)];
    swap(edges[i], edges.back());
    edges.pop_back();
  }
  assert(check());
  cout << n << ' ' << m << '\n';
  for (auto e : edges) {
    cout << e.first + 1 << ' ' << e.second + 1 << '\n';
  }
}