== include(page="template/taskheader" task_id="connect") ==

Poveste şi cerinţă...

_Note: This is the translated version of the statement. For the English (original) version of the statement, {'click here.':problema/connect/eng}_
 
h2. Cerinţă
 
Se da un graf neorientat cu n noduri si m muchii. Muchiile sunt numerotate in ordinea in care sunt date in fisierul de intrare.
 
Pentru fiecare pereche (i, j) pentru care $1 ≤ i ≤ j ≤ m$, se creeaza cate un graf cu n noduri si muchiile initiale indexate intre i si j inclusiv.
 
Sa se afle cate dintre aceste grafuri sunt conexe.

h2. Date de intrare

Fişierul de intrare $connect.in$ ...

Fişierul de intrare $connect.in$ contine pe prima linie numerele n si m. Pe fiecare din urmatoarele m linii se afla 2 numere: u si v, care denota faptul ca exista o muchie intre u si v.

h2. Date de ieşire

În fişierul de ieşire $connect.out$ ...

În fişierul de ieşire $connect.out$ se va afisa pe o singura linie numarul de grafuri conectate gasite.

h2. Restricţii

* $... ≤ ... ≤ ...$

* $2 ≤ n ≤ 50 000$
* $1 ≤ m ≤ 200 000$
* $1 ≤ u, v ≤ n$
* Graful poate contine mai multe muchii intre aceleasi 2 noduri
 
h2. Punctare
 
* Pentru $5$ puncte, $n ≤ 100$, $m ≤ 200$
* Pentru alte $15$ puncte, $n ≤ 2000$, $m ≤ 5000$
* Pentru alte $40$ de puncte, $n ≤ 200$
* Pentru restul de $40$ de puncte se aplica restrictiile initiale

h2. Exemplu
table(example). |_. connect.in |_. connect.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.
|

| 4 4
1 2
2 4
1 3
1 4
| 3 |

h3. Explicaţie

...

Perechile (i, j), pentru care graful rezultant este conectat, sunt (1, 3), (1, 4) si (2, 4).

== include(page="template/taskfooter" task_id="connect") ==