#include <stdio.h>

/* Depth-first search on directed graph, p. 478 in CLR */

#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 dfsNumber[VERTEXMAX],maxDescendant[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 nextDFS;  /*Keeps node numbering*/

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

vertexStatus[u]=GRAY;
descendant=maxDescendant[u]=dfsNumber[u]=(++nextDFS);

for (i=firstEdge[u];i!=(-1);i=nextNode[i])
{
  v=head[i];
  if (vertexStatus[v]==WHITE)
  {
    edgeType[i]=TREE;
    descendant=maxDescendant[u]=DFSvisit(v);
  }
  else if (vertexStatus[v]==GRAY)
    edgeType[i]=BACK;
  else if (dfsNumber[u]<dfsNumber[v])
    edgeType[i]=FORWARD;
  else
    edgeType[i]=CROSS;
}
vertexStatus[u]=BLACK;
return descendant;
}

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

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

/*Input code*/
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 (i=0;i<numVertices;i++)
  vertexStatus[i]=WHITE;
nextDFS=0;
for (i=0;i<numVertices;i++)
  if (vertexStatus[i]==WHITE)
    maxDescendant[i]=DFSvisit(i);

/*Output code*/
printf("Vertex DFSnumber maxDescendant\n");
for (i=0;i<numVertices;i++)
  printf(" %3d      %3d       %3d\n",i,dfsNumber[i],maxDescendant[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));
}
}