#include <utility>
#include <vector>
#include <queue>
#include <fstream>
#include <algorithm>
#include <stack>
using namespace std;
class graph {
int n, m;
std::vector<int> sel;
std::vector<std::vector<int>> nodes_list;
vector<int> topological_order;
bool has_cycle = false;
vector<vector<int>> strongly_connected_components;
void auxiliary_dfs (int start, vector<int> &DF);
void auxiliary_dfs2 (int start);
public:
graph(int n, int m, std::vector<std::vector<int>> nodes_list);
graph(const vector<vector<int>>& edges, int n, int m);
graph() : n(0), m(0) {}
void dfs (const int &start);
int number_of_components();
vector<vector<int>> get_bipartition ();
bool check_bipartite ();
bool check_dfs (vector<int> permutation);
vector<int> findOrder(vector<vector<int>>& edges);
vector<int> get_cycle();
vector<vector<int>> get_strongly_connected_components();
void
auxiliary_dfs3(int start, vector<bool> &on_stack, vector<int> &low_link_value, stack<int> &stack, vector<int> &id,
int ¤t_id);
};
graph::graph (int n, int m, std::vector<std::vector<int>> nodes_list) : n(n), m(m), nodes_list(std::move(nodes_list)){
sel.resize(n + 1, 0);
}
graph::graph(const vector<vector<int>>& edges, int n, int m = 0) : n(n), m(m) {
if (!m) m = edges.size();
nodes_list.resize(n + 1);
sel.resize(n + 1, 0);
for (auto edge : edges) {
nodes_list[edge[0]].push_back(edge[1]);
// nodes_list[edge[1]].push_back(edge[0]);
}
}
void graph::dfs (const int &start) {
sel[start] = 1;
for (auto vecin : nodes_list[start]) {
if (!sel[vecin]) dfs(vecin);
}
}
int graph::number_of_components () {
int number_of_components = 0;
for (int i = 1; i <= n; ++i) {
if (!sel[i]) {
++number_of_components;
dfs(i);
}
}
sel.resize(n + 1, 0);
return number_of_components;
}
vector<vector<int>> graph::get_bipartition () {
vector<int> color(n + 1, -1);
vector<int> color0; /// nodurile colorate cu culoarea 0
vector<int> color1; /// nodurile colorate cu culoarea 1
queue<int> BF;
for (int i = 1; i <= n; ++i) {
if (color[i] == -1) {
BF.push(i);
color[i] = 0;
color0.push_back(i);
while (!BF.empty()) {
int current = BF.front();
BF.pop();
for (auto nbh : nodes_list[current]) {
if (color[current] == color[nbh]) return {{},{}};
if (color[nbh] == -1) {
color[nbh] = 1 - color[current];
if (color[nbh]) color1.push_back(nbh);
else color0.push_back(nbh);
BF.push(nbh);
}
}
}
}
}
vector<vector<int>> split(2);
split[0] = color0;
split[1] = color1;
return split;
}
bool graph::check_bipartite() {
auto split = get_bipartition();
return !(split[0].empty() && split[1].empty());
}
bool graph::check_dfs (vector<int> permutation) {
vector<int> pos(n + 1);
for (int i = 0; i < n; ++i)
pos[permutation[i]] = i;
for (int i = 1; i <= n; ++i) {
sort(nodes_list[i].begin(), nodes_list[i].end(), [&] (int a, int b) { return pos[a] < pos[b]; });
}
vector<int> DF;
auxiliary_dfs (permutation[0], DF);
sel.resize(n + 1, 0);
return (DF == permutation);
}
void graph::auxiliary_dfs(int start, vector<int> &DF) {
DF.push_back(start);
sel[start] = 1;
for (auto nbh : nodes_list[start]) {
if (!sel[nbh])
auxiliary_dfs(nbh, DF);
}
}
void graph::auxiliary_dfs2 (int start) {
sel[start] = 1;
for (auto nbh : nodes_list[start]) {
if (!sel[nbh]) dfs(nbh);
else if (find(topological_order.begin(), topological_order.end(), nbh) == topological_order.end()) {
has_cycle = true;
topological_order.push_back(nbh);
return;
}
}
topological_order.push_back(start);
}
vector<int> graph::findOrder(vector<vector<int>>& edges) {
for (auto edge : edges)
nodes_list[edge[1]].push_back(edge[0]);
sel.resize(n, 0);
for (int i = 0; i < n; ++i) {
if (!sel[i])
auxiliary_dfs2(i);
}
sel.resize(n + 1, 0);
if (has_cycle) {
topological_order.clear();
return {};
}
reverse(topological_order.begin(), topological_order.end());
return topological_order;
}
vector<int> graph::get_cycle () {
sel.resize(n + 1, 0);
for (int i = 0; i < n; ++i) {
if (!sel[i])
dfs(i);
}
sel.resize(n + 1, 0);
if (has_cycle) {
reverse(topological_order.begin(), topological_order.end());
return topological_order;
}
return {};
}
void graph::auxiliary_dfs3 (int start, vector<bool> &on_stack, vector<int> &low_link_value, stack<int> &stack, vector<int> &id, int ¤t_id) {
stack.push(start);
on_stack[start] = true;
id[start] = low_link_value[start] = ++current_id;
for (auto nbh : nodes_list[start]) {
if (id[nbh] == -1)
auxiliary_dfs3(nbh, on_stack, low_link_value, stack, id, current_id);
if (on_stack[nbh])
low_link_value[start] = min(low_link_value[start], low_link_value[nbh]);
}
if (id[start] == low_link_value[start]) {
vector<int> found_component;
int top = stack.top();
while (top != start) {
found_component.push_back(top);
on_stack[top] = false;
low_link_value[top] = id[start];
stack.pop();
top = stack.top();
}
found_component.push_back(start);
stack.pop();
strongly_connected_components.push_back(found_component);
}
}
vector<vector<int>> graph::get_strongly_connected_components() {
vector<int> low_link_value(n + 1, 0);
vector<int> id(n + 1, -1);
stack<int> stack;
vector<bool> on_stack(n + 1, false);
int current_id = 0;
for (int i = 1; i <= n; ++i)
if (id[i] == -1)
auxiliary_dfs3(i, on_stack, low_link_value, stack, id, current_id);
return strongly_connected_components;
}
int main()
{
ifstream fin("ctc.in");
ofstream fout("ctc.out");
vector<vector<int>> edges;
// edges = {{1 ,2},{2, 6},{6, 7},{7, 6},{3, 1},{3, 4},{2, 3},{4, 5},{5, 4},{6, 5},{5, 8},{8, 7}};
int n, m;
fin >> n >> m;
while (m--) {
int a, b;
fin >> a >> b;
edges.push_back({a, b});
}
graph meow2(edges, n, m);
auto x = meow2.get_strongly_connected_components();
fout << x.size() << '\n';
for (const auto& comp : x) {
for (auto it : comp)
fout << it << " ";
fout << '\n';
}
return 0;
}