Problem C
Fyrtornen

Vi har ett kvadratiskt rutnät på $n \times n$ rutor. Det finns $m$ stycken fyrtorn utplacerade. Till en början är alla “släckta”, men när du tänder ett av dem så tänds samtliga andra fyrtorn som har en $x$- eller $y$-koordinat gemensam med det redan tända tornet, och detta forsätter sedan rekursivt. Antag nu att du själv får tända $k$ torn, och att du ska tända tornen så att så många som möjligt lyser på slutet. Hur många torn kan du få att lysa?

Indata

Den första raden av indata innehåler heltalen $n$, $m$ och $k$ ($1 \leq n \leq 3 \cdot 10^5$, $1 \leq m \leq 5 \cdot 10^5$, $1 \leq k \leq m$).

De följande $m$ radera innehåller vardera heltalskoordinaterna $(x_i, y_i)$ för varje fyrtorn, som uppfyller $0 \le x_i, y_i < n$. Det står som mest ett torn på varje ruta. Du kan inte förutsätta att fyrtornen står jämnt utspridda.

Utdata

Skriv ut ett heltal: det största antalet fyrtorn du kan lysa upp om du sätter på som mest $k$ stycken.

Poängsättning

Din lösning kommer att testas på en mängd testfallsgrupper. För att få poäng för en grupp så måste du klara alla testfall i gruppen.

4 5 2
0 0
1 1
0 1
2 2
3 3

4

20 15 4
19 2
6 15
18 6
18 11
0 10
9 12
17 8
14 2
17 10
3 9
12 11
5 19
0 4
13 11
1 5

11