#include <stdio.h>
#include <stdlib.h>
#include <string.h>


typedef struct {
    LinkedList **neighbors;       /* Listele de adiacenta ale grafului */
    int nodes;                    /* Numarul de noduri din graf. */
} ListGraph;


typedef struct Node {
    void *data; /* Pentru ca datele stocate sa poata avea orice tip, folosim un pointer la void. */
    struct 
    Node *next;
} Node;

typedef struct {
    Node *head;
    Node *tail;
    int size;
} LinkedList;

void add_nth_node(LinkedList *list, int n, void *new_data) {
    Node *prev, *curr;
    Node *new_node;

    if (list == NULL) {
        return;
    }

    /* n >= list->size inseamna adaugarea unui nou nod la finalul listei. */
    if (n > list->size) {
        n = list->size;
    } else if (n < 0) {
        return;
    }

    curr = list->head;
    prev = NULL;
    while (n > 0) {
        prev = curr;
        curr = curr->next;
        --n;
    }

    new_node = malloc(sizeof(Node));
    if (new_node == NULL) {
        perror("Not enough memory to add element!");
        exit(-1);
    }
    
    new_node->data = new_data;
    new_node->next = curr;
    if (prev == NULL) {
        /* Adica n == 0. */
        list->head = new_node;
    } else {
        prev->next = new_node;
    }

    if (new_node->next == NULL) {
        list->tail = new_node;
    }

    list->size++;
}

void clear_list_graph(ListGraph *graph) {
    for (int i = 0; i < graph->nodes; ++i) {
        free_list(&graph->neighbors[i]);
    }
    free(graph->neighbors);
}

void free_list(LinkedList **pp_list) {
    struct Node *currNode;

    if (pp_list == NULL || *pp_list == NULL) {
        return;
    }

    while(get_size(*pp_list) > 0) {
        currNode = remove_nth_node(*pp_list, 0);
        free(currNode);
    }

    free(*pp_list);
    *pp_list = NULL;
}


void dfs_topo_sort(ListGraph *lg, int *node, int *visited, LinkedList *result) {
    int x = *node;
    if(visited[x]) return;
    visited[x] = 1;
    for(Node* it = lg->neighbors[x]->head; it; it = it->next){
        dfs_topo_sort(lg, it->data, visited, result);
    }
    add_nth_node(result, 0, node);
}

void topo_sort(ListGraph *lg, int nodes) {
    int visited[nodes], ind[nodes];
    for(int i = 0; i < nodes; i++) visited[i] = 0;
    for(int i = 0; i < nodes; i++) ind[i] = i;

    LinkedList result;
    init_list(&result);

    for(int i = 0; i < nodes; i++){
        dfs_topo_sort(lg,&ind[i],visited, &result);
    }

    printf("Topological sort:\n");
    print_int_linkedlist(&result);
}

int main() {
    int nodes, edges;
    int color[MAX_NODES];
    int nodes_index[MAX_NODES];
    int x[MAX_NODES], y[MAX_NODES];
    ListGraph *lg = malloc(sizeof(ListGraph));

    scanf("%d %d", &nodes, &edges);
    init_list_graph(lg, nodes);
    for (int i = 0; i < nodes; ++i) {
        nodes_index[i] = i;
    }

    for (int i = 0; i < edges; ++i) {
        scanf("%d %d", &x[i], &y[i]);
        add_edge_list_graph(lg, x[i], &y[i]);
    }
     /* Ex 2 */
    topo_sort(lg, nodes);
    clear_list_graph(lg);
    free(lg);
    return 0;
}