La un moment dat un grup de elfi a primit vestea că fiecare dintre ei va primi straie noi. Straiele vor fi create din materiale colorate cu diferite nunțe de verde.
Din diverse motive, există perechi de elfi care nu doresc să aibe straie cu aceeași nuanță. Va trebui să se determine numărul minim k de nunțe necesare pentru a se confecționa noile straie ale elfilor din acest grup, precum și nuanța straielor fiecărui elf. Nuanțele vor fi identificate prin numere cuprinse între 1 și k, iar elfii vor fi identificați prin numere cuprinse între 1 și n.
Fișierul de intrare INPUT.TXT conține pe prima linie numărul n al elfilor care fac parte din grup.
Pe cea de-a doua linie se va afla numărul total m al perechilor de elfi care nu doresc să aibă straie confecționate din materiale colorate cu aceeași nuanță de verde. Fiecare dintre următoarele m linii conține câte două numere întregi, separate printr-un spațiu. Acestea reprezintă numerele de ordine a doi elfi care doresc ca straiele lor să fie confecționate din materiale care să aibă nuanțe diferite de verde.
Fișierul de ieșire OUTPUT.TXT trebuie să conțină pe prima linie numărul minim al nuanțelor necesare.
Fiecare dintre următoarele n linii va conține câte un număr întreg cuprins între 1 și k, care va reprezenta nuanța de verde a straielor elfului corespunzător liniei. Ordinea elfilor este dată de numerele lor de identificare.
INPUT.TXT
5 5 1 5 1 4 2 5 2 3 4 3 OUTPUT.TXT 3 1 1 2 3 2
|