#include<iostream>
#include<queue>
#include<vector>
#include<map>
#include<algorithm>
#define INF 2000000
using namespace std;
vector<vector<int> > gr;
vector<int> d,p,v;
vector<vector<int> > ccom;
map<pair<int,int>,int> my;
int min(int i,int j){return i<j?i:j;}
void dfs(int n,int ncc)
{
    v[n]=1;
    ccom[ncc].push_back(n);
    for(int i=0;i<gr[n].size();i++) if(v[gr[n][i]]==0) dfs(gr[n][i],ncc);
}
bool check(int a,int b)
{
    return (my[make_pair(a,b)] || my[make_pair(b,a)]);
}
int bfs(int n,int val,int ud)
{
    d[n]=val;
    v[n]=1;
    p[n]=-1;
    queue<int> q;
    q.push(n);
    int i,u,ret;
    ret=val;
    while(!q.empty())
    {
        u=q.front();
        q.pop();
        for(i=0;i<gr[u][i];i++)
        {
            if(check(u,gr[u][i])) continue;
            if(v[gr[u][i]]==0)
            {
                d[gr[u][i]]=d[u]+ud;
                ret=min(ret,d[u]+ud);
                v[gr[u][i]]=1;
                p[gr[u][i]]=u;
                q.push(gr[u][i]);
            }
            else
            {
                if(d[gr[u][i]]!=d[u]+ud) return -1;
            }
            my[make_pair(u,gr[u][i])]=1;
        }
    }
    return ret;
}
int main()
{
    int m,n,i,j,k,ans,node;
    cin>>m>>n;
    gr.resize(n+1);
    for(i=0;i<m;i++)
    {
        cin>>j>>k;
        gr[j].push_back(k);
        gr[k].push_back(j);
    }
    v.resize(n+1);
    for(i=1;i<=n;i++) v[i]=0;
    int ncc=0;
    for(i=1;i<=n;i++)
    {
        if(v[i]==0)
        {
            ccom.resize(ncc+1);
            dfs(i,ncc);
            ncc++;
        }
    }
    //cout<<ccom.size();
    //cout<<ccom[0][0];
    int mn,tmp,nn;
    vector<pair<int,int> > inf;
    inf.resize(ncc);
    for(i=0;i<ncc;i++)
    {
        mn=100;
        for(j=0;j<ccom[i].size();j++)
        {
            v.clear();
            v.resize(n+1);
            d.clear();
            d.resize(n+1);
            p.clear();
            p.resize(n+1);
            my.clear();
            for(k=1;k<=n;k++) v[i]=0;
            //cout<<ccom[i][j];
            tmp=bfs(ccom[i][j],50,-1);
            if(tmp!=-1 && tmp<mn)
            {
                nn=ccom[i][j];
                mn=tmp;
            }
        }
        if(mn==100)
        {
            cout<<-1;
            return 0;
        }
        else //inf.push_back(make_pair(mn,nn));
        {
            //inf.resize(i+1);
            inf[i].first=mn;
            inf[i].second=nn;
        }
        //cout<<inf[i].first<<' '<<inf[i].second;
    }
    if(ncc==1) cout<<50-inf[0].first<<endl;
    else cout<<49<<endl;
    for(i=1;i<=n;i++) v[i]=0;
    my.clear();
    for(i=0;i<ncc;i++)
    {
        if(i!=0) bfs(inf[i].second,1,1);
        else bfs(inf[i].second,50,-1);
    }
    for(i=1;i<=n;i++) cout<<d[i]<<' ';
    return 0;
}