Diferențe pentru problema/meta între reviziile #8 si #9

Elevii de la cercul de informatică înțeleg atât de bine algoritmii pentru găsirea arborelui parțial de cost minim, încât îi pot implementa și cu ochii închiși. De aceea, profesorul le-a dat o problemă ceva mai grea: găsirea celui de-al doilea arbore parțial în ordinea costului.

Se dă un graf neorientat cu $N$ noduri și $M$ muchii. Fiecare muchie are un cost pozitiv asociat și toate muchiile au costuri diferite. Ajutați-i pe elevii de la cerc să calculeze costul celui de-al doilea arbore parțial minim. Mai exact, se cere cel mai mic număr natural $K$ cu proprietățile:

Se dă un graf neorientat conex cu $N$ noduri și $M$ muchii. Fiecare muchie are un cost pozitiv asociat și toate muchiile au costuri diferite. Ajutați-i pe elevii de la cerc să calculeze costul celui de-al doilea arbore parțial minim. Mai exact, se cere cel mai mic număr natural $K$ cu proprietățile:

# Există un arbore parțial de cost total [$K$].
# $K$ este strict mai mare decât costul arborelui parțial de cost minim pentru graful dat.

* $1 ≤ N ≤ 1.000$
* $1 ≤ M ≤ 300.000$

* $M ≥ N$

* Nodurile sunt numerotate de la 1 la [$N$].
* Costurile muchiilor sunt numere naturale distincte cuprinse între 1 și 1.000.000.