//#define DEBUG

/*
 * Problema: Ilhas (Hawaianas, as legítimas)
 *
 * Autor___: Aritanan Borges Garcia Gruber (Pil)
 *
 * Data____: 18/08/2001
 *
 * Solução_: Construção de um grafo orientado que represente as rotas possíveis
 *           e determinação dos componentes fortemente conexos.
 *
 */

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

#define IF_NAME "ilhas.in"

#define MAX_NUM_VERTEX 20
#define MAX_NUM_ARCS   (MAX_NUM_VERTEX * MAX_NUM_VERTEX)

#define MallocT(v,t,l) (assert ((v = (t*) malloc (sizeof (t) * (l))) != 0))

#ifdef DEBUG
#  define D(x) x
#else
#  define D(x)
#endif

// ------------------------------------------------------------------------- //
//               Estrutura e funções de manipulação do grafo.                //
// ------------------------------------------------------------------------- //

// Definição de um vértice de uma lista ligada que armazena adjacências entre
// vértices de um grafo.
//
typedef struct _arc {
  int v;
  struct _arc* next;
} arc_t;

// Definição da estrutura de representação de um grafo orientado através
// de listas de adjacências. O número de vértices varia de acordo com a instância.
//
typedef struct {
  int nVertex;
  int*  color; // Cor associada ao vértice
  int* parent; // Pai na floresta de busca em profundidade.
  arc_t** adj; // Apontador para a lista de adjacência do vértice.
} graph_t;

// Definição das cores que cada vértice pode assumir durante uma busca em profundidade.
//
enum {
  WHITE,
  GRAY ,
  BLACK 
};

/* -- create --------------------------------------------------------------- */
/* - Cria e inicializa o grafo apontado por G.                             - */
/* ------------------------------------------------------------------------- */
graph_t* createGraph (int nVertex)
{
  int i;
  graph_t* G;

  MallocT (G, graph_t, 1);
  G->nVertex = nVertex;

  MallocT (G->color , int   , nVertex);
  MallocT (G->parent, int   , nVertex);
  MallocT (G->adj   , arc_t*, nVertex);
  
  for (i = 0; i < nVertex; i++) {
    G->color [i] = WHITE;
    G->parent[i] = i;
    G->adj   [i] = NULL;
  }
  return G;
}

/* -- insertEdge ----------------------------------------------------------- */
/* - Insere o arco (u, v) no grafo apontado por G.                         - */
/* ------------------------------------------------------------------------- */
void graphInsertEdge (graph_t* G, int u, int v)
{
  arc_t* e;
  MallocT (e, arc_t, 1);

  e->v = v;
  e->next = G->adj[u];
  G->adj[u] = e;
}

/* -- createTransposed ----------------------------------------------------- */
/* - Cria um grafo transposto para o grafo apontado por G.                 - */
/* ------------------------------------------------------------------------- */
graph_t* createTransposedGraph (graph_t* G)
{
  int u;
  arc_t* e;
  graph_t* H = createGraph (G->nVertex);

  for (u = 0; u < G->nVertex; ++u)
    for (e = G->adj[u]; e; e = e->next)
      graphInsertEdge (H, e->v, u);

  return H;
}

/* -- free ----------------------------------------------------------------- */
/* - Libera o espaço alocado para armazenar o grafo apontado por G.        - */
/* ------------------------------------------------------------------------- */
void freeGraph (graph_t* G)
{
  int i;
  arc_t* e;
  arc_t* f;

  for (i = 0; i < G->nVertex; i++) {
    e = G->adj[i];
    while (e) {
      f = e;
      e = e->next;
      free (f);
    }
  }
  free (G->color);
  free (G->parent);
  free (G->adj);
  free (G);
}

/* -- pathCompression ------------------------------------------------------ */
/* - Libera o espaço alocado para armazenar o grafo apontado por G.        - */
/* ------------------------------------------------------------------------- */
int pathCompression (graph_t* G, int u)
{
  if (G->parent[u] == u) return u;
  return G->parent[u] = pathCompression (G, G->parent[u]);
}

// ------------------------------------------------------------------------- //
//            Estrutura e funções de manipulação de uma pilha.               //
// ------------------------------------------------------------------------- //

// Declaração da estrutura que implementa uma Pilha como um Tipo Abstrato de Dados.
//
typedef struct {
  int size;    // Número máximo de elementos que podem ser armazenados em uma pilha.
  int top_ptr; // Apontador para o topo da pilha. Consideramos como topo a  primeira
               // posição livre após o último elemento.
  int* body;   // Vetor que armazena os elementos da pilha. Alocado dinâmicamente.
} stack_t;

/* -- create --------------------------------------------------------------- */
/* - Inicializa a pilha apontada por s, alocando espaço para sz objetos.   - */
/* ------------------------------------------------------------------------- */
void createStack (stack_t* s, int sz)
{
  s->body = (int*) malloc (sizeof (int) * sz);
  assert (s->body);

  s->size = sz;
  s->top_ptr = 0;
}

/* -- free ----------------------------------------------------------------- */
/* - Libera o espaço alocado para armazenar os elementos da pilha apontada - */
/* - por s.                                                                - */
/* ------------------------------------------------------------------------- */
void freeStack (stack_t* s)
{
  free (s->body);
}

