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.

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 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$ 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 $2$ numere: $u$ si $v$, care denota faptul ca exista o muchie 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 $15$ puncte, $n ≤ 2.000$, $m ≤ 5.000$

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

* Pentru restul de $40$ de puncte se aplica restrictiile initiale

* 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") ==