Fişierul intrare/ieşire:feisbuc.in, feisbuc.outSursăOlimpiada locală 2015, clasele 11-12
AutorRadu BorigaAdăugată deheracleRadu Muntean heracle
Timp execuţie pe test0.1 secLimită de memorie8192 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise

Feisbuc (clasele 11-12)

Cuprins de febra socializării on-line, Firicel a creat o nouă reţea de socializare, numită Feisbuc. În timp, între unele perechi de utilizatori ai reţelei s-au stabilit relaţii de prietenie reciprocă. Pentru a menţine şi dezvolta reţeaua Feisbuc, Firicel are nevoie de mai mulţi bani, pe care s-a gândit să-i obţină din publicitate on-line. În acest sens, el a implementat în cadrul reţelei o mesagerie instantanee care îi permite să trimită un mesaj publicitar oricărui utilizator al reţelei într-o secundă. Din raţiuni de marketing, Firicel nu doreşte să trimită el însuşi mesaje publicitare tuturor utilizatorilor reţelei şi, ca atare, sistemul de mesagerie instantanee creat va trimite, în mod automat, orice mesaj publicitar primit de către un utilizator şi tuturor prietenilor acestuia, tot într-o secundă. În plus, în reţeaua Feisbuc, prieteniile au fost limitate astfel încât, niciun utilizator să nu primească un mesaj publicitar de mai multe ori (nici simultan, nici în secunde diferite).

Cunoscând perechile de utilizatori între care s-au stabilit relaţii de prietenie reciprocă, scrieţi un program care să determine:
a) numărul minim de utilizatori u cărora Firicel trebuie să le transmită un mesaj publicitar astfel încât respectivul mesaj să fie primit de toţi utilizatorii reţelei Feisbuc;
b) timpul minim t în care toţi utilizatorii reţelei Feisbuc primesc mesajul publicitar trimis de Firicel.

Date de intrare

Fişierul de intrare feisbuc.in conţine pe prima linie două numere naturale nenule n şi m, primul reprezentând numărul utilizatorilor reţelei Feisbuc, identificaţi prin numere naturale cuprinse între 1 şi n, iar cel de-al doilea reprezentând numărul perechilor de utilizatori ai reţelei între care s-au stabilit relaţii de prietenie reciprocă. Pe următoarele m linii din fişier sunt scrise perechi de numere naturale de forma X Y, indicând faptul că utilizatorii X şi Y sunt prieteni.

Date de ieşire

Pe prima linie a fişierului de ieşire feisbuc.out se vor scrie cele două numere naturale u şi t cerute, despărţite printr-un spaţiu.

Restricţii

1 <= n <= 5000
1 <= m <= 1000000 
1 <= X < Y <= n
Perechile X Y sunt distincte şi respectă restricţiile de prietenie impuse de reţea.
Pentru 50% din teste se garantează faptul că 1 <= n <= 500 şi 1 <= m <= 100000.
Pentru determinarea corectă a numărului u se acordă 30% din punctajul testului respectiv, iar pentru determinarea corectă a numărului t se acordă 70% din punctajul testului respectiv.

Exemplu

feisbuc.infeisbuc.out
8 6
1 2
2 4
2 5
3 7
4 8
6 7
2 3

Explicaţie

Pentru ca un mesaj publicitar să fie primit de toţi utilizatorii reţelei, Firicel trebuie să-l trimită unuia dintre utilizatorii 1, 2, 4, 5, 8 şi unuia dintre utilizatorii 3, 6, 7, deci u=2.

Timpul minim în care toţi utilizatorii reţelei primesc mesajul publicitar trimis de Firicel este t=3 secunde şi se obţine, de exemplu, dacă Firicel transmite mesajul publicitar utilizatorilor 2 şi 7 într-o secundă, de la aceştia se transmite mesajul la 1, 5, 4 şi respectiv 3 şi 6 în secunda a doua, iar în secunda a treia, de la utilizatorul 4 se transmite mesajul la utilizatorul 8.

Trebuie sa te autentifici pentru a trimite solutii. Click aici