#include <iostream>
#include <vector>
#include <queue>
#include <fstream>
#include <stack>
#include <algorithm>

using namespace std;
#define Nmax 100007
#define Rezolvare 1

const char iname[] = "bfs.in";
const char oname[] = "bfs.out";


vector<int> rev[Nmax];
vector<int> aux;
ifstream f(iname);
ofstream g(oname);

class Graph{
public:
    Graph(int n, int m);
    ~Graph();
    virtual void add_muchie(int x, int y){}
    bool is_correct_graph(vector<int> grade);
private:

protected:
    vector<int> la[Nmax]; //lista de adiacenta;
    int n,m; //numarul de noduri si numarul de muchii
};

bool Graph::is_correct_graph(vector<int> grade)
{
    sort(grade.begin(),grade.end(),greater <int>());
    while(grade[0]!=0)
    {
        int v=grade[0];
        grade.erase(grade.begin()+0);
        if(v>grade.size())
            return false;
        for(int i=0;i<v;i++)
        {
            grade[i]--;
            if(grade[i]<0)
                return false;
        }
        sort(grade.begin(),grade.end(),greater <int>());
    }
    return true;
}

class Undirected: public Graph{
public:
     Undirected(int n, int m);
     ~Undirected();
     void add_muchie(int x,int y)
     {
         la[x].push_back(y);
         la[y].push_back(x);
     }
     void dfs(int start,int visited[]);

private:

};

int nr_conex=0;
void Undirected::dfs(int start,int visited[])
{
  visited[start] = nr_conex;
  for(auto i:la[start])
  {
      if(!visited[i])
        dfs(i,visited);
  }
}
 Undirected::Undirected(int n, int m): Graph(n,m)
{

}
Undirected::~Undirected()
{

}

class Directed: public Graph{
public:
     Directed(int n,int m);
     ~Directed();
     void add_muchie(int x,int y);
     void bfs(int start, int visited[],int dist[]);
     void findCTC();
     void reverse();
     void topologic();
private:
    void dfs_plus(int i,stack<int> &my_stack,int visited[]);
    void dfs_reverse(int i,vector <int>& aux,int visited[]);
    //void dfs_topologic(int i,stack <int>&Stack,int visited[]);
};

void Directed::topologic()
{
    stack <int> Stack;
    int visited[n];
    for(int i=1; i<=n;i++)
        visited[i]=0;

    for(int i=1;i<=n;i++)
        if(visited[i]==0)
           dfs_plus(i,Stack,visited);
    while(!Stack.empty())
        {
         g<<Stack.top()<<" ";
          Stack.pop();
        }
}


void Directed::dfs_reverse(int i,vector <int>& aux,int visited[])
    {
        visited[i]=1;
        for(auto j:rev[i])
        {
            if(!visited[j])
                dfs_reverse(j,aux,visited);
        }
        aux.push_back(i);
    }
void Directed::findCTC()
     {
         int visited[n];
         vector< vector<int> > sol;
         for(int i=1;i<=n;i++)
            visited[i]=0;
         stack<int> my_stack;
         for(int i=1;i<=n;i++)
            if(!visited[i])
                dfs_plus(i,my_stack,visited);



        for(int i=1;i<=n;i++)
            visited[i]=0;
        int scc = 0;

         while(!my_stack.empty())
         {

             int cur = my_stack.top();
             my_stack.pop();
             if(!visited[cur])
                {
                    aux = vector<int>();
                    dfs_reverse(cur,aux,visited);
                    sol.push_back(aux);
                    scc++;
                }
         }
         g<<scc<<"\n";
         cout<<sol[1].size();
         for(int i=0;i<sol.size();i++)
         {
             for(int j=0;j<sol[i].size();j++)
                g<<sol[i][j]<<" ";
          g<<"\n";
         }
     }

void Directed::reverse()
{
    for(int i=1;i<=n;i++)
    {
        for(int j:la[i])
            rev[j].push_back(i);
    }
}

void Directed::dfs_plus(int i,stack<int> &my_stack,int visited[])
{
    visited[i]=1;
    for(int j:la[i])
    {
        if(!visited[j])
            dfs_plus(j,my_stack,visited);
    }
    my_stack.push(i);
}
Directed::Directed(int n, int m): Graph(n,m)
{

}
Directed::~Directed()
{

}
void Directed::add_muchie(int x,int y)
{
    la[x].push_back(y);
}

void Directed::bfs(int start, int visited[],int dist[]){
    queue <int> coada;
    visited[start]=true;
    coada.push(start);
    dist[start] = 0;
    while(!coada.empty())
    {   start = coada.front();
        coada.pop();
        for(auto i:la[start])
        {
            if(!visited[i])
            {
                visited[i] = true;
                coada.push(i);
                dist[i]=dist[start]+1;
            }
        }
    }
}
Graph::Graph(int n=0, int m=0):n(n),m(m)
{

}
Graph::~Graph()
{

}



int main()
{
    int n,m,s;
    int x,y;
    switch(Rezolvare)
    {

    case 1:
    {
     f>>n>>m>>s;
     Directed grf(n,m);
     for(int i=0;i<m;i++)
     {
      f>>x>>y;
      grf.add_muchie(x,y);
     }
     f.close();
     int visited[n],dist[n];
     for(int i=0;i<=n;i++)
        visited[i]=dist[i]=0;
     grf.bfs(s,visited,dist);
     for(int i=1;i<=n;i++)
     {
         if(visited[i])
            g<<dist[i]<<" ";
        else g<<-1<<" ";
     }
        break;
    }
    case 2:
    {
     f>>n>>m;
     Undirected grf(n,m);
     int visited[n];
     for(int i=0;i<m;i++)
      {
      f>>x>>y;
      grf.add_muchie(x,y);
      }
     for(int i=0;i<=n;i++)
        visited[i]=0;
       for(int i=1;i<=n;i++)
        if(!visited[i])
         {
             nr_conex++;
             grf.dfs(i,visited);
         }
    g<<nr_conex;
    break;
    }
    case 3:
    {

     f>>n>>m;
     Directed grf(n,m);

     for(int i=0;i<m;i++)
     {
         f>>x>>y;
         grf.add_muchie(x,y);
     }
     grf.reverse();

     grf.findCTC();
     break;
    }
    case 4:
 {vector<int> check;
   int number;
   cin>>number;
   for(int i=0;i<number;i++)
   {
       int c;
       cin>>c;
       check.push_back(c);
   }
   Graph grf(n);
   if(grf.is_correct_graph(check))
     cout<<"DA";
   else cout<<"NU";
    }
    case 5:
        {
     f>>n>>m;
     Directed grf(n,m);

     for(int i=0;i<m;i++)
     {
      f>>x>>y;
      grf.add_muchie(x,y);
     }

     f.close();
     grf.topologic();
        }
    }
    g.close();
    return 0;
}