| Fişierul intrare/ieşire: | sali.in, sali.out | Sursă | FMI No Stress 10 |
| Autor | Lucian Bicsi | Adăugată de |  FMI No Stress 9 •fminostress9 |
| Timp execuţie pe test | 0.25 sec | Limită de memorie | 64536 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Sali
În căutare de modalităţi de a obţine bani de buzunar pentru a-ţi face viaţa de student mai plăcută, ai găsit pe un site de anunţuri postul de "ajutor administrator sistem informatic şcoală", la care te-ai şi angajat. Desigur, pe timp de pandemie, ajutarea în administrarea şcolilor este mai dificilă decât pare.
Mai exact, acum se doreşte împărţirea unei clase de N elevi în mai multe săli (de capacitate presupusă infinită) de-a lungul unui coridor lung (presupus infinit), pentru a promova distanţarea socială. Din păcate însă, între cei N elevi există M relaţii de prietenie (bineînţeles, bidirecţionale), iar doi prieteni nu vor fi de acord cu planul de împărţire, decât dacă aceştia vor fi repartizaţi în aceeaşi sală sau, cel mult, în săli adiacente. Mai exact, doi prieteni i şi j vor fi de acord cu planul de împărţire dacă şi numai dacă |s(i) - s(j)| ≤ 1 ( s(i) reprezintă indicele sălii la care va fi atribuit elevul cu numărul i, iar |x| reprezintă modulul numărului întreg x ).
Pentru a respecta cât mai îndeaproape normele de distanţare socială, trebuie ca elevii să fie repartizaţi în cât mai multe săli.
Sarcina ta este de a concepe un sistem informatic care să determine numărul maxim de săli în care pot fi repartizaţi, astfel încât toţi elevii să fie de acord cu planul de împărţire şi, de asemenea, un astfel de plan.
Date de intrare
Fişierul de intrare sali.in conţine pe prima linie două numere naturale N şi M, cu specificaţiile din enunţ.
Pe următoarele M linii se vor afla câte două numere naturale a şi b ( 1 ≤ a, b ≤ N ), descriind relaţiile de prietenie.
Date de ieşire
În fişierul de ieşire sali.out se va regăsi pe prima linie un număr natural K, numărul maxim de săli în care pot fi repartizaţi.
Pe a doua linie se vor regăsi N numere naturale din intervalul [1..K]. Al i-lea număr va reprezenta indicele sălii atribuite elevului cu numărul i.
Restricţii
- 1 ≤ N ≤ 1000
- 1 ≤ M ≤ 10000
- Toate perechile din fişierul de intrare sunt distincte
- Pentru fiecare pereche (i, j), avem că i ≠ j
- Pentru ca soluţia afişată să fie corectă, trebuie ca fiecare dintre cele K săli să conţină măcar un elev
Exemplu
| sali.in | sali.out |
|---|---|
| 4 3 1 2 2 3 3 4 | 4 1 2 3 4 |
| 6 6 1 2 2 3 3 1 4 5 5 6 6 4 | 4 1 2 2 4 4 3 |
