== include(page="template/taskheader" task_id="sali") ==
Poveste şi cerinţă...
Î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.
h2. Date de intrare
Fişierul de intrare $sali.in$ ...
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.
h2. Date de ieşire
În fişierul de ieşire $sali.out$ ...
Î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$.
h2. 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**
h2. Exemplu
table(example). |_. sali.in |_. sali.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 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
|
h3. Explicaţie
...
== include(page="template/taskfooter" task_id="sali") ==