/* -- clear ---------------------------------------------------------------- */
/* - Limpa o conteúdo da pilha apontada por s.                             - */
/* ------------------------------------------------------------------------- */
void clearStack (stack_t* s)
{
  s->top_ptr = 0;
}

/* -- isfull --------------------------------------------------------------- */
/* - Devolve verdadeiro caso não haja mais espaço na pilha apontada por  s - */
/* - e falso em caso contrário.                                            - */
/* ------------------------------------------------------------------------- */
int stackIsFull (stack_t* s)
{
  return (s->top_ptr == s->size);
}

/* -- isempty--------------------------------------------------------------- */
/* - Devolve verdadeiro caso a pilha apontada por s esteja vazia  e  falso - */
/* - em caso contrário.                                                    - */
/* ------------------------------------------------------------------------- */
int stackIsEmpty (stack_t* s)
{
  return (!s->top_ptr);
}

/* -- push ----------------------------------------------------------------- */
/* - Empilha o elemento x na pilha apontada por s.                         - */
/* ------------------------------------------------------------------------- */
void stackPush (stack_t* s, int x)
{
  assert (!stackIsFull (s));
  s->body[s->top_ptr++] = x;
}

/* -- pop ------------------------------------------------------------------ */
/* - Desempilha e devolve o elemto do topo da pilha apontada por s.        - */
/* ------------------------------------------------------------------------- */
int stackPop (stack_t* s)
{
  assert (!stackIsEmpty (s));
  return s->body[--s->top_ptr];
}

/* -- top ------------------------------------------------------------------ */
/* - Devolve o elemto do topo da pilha apontada por s, sem desemplilhá-lo. - */
/* ------------------------------------------------------------------------- */
int stackTop (stack_t* s)
{
  assert (!stackIsEmpty (s));
  return s->body[s->top_ptr - 1];
}

// ------------------------------------------------------------------------- //
//                    Funções para busca em profundidade.                    //
// ------------------------------------------------------------------------- //

void DFSVisit (graph_t* G, stack_t* S, int u)
{
  arc_t* e;
  G->color[u] = GRAY;

  for (e = G->adj[u]; e; e = e->next)
    if (G->color[e->v] == WHITE) {
      G->parent[e->v] = u;
      DFSVisit (G, S, e->v);
    }

  stackPush (S, u);
  G->color[u] = BLACK;
}

void DFS (graph_t* G, stack_t* S1, stack_t* S2)
{
  while (!stackIsEmpty (S1)) {
    int u = stackPop (S1);
    if (G->color[u] == WHITE)
      DFSVisit (G, S2, u);
  }
}

/* -- PrintDFS_Tree -------------------------------------------------------- */
/* - Imprime a árvore de busca em profundidade.                            - */
/* ------------------------------------------------------------------------- */
void PrintDFS_Tree (graph_t* G)
{
  int i;
  for (i = 0; i < G->nVertex; i++)
    printf ("Vertice %2d, color = %2d, parent = %2d\n", i + 1, G->color[i], G->parent[i] + 1);
  printf ("\n");
}

// ------------------------------------------------------------------------- //
//                             Função principal.                             //
// ------------------------------------------------------------------------- //
int main (void)
{
  FILE* ifs;

  int i, j, k, n, m, compNum, instNum = 0;

  graph_t* G;
  graph_t* H;

  stack_t S1; 
  stack_t S2; 

  assert ((ifs = fopen (IF_NAME, "rt")) != 0);

  createStack (&S1, MAX_NUM_VERTEX);
  createStack (&S2, MAX_NUM_VERTEX);

  for (;;) {
    instNum++;
    fscanf (ifs, "%d%d", &n, &m);
    if (!n && !m) break;
    assert (0 < n && n < MAX_NUM_VERTEX);
    assert (0 < m && m < MAX_NUM_ARCS);

    G = createGraph (n);
    compNum = 0;

    for (k = 0; k < m; ++k) {
      fscanf (ifs, "%d%d", &i, &j);
      graphInsertEdge (G, i - 1, j - 1);
    }

    for (k = 0; k < n; ++k)
      stackPush (&S1, n - k - 1);

    // Primeira busca em profundidade.
    //
    DFS (G, &S1, &S2);
    D (PrintDFS_Tree (G));

    // Transpõe o grafo.
    //
    H = createTransposedGraph (G);

    // Segunda busca em profundidade.
    //
    DFS (H, &S2, &S1);
    D (PrintDFS_Tree (H));

    // Imprime a solução.
    //
    clearStack (&S1);
    for (k = n - 1; k >= 0; --k)
      if (H->parent[k] == k) {
	stackPush (&S1, k);
	++compNum;
      }

    for (k = 0; k < n; ++k)
      pathCompression (H, k);

    printf ("Arquipelago %d\n", instNum);
    for (i = 0; i < compNum; ++i) {
      printf ("Grupo %d:", i + 1);

      k = stackPop (&S1);
      for (j = 0; j < n; ++j)
	if (H->parent[j] == k)
	  printf (" %d", j + 1);

      printf ("\n");
    }
    printf ("\n");
    D (PrintDFS_Tree (H));
    
    clearStack (&S1);
    clearStack (&S2);
    freeGraph (G);
    freeGraph (H);
  }

  freeStack (&S1);
  freeStack (&S2);
  fclose (ifs);
  return 0;
}