#include <iostream>
#include <vector>
#include <list>
#include <utility>
#include <algorithm>
using namespace std;

//hakimi-havel
//sortare si permutatie in acelasi timp

vector<int> d={1,1,2,3,0,5,1,1,4};
int n=9;
typedef vector<list<int> > graf;

int main()
{
    graf g(n);
    vector<int> perm(n);
    for(int i=0; i<n; i++) perm[i]=i;
    for(int i=0; i<n; i++)
    {
        int dmax=-1; //calculam gradul maxim
        for(int j=i; j<n; j++) if(d[j]>dmax) dmax=d[j];

        vector<list<int> > grad(dmax+1); //grad[k] = lista de varfuri cu gradul k
        for(int j=i; j<n; j++)
            grad[d[j]].push_back(perm[j]);

        int c=i;
        for(int k=dmax; k>=0; k--)
        {
            for(list<int>::iterator it=grad[k].begin(); it!=grad[k].end(); it++)
            {
                d[c]=k;
                perm[c]=*it;
                c++;
            }
        }
        cout<<i<<endl;
            cout<<"perm\n";
            for(int k=0; k<n; k++) cout<<perm[k]<<' ';
            cout<<"\nd\n";
            for(int k=0; k<n; k++) cout<<d[k]<<' ';
            cout<<endl;
        //varful in pozitia i = varful de grad maxim
        if(d[i]>0&&(i+d[i]>=n || d[i+d[i]]==0))
        {

            cout<<"\nnu este o secventa grafica\n";
            break;
        }
        else
            for(int j=i+1; j<=i+d[i]; j++)
            {
                g[perm[i]].push_back(perm[j]);
                g[perm[j]].push_back(perm[i]);
                d[j]--;
            }
    }

    for(int i=0; i<n; i++) //afisare
        {
            cout<<i+1<<": ";
            for(list<int>::iterator it=g[i].begin(); it!=g[i].end(); it++)
            {
                cout<<*it<<' ';
            }
            cout<<endl;
        }
    return 0;
}