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

typedef struct graph {
    // Graf orientat
    int *visited, *discover_time, *finish_time;
    int nr_nodes;
    int *size;
    int **neighbours;
    int *dim;
} graph;


graph* read_graph(FILE *file) {
  graph *G =(graph*) malloc(sizeof(graph));
  int n,m,i;
  fscanf(file, "%d %d\n", &n, &m);
 
  G->nr_nodes = n;
  G->size = (int*) malloc(n * sizeof(int*));
  G->neighbours = (int**) malloc(n * sizeof(int*));
  G->dim = (int*) calloc(n, sizeof(int));
  G->discover_time = (int*) calloc(n, sizeof(int));
  G->finish_time = (int*) calloc(n, sizeof(int));
  G->visited = (int*) calloc(n, sizeof(int));
  
  for(i=0; i<n; i++) {
    G->size[i] = 10;
    G->neighbours[i] = (int*) malloc(n * sizeof(int));
  }
 
  while(m--) {
     int x, y;
     fscanf(file, "%d %d\n", &x, &y);
     x--; y--; // in fisier am de la 1
     
     if(G->dim[x]-1 == G->size[x]) {
      G->size[x] *= 2;
      G->neighbours[x] = (int*) realloc(G->neighbours[x], G->size[x] * sizeof(int));
     }
     G->neighbours[x][G->dim[x]++] = y;
  }
  return G;
}

void show_neighbours(graph *G) {
  int i, j;
  for(i=0; i<G->nr_nodes; i++) {
    printf("Nodul %d are vecinii:", i);
    for(j=0; j<G->dim[i]; j++) {
      printf(" %d", G->neighbours[i][j]);
    }
    printf("\n");
  }
}

typedef struct stack {
  int nr;
  int *v;
} stack;

void dfs(graph *G, int nod, int *time, stack *st) {
  G->visited[nod] = 1;
  G->discover_time[nod] = (*time)++;
  
  int i;
  for(i=0; i<G->dim[nod]; i++) {
    int x = G->neighbours[nod][i];
    if(G->visited[x] == 0) {
      dfs(G, x, time, st);
    }
  }
  
  G->finish_time[nod] = (*time)++;
  st->v[st->nr++] = nod;
}

void apel_dfs(graph *G, stack *st) {
  int i;
  int time=0;
  st->nr = 0;
  st->v = (int*) malloc(G->nr_nodes * sizeof(int));
  for(i=0; i<G->nr_nodes; i++) {
    if(G->visited[i] == 0) {
        dfs(G, i, &time, st);
    }
  }
}

int main()
{
  FILE *file, *file2;
  file = fopen("sortaret.in", "rt");
  file2 = fopen("sortaret.out", "wt");
  
  graph* G = read_graph(file);
  
  stack* st;
  st = (stack*) malloc(sizeof(stack));
  apel_dfs(G, st);
  
  int i;
  for(i=0; i<G->nr_nodes; i++) {
    printf("%d : %d - %d\n",i , G->discover_time[i], G->finish_time[i]);
  }
  
  // Sortarea topologica (daca graful e conex si aciclic, orientat)
  
  for(i=st->nr-1; i>=0; i--) {
    fprintf(file2, "%d ", st->v[i]+1);
  }
  
  free(st->v);
  free(st);
  
  free(G->discover_time);
  free(G->finish_time);
  free(G->size);
  free(G->visited);
  for(i=0; i<G->nr_nodes; i++) {
    free(G->neighbours[i]);
  }
  free(G->neighbours);

  fclose(file);
  fclose(file2);

  return 0;
}