#include <stdio.h>

/* Depth-first search on directed graph, p. 541 in CLRS */

#define VERTEXMAX 40
#define EDGEMAX VERTEXMAX*VERTEXMAX

enum vertexStatusEnum {WHITE,GRAY,BLACK};
enum edgeEnum {TREE,CROSS,BACK,FORWARD};

int numVertices,numEdges;
enum vertexStatusEnum vertexStatus[VERTEXMAX];
int discovery[VERTEXMAX],finish[VERTEXMAX],predecessor[VERTEXMAX];

int firstEdge[VERTEXMAX];  /*Points to first edge for vertex as tail*/

/*These 3 arrays are used together for adjacency list nodes*/
int head[EDGEMAX];
enum edgeEnum edgeType[EDGEMAX];
int nextNode[EDGEMAX];

int time;  /*Keeps node numbering*/

int DFSvisit(u)
int u;
{
int i,v;

vertexStatus[u]=GRAY;
time++;
discovery[u]=time;

for (i=firstEdge[u];i!=(-1);i=nextNode[i])
{
  v=head[i];
  if (vertexStatus[v]==WHITE)
  {
    edgeType[i]=TREE;
    predecessor[v]=u;
    DFSvisit(v);
  }
  else if (vertexStatus[v]==GRAY)
    edgeType[i]=BACK;
  else if (discovery[u]<discovery[v])
    edgeType[i]=FORWARD;
  else
    edgeType[i]=CROSS;
}
vertexStatus[u]=BLACK;
time++;
finish[u]=time;
}

main()
{
int u,i,j,k,lastTail,tail;

scanf("%d %d",&numVertices,&numEdges);

/*Input code - assumes edges are sorted*/
for (i=0;i<numVertices;i++)
  firstEdge[i]=(-1);
lastTail=(-1);
for (i=0;i<numEdges;i++)
{
  scanf("%d %d",&tail,&head[i]);
  if (lastTail==tail)
    nextNode[i-1]=i;
  else
  {
    if (lastTail!=(-1))
      nextNode[i-1]=(-1);
    firstEdge[tail]=i;
    lastTail=tail;
  }
}
nextNode[i-1]=(-1);

/*DFS code*/
for (u=0;u<numVertices;u++)
{
  vertexStatus[u]=WHITE;
  predecessor[u]=(-1);
}
time=0;
for (u=0;u<numVertices;u++)
  if (vertexStatus[u]==WHITE)
    DFSvisit(u);

/*Output code*/
printf("Vertex  discovery    finish     predecessor\n");
for (i=0;i<numVertices;i++)
  printf(" %3d      %3d         %3d          %3d\n",i,
    discovery[i],finish[i],predecessor[i]);
printf("Edge Tail Head Type\n");
tail=0;
while (firstEdge[tail]==(-1))
  tail++;
for (i=0;i<numEdges;i++)
{
  printf(" %3d  %3d  %3d  ",i,tail,head[i]);
  switch(edgeType[i])
  {
    case TREE:    printf("tree\n"); break;
    case BACK:    printf("back\n"); break;
    case CROSS:   printf("cross\n"); break;
    case FORWARD: printf("forward\n"); break;
  }
  if (nextNode[i]==(-1))
    do
    {
      tail++;
    }
    while (firstEdge[tail]==(-1));
}
}