Metrou4

Metrou 4

h2. Date de intrare

Datele de intrare se citesc din fişierul “metrou4.in”.

Datele de intrare se citesc din fisierul “metrou4.in”.

Pe prima linie se află numărul de teste, T. Fiecare test va începe cu numărul de locaţii N. Următoarele N linii sunt de forma X Y, unde X şi Y sunt numere întregi, reprezentând coordonatele unei locaţii.
h2. Date de ieşire

h2. Restricţii

* 1 ≤ T ≤ 12
* 1 ≤ N ≤ 150.000

* 1 ≤ T ≤ 10
* 1 ≤ N ≤ 200.000

* 0 ≤ X,Y ≤ 1.000.000.000
* Se poate săpa un tunel între oricare două locaţii.

* Fiecare tunel este distinct, nu se poate refolosi o secţiune a unui tunel săpat anterior pentru a conecta două locaţii.

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

| 3
3
0 0
1 1
0 2

| 2

4
0 0
1 1

2 2
1 1
0 0

| 4
3

| 3

10
|