Components connexos P94041

En un graf no dirigit amb n nodes, i inicialment sense cap aresta, s’hi han d’inserir m arestes donades, en l’ordre en què es donen, i dient quants components connexos té el graf després de cada inserció.

Entrada

L’entrada consisteix en diversos casos. Cada cas comença amb n i m, seguits de les arestes. Cada aresta es descriu amb els seus dos vèrtexs. Suposeu 2 ≤ n ≤ 10⁵, 1 ≤ m ≤ 2n, que els vèrtexs es numeren entre 0 i n−1, i que no hi ha arestes repetides, ni arestes que connectin un vèrtex amb ell mateix.

Sortida

Per a cada cas, escriviu una línia amb m nombres separats per espais: el k-èssim ha de ser el nombre de components connexos del graf si només considerem les k primeres arestes de l’entrada.