unire

Gigel are un graf cu $n$ noduri și $m$ muchii, care nu este conex. El dorește să afle răspunsul la două întrebări:

1. Care este numărul minim de muchii ce trebuie ađugate astfel încât graful să devină conex?
2. Dacă costul adăugării unei muchii între nodurile $a$ și $b$ este $a + b$, care este costul total minim al muchiilor care trebuie adăugate astfel încât graful să devină conex?

Date de intrare

Fișierul de intrare unire.in conține pe prima linie numerele $n$ și $m$, pe a doua linie conține numărul $c$, reprezentând numărul cerinței $1 \leq c \leq 2$, iar pe următoarele $m$ linii se află muchiile grafului $a \ b$, $1 \leq a, b \leq n$, $a \neq b$.

Date de ieșire

Fișierul de ieșire unire.out va conține pe prima linie numărul $S$, reprezentând răspunsul cerut de Gigel.

Restricții și precizări

• $1 \leq n \leq 100 \ 000$, $0 \leq m < n-1$
• Pentru teste în valoare de $30$ de puncte, cerința va fi 1.
• Pentru teste în valoare de $40$ de puncte, $1 \leq n \leq 1 \ 000$.

Exemplul 1

unire.in

6 3
1
1 2
3 4
5 6

unire.out

2

Exemplul 2

unire.in

6 3
2
1 2
3 4
5 6

unire.out

10

Explicație

Se vor uni nodurile $1$ și $3$, respectiv nodurile $1$ și $5$, s-au folosit $2$ muchii, iar costul total va fi $1 + 3 + 1 + 5 = 10$.