//i682, S�meghi N�ndor, 12.B, Budapesti Fazekas Mih�ly Gyakorl� �ltal�nos Iskola �s Gim�zium, GNU GCC Compiler
#include <bits/stdc++.h>
//a feladat val�sz�n�leg nehezebb, mint els�re t�nik, v�gs� soron a k�rd�s egy gr�f kromatikus sz�ma - np probl�ma - hossz� a fut�sid�
using namespace std;


struct konyvek
{
    vector<set<int>> graf;//graf[n] - n "nev�" szerz� szomsz�djai
    vector<int> polc;
    konyvek(int n) : polc(n) {}
};

konyvek be()
{
    int seged;
    cin>>seged;//els� sor
    konyvek konyv(seged);//l�trehozza a k�nyvet �s azon bel�l a polc hossz�t
    cin>>konyv.polc[0];//Az els�t kivessz�k, k�nnyebs�g kedv��rt
    konyv.graf.resize(konyv.polc[0]+1);
    for (int i=1; i<konyv.polc.size(); i++)
    {
        cin>>konyv.polc[i];// a polc anyiadik tagja
        if (konyv.graf.size()<konyv.polc[i]+1) konyv.graf.resize(konyv.polc[i]+1);//Ha a gr�f t�l kicsi, akkor �tm�retezi a jelenlegi szerz�re
        konyv.graf[konyv.polc[i-1]].insert(konyv.polc[i]);//Az el�z�nek a szomsz�dja a jelenlegi
        konyv.graf[konyv.polc[i]].insert(konyv.polc[i-1]);//A jelenlegi szomsz�dja az el�z�
    }
    return konyv;
}


//Lehet-e az adott kromatikus sz�mmal?
bool kromjo(int kszam, int el, const vector<set<int>>& graf, vector<int>& szin)
{
    if (el+1==graf.size()) return true;//Ha az utols� elem is belement �s megh�vta mag�t m�gegyszer
    //else if (graf[el+1].empty()&&kromjo(kszam, el+1, graf, szin)) return true;//Ez figyel arra, hogy �res-e, ha igen, megh�vja a k�vetkez�t
    for (int i=0; i<kszam; i++)//v�gigmegy az �sszes sz�nen k-ig
    {
        bool jo=1;
        for(int szom : graf[el+1])//v�gigmegy a szomsz�dokon
        {
            if (szom<el+1&&szin[szom]==i)//ha a szomsz�d m�r kapott sz�nt �s ez a sz�n annak ellentmondana
            {
                jo=0;
                break;
            }
        }
        if (jo)//Ha a jelenlegi sz�n nem �tk�zik a szomsz�dokkal
        {
            szin[el+1]=i;//megkapja a sz�nt
            if (kromjo(kszam, el+1, graf, szin)) return true;//Megh�vja mag�t a k�vetkez� szerz�re
            szin[el+1]=-1;//Ha nem j�, akkor megy tov�bb a sz�nez�s n�lk�l
        }
    }
    //Ide csak akkor juthat el, ha m�r v�gigment minden konstrukci�n -->
    return false;
}
//A f�gv�ny el�sz�r megn�zi, hogy besz�nezett-e m�r minden elemet, ha igen, akkor igazat ad vissza
//Ezut�n, ha az �ppen vizsg�lt szerz� �res, akkor megh�vja mag�t a k�vetkez� szerz�re, ami ha igaz, akkor igazat ad vissza
//Ha ezekb�l egyik se igaz, elkezd v�gigmenni az �sszes k-n, egy olyan k-t keresve, ami az adott tag lehet
//Ha lehets�ges, akkor ezt elmenti �s megh�vja mag�t a k�vetkez� gr�ftagra, ha az igaz, igazat ad vissza
//Ezut�n kit�rli mag�t a sz�nb�l
//Ha v�gigment az �sszes sz�nen �s egyiket sem tal�lta helyesnek, akkor hamisat ad vissza, ezzel jelezve, hogy a jelenlegi konstrukci�ban � az egyik sem lehet
//Ezzel a f�ggv�ny v�gigvizsg�lja az �sszes elemre az adott k-t �s ha tal�l egy j� kontrukci�t, azonnal igazat ad vissza


