#include<iostream>

#include<cstdio>

#include<cstring>

#include<string>

#include<map>

#include<vector>

#include<stack>

#include<set>

#include<map>

#include<queue>

#include<algorithm>

#include<cmath>

#define LL long long

#define sint short int

//#pragma comment(linker, "/STACK:1024000000,1024000000")

using namespace std;

const int N=105;

const int INF=0x3f3f3f3f;

int head[N],I;

struct node

{

    int j,next;

}side[N*N];

int d[N];//等級

int v[N];//屬于第幾個聯(lián)通圖

int M[N],s[N],m;//m,有幾個聯(lián)通圖 s[]第幾個聯(lián)通圖最好以第幾個點為起點 M[]最大差距

void add(int i,int j)

{

    side[I].j=j;

    side[I].next=head[i];

    head[i]=I++;

}

void dfs(int x,int k)

{

    v[x]=k;

    for(int t=head[x];t!=-1;t=side[t].next)

    {

        int j=side[t].j;

        if(v[j]==-1)

        {

            dfs(j,k);

        }

    }

}

int bfs(int x1,int st)

{

    queue<int>qt;

    qt.push(x1);

    d[x1]=st;

    int k=0;

    while(!qt.empty())

    {

        int x=qt.front();

        qt.pop();

        k=max(k,d[x]);

        for(int t=head[x];t!=-1;t=side[t].next)

        {

            int j=side[t].j;

            if(v[j]!=v[x])

            continue;

            if(d[j]!=0&&abs(d[j]-d[x])!=1)

            return -1;

            if(d[j]!=0&&abs(d[j]-d[x])==1)

            continue;

            d[j]=d[x]+1;

            qt.push(j);

        }

    }

    return (k-st);

}

int main()

{

    //freopen("data.in","r",stdin);

    int n,p;

    while(cin>>n>>p)

    {

        memset(head,-1,sizeof(head));

        I=0;

        while(n--)

        {

            int l,r;

            cin>>l>>r;

            add(l,r);

            add(r,l);

        }

        memset(v,-1,sizeof(v));

        m=0;

        for(int i=1;i<=p;++i)

        if(v[i]==-1)

        dfs(i,m++);

        memset(M,-1,sizeof(M));

        memset(s,-1,sizeof(s));

        for(int i=1;i<=p;++i)

        {

            memset(d,0,sizeof(d));

            int k=bfs(i,1);

            if(k!=-1)

            {

                int l=v[i];

                if(k>M[l])

                {M[l]=k;s[l]=i;}

            }

        }

        bool flag=true;

        for(int i=0;i<m;++i)

        if(M[i]==-1)

        flag=false;

        if(flag==false)

        {cout<<"-1"<<endl;continue;}

        memset(d,0,sizeof(d));

        if(m==1)

        {

            cout<<M[0]<<endl;

            bfs(s[0],1);

        }else

        {

            cout<<"49"<<endl;

            bfs(s[0],1);

            for(int i=1;i<m;++i)

            bfs(s[i],50-M[i]);

        }

        for(int i=1;i<=p;++i)

        cout<<d[i]<<" ";

        cout<<endl;

    }

    return 0;

}