Agora GSM deține n dispoziție pentru comunicație identificate prin numere cuprinse între 1 și n. Din nefericire nu este posibilă comunicația între oricare două dispozitive. Mai mult, dacă un mesaj poate fi transmis de la un dispozitiv x la un dispozitiv y, nu este sigur că poate fi transmis și un mesaj de la dispozitivul y la dispozitivul x.
Compania dorește să determine numărul minim al grupurilor care pot fi formate astfel încât să existe posibilitatea comunicării directe sau indirecte între oricare două dispozitive care fac parte din același grup.
Prima linie a fișierului de intrare DEVICES.IN conține numărul n al dispozitivelor de comunicare și numărul m al legăturilor care pot fi stabilite între dispozitive. Fiecare dintre următoarele m linii va conține două numere întregi x și y cu semnificația: există posibilitatea de a transmite un mesaj de la dispozitivul x la dispozitivul y. Numerele de pe o linie vor fi separate prin spații.
Fișierul de ieșire DEVICES.OUT trebuie să conțină o singură linie pe care se va afla numărul minim al grupurilor care pot fi formate astfel încât să existe posibilitatea comunicării directe sau indirecte între oricare două dispozitive care fac parte din același grup.
DEVICES.IN
4 5 1 2 2 3 2 4 3 1 3 4 DEVICES.OUT 2
|