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

På första raden står heltalen $n$, $m$, $k$ där $1 \le n \le 300\, 000$, $1\le m \le 500\, 000$ och $1 \le k \le m$. Därefter följer $m$ rader med koordinaterna $(x_ i, y_ i)$ för varje fyrtorn, som uppfyller $0 \le x_ i, y_ i < n$. Du kan inte förutsätta att fyrtornen står jämnt utspridda.

Utdata

En rad med ett heltal, hur många fyrtorn du totalt kan lysa upp.

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