#include <bits/stdc++.h>

using namespace std;
ifstream fin("in");

int n, m, tt[100001], sz[100001], x, y, var1, max1;

int Find(int nod)
{
    if (tt[nod] == nod)
        return nod;
    return tt[nod] = Find(tt[nod]);
}

void Union(int a, int b)
{
    if (a == b)
        return;
    var1++;
    if (sz[a] >= sz[b]) {
        sz[a] += sz[b];
        tt[b] = a;
    }
    else {
        sz[b] += sz[a];
        tt[a] = b;
    }
}

int main()
{
    fin >> n >> m;
    for (int i = 1; i <= n; i++) {
        tt[i] = i;
        sz[i] = 1;
    }
    for (int i = 1; i <= m; i++) {
        fin >> x >> y;
        Union(Find(x), Find(y));
        max1 = max(max(sz[Find(x)], sz[Find(y)]), max1);
        cout << n - var1 << " " << max1 << "\n";
    }
    return 0;
}