#include <fstream>

using namespace std;

 ifstream x ("dfs.in");
 ofstream y ("dfs.out");

 struct node
 {
     int i;
     node *next;
 };

 int n,m;
 int k;
 int a[100001];
 node *current;
 node *temp;
 node *head[100001];

 void dfs(int i)
 {
     a[i]=k;

     if(head[i])
     {
         current=head[i];

         while(current!=NULL)
         {
             if(a[current->i]==0)
                dfs(current->i);
             current=current->next;
         }
     }
 }

int main()
{
    int i;

    x>>n>>m;

    int X,Y;

    for(i=1;i<=m;i++)
    {
        x>>X>>Y;

        if(head[X]==NULL)
        {
            head[X]=new node();

            head[X]->i=Y;
            head[X]->next=NULL;
        }
        else
        {
            current=new node();
            bool flag=true;

            current=head[X];
            while(current->next)
            {
                if(current->i==Y)
                {
                    flag=false;
                    break;
                }
                current=current->next;
            }

            if(flag==true)
            {
                temp=new node();

                temp->i=Y;
                temp->next=NULL;
                current->next=temp;
            }
        }
    }

    for(i=1;i<=n;i++)
    {
        y<<i<<" --> ";

        current=head[i];

        while(current)
        {
            y<<current->i<<' ';
            current=current->next;
        }

        y<<'\n';
    }
    y<<'\n';

    for(i=1;i<=n;i++)
       if(a[i]==0)
       {
           k++;
           dfs(i);
       }

    y<<k<<'\n';

    for(i=1;i<=n;i++)
       y<<a[i]<<' ';
    y<<'\n';

    return 0;
}