unire

Time limit: 0.1s Memory limit: 64MB Input: unire.in Output: unire.out

Gigel are un graf cu nn noduri și mm 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 aa și bb este a+ba + 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 nn și mm, pe a doua linie conține numărul cc, reprezentând numărul cerinței 1c21 \leq c \leq 2, iar pe următoarele mm linii se află muchiile grafului a ba \ b, 1a,bn1 \leq a, b \leq n, aba \neq b.

Date de ieșire

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

Restricții și precizări

  • 1n100 0001 \leq n \leq 100 \ 000, 0m<n10 \leq m < n-1
  • Pentru teste în valoare de 3030 de puncte, cerința va fi 1.
  • Pentru teste în valoare de 4040 de puncte, 1n1 0001 \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 11 și 33, respectiv nodurile 11 și 55, s-au folosit 22 muchii, iar costul total va fi 1+3+1+5=101 + 3 + 1 + 5 = 10.

Log in or sign up to be able to send submissions!