#include <bits/stdc++.h>
using namespace std;
#define maxi 100005
ifstream in("ctc.in");
ofstream out("ctc.out");
class Graf
{
int n,m; //n- nr noduri, m- nr muchii
int x,y; //muchie stg-dr
int viz[100005]; //pt dfs
vector<int> *l;
public:
Graf();
//dfs
void citireDFS();
void dfs(int s);
void nrCompCone();
//bfs
int citireBFS();
void bfs(int s);
//toposort
void sort_top_dfs(int s, vector<int>& );
void citire_top_dfs();
void sortare_topologica();
//compTareConexe
void citire_ctc(vector<int>[],vector<int>[]);
void dfs1(int s,vector<int>[], vector<int>&,int []);
void dfs2(int s,vector<int>[], vector<int>[], int [],int);
void ctc();
//HAVEL
void havel_hakimi();
//PaduriMultDisj
void citire_paduri();
int find_radacina(int);
void unite(int, int);
void paduri();
};
Graf::Graf() {
n = m = x = y = 0;
l = new vector<int>[maxi];
//l2 = new vector<int>[maxi];
}
void Graf::citireDFS()
{
in>>n>>m;
int x,y;
for(int i =0; i<m; i++)
{
in>>x>>y;
l[x].push_back(y);
l[y].push_back(x);
}
}
void Graf:: dfs(int s)
{
viz[s]=1;
for(auto el:l[s])
{
if(viz[el]==0)
{
dfs(el);
}
}
}
void Graf::nrCompCone()
{
int c_con=0;
for(int i=1; i<=n; i++)
{
if(viz[i]==0)
{
dfs(i);
c_con++;
}
}
out<<c_con;
}
int Graf :: citireBFS()
{
int s;
in>>n>>m>>s;
int x,y;
for(int i =0; i<m; i++)
{
in>>x>>y;
l[x].push_back(y);
}
return s;
}
void Graf::bfs(int s)
{
//int vizitat[10000];
queue<int> q;
int dist[100005];
for(int i =1; i<=n; i++)
{
dist[i]=-1;
}
int v;
q.push(s);
viz[s] = 1;
dist[s]=0;
while(!q.empty())
{
v=q.front();
for(auto el:l[v])
{
if(dist[el]==-1)
{
q.push(el);
viz[el]=1;
dist[el]=dist[v]+1;
}
}
q.pop();
}
for(int i = 1; i<=n; i++)
{
out << dist[i]<<' ';
}
}
void Graf :: citire_top_dfs()
{
in>>n>>m;
int x,y;
for(int i=0;i<m;i++)
{
in>>x>>y;
l[x].push_back(y);
}
}
void Graf::sort_top_dfs(int s, vector<int> &sortop)
{
viz[s]=1;
for(auto el:l[s])
{
if(viz[el]==0)
{
sort_top_dfs(el, sortop);
}
}
sortop.push_back(s);
}
void Graf::sortare_topologica()
{
vector <int> sortop;
for(int i=1; i<=n; i++)
{
if(viz[i]==0)
{
sort_top_dfs(i, sortop);
}
}
reverse(sortop.begin(),sortop.end());
for(int i:sortop)
{
out<<i<<" ";
}
}
//CTC
void Graf::citire_ctc(vector<int>graf1[],vector<int>graf2[])
{
in>>n>>m;
int x,y;
for(int i=0;i<m;i++)
{
in>>x>>y;
graf1[x].push_back(y);
graf2[y].push_back(x);
}
}
void Graf::dfs1(int s,vector<int>graf1[], vector<int> &sortop, int viz1[])
{
viz1[s]=1;
for(auto el:graf1[s])
{
if(viz1[el]==0)
{
dfs1(el,graf1, sortop,viz1);
}
}
sortop.push_back(s);
}
void Graf::dfs2(int s,vector<int>graf2[], vector<int> comp[], int viz2[],int comp_curenta)
{
viz2[s] = 1;
comp[comp_curenta].push_back(s);
for(auto el:graf2[s])
{
if(viz2[el]==0)
{
dfs2(el,graf2,comp,viz2,comp_curenta);
}
}
}
void Graf::ctc()
{
int *viz1 = new int [100005];
int *viz2 = new int [100005];
for(int i=0; i<100005; ++i)
{
viz1[i]=0;
}
for(int i=0; i<100005; ++i)
{
viz2[i]=0;
}
vector <int> *graf1 = new vector<int>[100005];
vector <int> *graf2 = new vector<int> [100005];
int comp_curenta=0;
vector <int> sortop;
vector <int> *comp = new vector<int> [100005];
citire_ctc(graf1,graf2);
for(int i=1; i<=n; i++)
{
if(viz1[i]==0)
{
dfs1(i,graf1,sortop,viz1);
}
}
reverse(sortop.begin(),sortop.end());
for(int i:sortop)
{
if(viz2[i]==0)
{
dfs2(i,graf2,comp,viz2,comp_curenta);
comp_curenta++;
}
}
out<<comp_curenta<<'\n';
for(int i=0; i<comp_curenta; i++)
{
for(int j = 0; j < comp[i].size(); j++)
{
out<<comp[i][j]<<" ";
}
out<<'\n';
}
}
//HAVEL HAKIMI
void Graf::havel_hakimi()
{
vector <int> v;
int from, to;
in>>n;
int i;
for(i=0;i<n;i++)
{
int w;
in>>w;
v.push_back(w);
}
sort(v.begin(), v.end());
for(from = n-1; from>=0; from--)
{
for(to = from -1; to >=0; to--)
{
if(v[to]>0 && v[from]>0)
{
v[from]--;
v[to]--;
}
}
if(v[from]>0)
{
out<<"Nu";
break;
}
sort(v.begin(), v.begin()+from+1);
}
out<<"Da";
}
int main()
{
/*Graf g4;
g4.havel_hakimi();
*/
//CTC
Graf g5;
g5.ctc();
/*
//SORTOP
Graf g3;
g3.citire_top_dfs();
g3.sortare_topologica();
*/
/*
BFS
int ss; //stocheaza ce returneaza citirea (nodul s initial)
Graf g2;
ss=g2.citireBFS();
g2.bfs(ss);
*/
/*
DFS
Graf g1;
g1.citireDFS();
g1.nrCompCone();
*/
return 0;
}