//Kromatiku sz�m fels� hat�r�rt�k
int kfel(const vector<set<int>>& graf)
{
    int kmax=1;
    vector<int> szin(graf.size(), -1);
    for (int i=0; i<graf.size(); i++)
    {
        if (graf[i].empty()) continue;
        for (int k=0; k<kmax; k++)
        {
            bool jo=1;
            for(int szomsz : graf[i])//v�gigmegy�nk a szomsz�dokon
            {
                if (szomsz<i&&szin[szomsz]==k)//Ha a szomsz�dnak m�r adtunk sz�nt �s az egyezik
                {
                    jo=0;
                    break;
                }
            }
            if (jo)
            {
                szin[i]=k;
                break;
            }
        }
        if (szin[i]==-1)
        {
            kmax++;
            szin[i]=kmax-1;
        }
    }
    return kmax;
}


//Minimum kromatikus sz�m keres�
int kromatikusszam(const vector<set<int>>& graf)
{
    int kmax = kfel(graf);

    for (int k = 1; k <= kmax; k++)
    {
        vector<int> szin(graf.size(), -1);
        if (kromjo(k, -1, graf, szin))
            return k;
    }
    return kmax; // ez nem szabadna megt�rt�njen
}

struct eredmeny
{
    int k;
    vector<int> polc, szinossz;
    eredmeny(int k, vector<int> polc, vector<int> szinossz) : k(k), polc(polc), szinossz(szinossz) {}
    void ki()
    {
        cout<<k-1<<endl;
        for (int i=0; i<szinossz.size(); i++)
        {
            if (szinossz[i]!=0) cout<<szinossz[i]<<" ";
        }
        cout<<endl;
        for (int i=0; i<polc.size(); i++) cout<<polc[i]+1<<" ";
        cout<<endl;
    }
};


vector<int> sorrendezo(vector<int> polc)
{
    int legk=0;
    //for(int i=0; i<polc.size(); i++) cout<<polc[i]<<" "; - debug
    //cout<<endl;
    if (polc[0]>0)
    {
        int csere=polc[0];
        for (int j=0; j<polc.size(); j++)
        {
            if (polc[j]==0) polc[j]=csere;
            else if (polc[j]==csere) polc[j]=0;
        }
    }
    //for(int i=0; i<polc.size(); i++) cout<<polc[i]<<" ";
    //cout<<endl;
    for(int i=1; i<polc.size(); i++)
    {
        if (polc[i]==legk+1) legk++;//Ha a legkisebbn�l eggyel nagyobb, akkor j�, legk eggyel t�bb lesz
        else if (polc[i]>legk)
        {
            int csere=polc[i];
            for(int j=i; j<polc.size(); j++)
            {
                if (polc[j]==legk+1) polc[j]=csere;
                else if (polc[j]==csere) polc[j]=legk+1;
            }
        }
    }
    //for(int i=0; i<polc.size(); i++) cout<<polc[i]<<" ";
    //cout<<endl;
    return polc;
}


vector<int> polckonv(int k, vector<int> polc, const vector<set<int>>& graf)
{
    vector<int> szin(graf.size(), -1);
    kromjo(k, -1, graf, szin);//Ez val�j�ban l�tre is hozza a j� megold�st
    for (int i=0; i<polc.size(); i++)//a polcot besz�nezi
    {
        polc[i] = szin[polc[i]];
    }
    return sorrendezo(polc);

}//Megjelent egy olyan probl�ma, hogy nem mindig j� sz�mmal kezd, mert ha az els� szerz� nem a legkisebb, akkor hiba lesz. Erre meg�rom a sorrendez� f�ggv�nyt


vector<int> hanyszin(const vector<int>& szin, int k)
{
    vector<int> szinossz(k);
    for (int i=0; i<szin.size(); i++) if (0 <= szin[i] && szin[i] < k) szinossz[szin[i]]++;
    return szinossz;
}

int main()
{
    konyvek adat=be();
    int k=kromatikusszam(adat.graf)+1;
    vector<int> polcszin=polckonv(k, adat.polc, adat.graf);
    eredmeny menj(k, polcszin, hanyszin(polcszin, k));
    menj.ki();
}