#include <stdlib.h>
#include <stdio.h>
#include <string.h>
struct node
{
void* data;
struct node *next;
};
int list_add_front(struct node **head, void* val)
{
struct node *tmp;
tmp = malloc(sizeof(struct node));
tmp->data = val;
tmp->next = *head;
*head = tmp;
return 0;
}
int dfs(struct node **graph, int root, int *marked, int conr, int *order, int* oidx, struct node** out)
{
if (out)
list_add_front(out, (void *)root);
marked[root] = conr;
for(struct node* p = graph[root]; p != NULL; p = p->next)
if(!marked[(int)p->data])
dfs(graph, (int)p->data, marked, conr, order, oidx, out);
if (order != NULL)
order[(*oidx)++] = root;
return 0;
}
int main()
{
FILE *infile, *outfile;
int n, m, i;
int *order, *marked;
struct node **grapht, **graph;
int count = 0, oidx = 0;
struct node *output = NULL;
struct node *temp = NULL;
infile = fopen("ctc.in", "r");
outfile = fopen("ctc.out", "w");
fscanf(infile, "%d %d", &n, &m);
marked = malloc((n+1) * sizeof(int));
order = malloc((n+1) * sizeof(int));
graph = malloc((n+1) * sizeof(struct node*));
grapht = malloc((n+1) * sizeof(struct node*));
memset(marked, 0, (n+1) * sizeof(int));
for (i = 0; i <= n; i++) {
graph[i] = NULL;
grapht[i] = NULL;
}
for (i = 0; i < m; i++) {
int u, v;
fscanf(infile, "%d %d", &u, &v);
// add reverse
list_add_front(&grapht[v], (void *)u);
list_add_front(&graph[u], (void *)v);
}
for (i = 1; i <=n; i++)
if (!marked[i])
dfs(grapht, i, marked, 1, order, &oidx, NULL);
memset(marked, 0, (n+1) * sizeof(int));
for(i = oidx - 1; i >= 0; i--) {
if(marked[order[i]])
continue;
count++;
temp = NULL;
dfs(graph, order[i], marked, count, NULL, NULL, &temp);
list_add_front(&output, temp);
}
fprintf(outfile, "%d\n", count);
for(struct node* p = output; p != NULL; p = p->next) {
for(struct node* q = p->data; q != NULL; q = q->next)
fprintf(outfile, "%d ", (int)q->data);
fprintf(outfile, "\n");
}
fclose(infile);
fclose(outfile);
return 0;
}