snm1

// #include <algorithm>
#include <cstdio>
#include <utility>
#include <vector>

#define ULL unsigned long long
#define LL long long
#define uint unsigned int

uint sz_max = 1;

std::vector<uint> p, sz;

// O(log(n))
uint get(uint v) {
  if (v == p[v])
    return v;
  p[v] = get(p[v]);
  return p[v];
}

bool check(uint v, uint u) {
  if (get(v) == get(u))
    return true;
  else
    return false;
}

bool unite(uint v, uint u) {
  int x = get(v);
  int y = get(u);
  if (x == y)
    return false;
  if (sz[x] > sz[y])
    std::swap(x, y);
  p[x] = y;
  sz[y] += sz[x];

  if (sz[y] > sz_max) {
    sz_max = sz[y];
  }
  return true;
}

int main() {
  uint n = 0;
  scanf("%u", &n);

  p.resize(n, 0);
  sz.resize(n, 0);

  uint n_cmp = n;

  for (uint i = 0; i < n; i++) {
    p[i] = i;
    sz[i] = 1;
  }

  uint q;
  scanf("%u", &q);

  for (uint i = 0; i < q; i++) {
    uint v, u;
    scanf("%u %u", &v, &u);
    if (unite(--v, --u)) {
      n_cmp--;
    }

    printf("%u %u\n", n_cmp, sz_max);
  }

  return 0;
}