dicsi

Dicsi

== include(page="template/taskheader" task_id="dicsi") ==

Poveste şi cerinţă...

h3. _Ştiti cum plâng copiii mici? WEEEEEEE_
 
Toata lumea îl ştie pe celebrul personaj, Dicsi. Acesta tocmai a aflat că are $N$ copii (cu o fată specială). Deoarece Dicsi este un familist, acesta îşi doreşte să işi cunoască copiii mai bine, însă acest lucru nu este foarte uşor întrucât Dicsi are foarte mulţi copii ( $N ≤ 100.000$ ). Fiind un informatician înnăscut, Dicsi a luat $2$ măsuri:
 
* Toţi copiii au fost numerotaţi cu indici distincţi de la $1$ la $N$
* Fiecare copil a fost colorat cu câte o culoare.
 
Doi copii se consideră ca seamănă între ei dacă indicele unuia este divizor al indicelui celuilalt. Dicsi nu vrea să coloreze doi copii care seamănă între ei cu aceeaşi culoare deoarece după i-ar confunda. Ajutaţi-l pe Dicsi să determine numărul minim de culori necesar acestuia să îşi colorze copiii astfel încât să nu îi confunde, precum şi o colorare validă.

h2. Date de intrare

Fişierul de intrare $dicsi.in$ ...

Fişierul de intrare $dicsi.in$ va conţine un singur număr natural $N$, reprezentând numărul de copii.

h2. Date de ieşire

În fişierul de ieşire $dicsi.out$ ...

Fişierul de ieşire $dicsi.out$ va conţine pe prima linie un număr $X$, reprezentând numărul minim de culori necesar. Pe linia a doua se vor afişa $N$ numere naturale din intervalul $[1...X]$, al $i$-lea element reprezentând culoarea celui de al $i$-lea copil. Dacă există mai multe soluţii, puteţi afişa oricare dintre acestea.

h2. Restricţii

* $... ≤ ... ≤ ...$

* $1 ≤ N ≤ 100.000$

h2. Exemplu
table(example). |_. dicsi.in |_. dicsi.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

|5
|3
3 2 1 1 2

|

h3. Explicaţie
 
...
 

== include(page="template/taskfooter" task_id="dicsi") ==