connect

Connect

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

_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.

Pentru fiecare pereche $(i, j)$ pentru care $1 ≤ i ≤ j ≤ m$, se creeaza cate un graf cu $n$ noduri si muchiile initiale numerotate intre $i$ si $j$ inclusiv.

Sa se afle cate dintre aceste grafuri sunt conexe.
h2. Date de intrare

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$.

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

h2. Date de ieşire

* Pentru $5$ puncte, $n ≤ 100$, $m ≤ 200$
* Pentru alte $15$ puncte, $n ≤ 2.000$, $m ≤ 5.000$

* Pentru alte $40$ de puncte, $n ≤ 200$

* Pentru alte $40$ de puncte, $n ≤ 200$, $m ≤ 200.000$

* Pentru restul de $40$ de puncte se aplica restrictiile initiale.
h2. Exemplu