2282 - Componente Conexe 4
Enunț
Se consideră un graf neorientat cu n vârfuri și m muchii. Cele m muchii se elimină pe rând din graf.
Cerința
Pentru fiecare muchie eliminată trebuie să spuneți câte componente conexe are graful.
Date de intrare
Programul citește de la tastatură numerele n și m, iar pe următoarele m linii se află câte două valori x și y separate prin spațiu, reprezentând o muchie din graf. Muchiile vi se dau în ordinea în care ele se elimină din graf.
Date de ieșire
Programul va afișa pe ecran exact m linii, pe fiecare linie i aflându-se un singur număr natural reprezentând numărul componentelor conexe din graf după eliminarea celei de-a i-a muchii.
Restricții și precizări
1 ≤ n ≤ 100 0001 ≤ m ≤ 500 000- Între două vârfuri va exista cel mult o muchie
Exemplul 1
Intrare
5 6 1 2 3 4 2 3 1 5 5 4 4 1
Ieșire
1 2 3 3 4 5
Explicație
Sunt 5 vârfuri și 6 muchii. Urmează cele 6 muchii în ordinea eliminării lor. După eliminarea muchiei 1 2 graful este tot conex, deci rezultatul este 1. După eliminarea muchiei 3 4 se obțin două componente conexe, una formată din vârfurile 2, 3, iar cealaltă componentă formată din vârfurile 1, 4, 5. Restul eliminărilor nu mai trebuie explicate că ați înțeles deja.
Exemplul 1
Intrare
1000000000 10000000000
consola
Datele nu corespund restrictiilor impuse
