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

Se da un graf neorientat cu $n$ noduri si $m$ muchii. Muchiile sunt numerotate in ordinea in care sunt date in fisierul de intrare.

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

h2. Restricţii

* $2 ≤ n ≤ 50 000$
* $1 ≤ m ≤ 200 000$

* $2 ≤ n ≤ 50.000$
* $1 ≤ m ≤ 200.000$

* $1 ≤ u, v ≤ n$

* Graful poate contine mai multe muchii intre aceleasi 2 noduri

* 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

* Pentru alte $15$ puncte, $n ≤ 2.000$, $m ≤ 5.000$
* Pentru alte $40$ de puncte, $n ≤ 200$, $m ≤ 200.000$
* Pentru restul de $40$ de puncte se aplica restrictiile initiale.

h2. Exemplu

h3. Explicaţie

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

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

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