Norii se formează atunci când vaporii invizibili de apă din aer (particule elementare al căror diametru este mai mic de 0.01mm) se condensează în picături de apă vizibile sau în cristale de gheaţă. Un nor conţine n particule elementare numerotate de la 1, 2, …, n.
Un proces important în formarea formaţiunilor noroase este procesul de coliziune şi captare în care coliziunea dintre particule elementare care se ridică şi coboară produce cuplarea (captarea) acestora în picături din ce în ce mai mari, care în final sunt destul de grele pentru a cădea pe pământ sub formă de ploaie. Numărul minim de particule elementare conţinute de o picătură ca să cadă pe pământ este de 3 particule.
Ca procesul de captare să aibă loc trebuie ca între două particule aflate în picături diferite să existe coliziune, picătura cu număr de particule mai mare atrage picătura cu număr de particule mai mic sau cel mult egal.
Pentru a se forma un nor Cumulonimbus (Cumulus - grămadă), adică un nor care aduce ploaia, sunt necesare cel puţin n/2+1 particule elementare distribuite în picături suficient de mari pentru a cădea pe pământ.
Cerinţă
Fiind date n, numărul de particule elementare, m, numărul de coliziuri şi cele m coliziuni, să se scrie un program ce determină numărul minim de picături necesare pentru formarea unui nor Cumulonimbus.
Date de intrare
Fişierul de intrare nor.in conţine pe prima linie două numere naturale separate prin spaţiu n şi m, n reprezentând numărul total de particule elementare, respectiv m numărul de coliziuni care se produc. Pe fiecare dintre următoarele m linii se află câte două numere naturale x şi y, 1≤x,y≤n, separate printr-un spaţiu, cu semnificaţia "particula x intră în coliziune cu particula y".
Date de ieşire
Fişierul de ieşire nor.out va conţine pe prima linie un număr natural k, reprezentând numărul minim de picături necesare pentru formarea unui nor Cumulonimbus.
Pe cea de a doua linie vor fi scrise k numere naturale aflate în ordine descrescătoare, separate prin câte un spaţiu, ce reprezintă pentru fiecare picătură care cade din nor, numărul de particule elementare ce o alcătuiesc. Fiind un an secetos se va alege soluţia cu număr maxim de picături elementare.
Restricţii
0 < n <= 15000
0 < m <= 60000
Numărul maxim de particule elementare aflate într-o picătură este mai mic de 256.
Exemple
nor.in
nor.out
Explicaţie
11 7
1 2
1 11
4 5
5 9
4 7
4 9
3 10
2
4 3
Picăturile formate:
(1,2,11),
(4,5,7,9),
(3,10)
Iar cele care pot să cadă pe pământ sunt formate din 4 respectiv 3 picături elementare
Picăturile formate: (1,2,3,4,5,6), (7,8,9,10,11), (12,13,14)
Se observă că o soluţie posibilă este formată din 6+3 picături elementare, dar se va alege soluţia cu 6+5 pentru că are număr mai mare de picături elementare
nor.in
nor.out
Explicaţie
30 7
5 7
2 3
10 14
14 6
9 15
7 30
3 2
0
Picăturile formate:
(2,3),
(5,7,30), (6,10,14),
(9,15)
Nu sunt suficiente pentru a forma un nor Cumulonimbus
Ştiaţi că un nor Cumulonimbus poate atinge o înălţime de 18 km, dublul Everestului şi poate conţine peste o jumătate de milion de tone de apă!