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 \le n \le 10^5$, $1 \le m \le 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.