#include <stdio.h>
/*-------------------------------------------------------------------*\
|  grafos0.h  --- TAD para implementacao de grafo dirigido SEM pesos  |
|                                                                     |
|    Vers�o simplificada;  |V| <=  MAXVERTS;                          |
|     Assume-se que os v�rtices s�o numerados de 1 a |V|.             |
|                                                                     |
|   A.P.Tom�s, CC2001 (material para prova pratica), DCC-FCUP, 2017   |
|   Last modified: 2017.12.18                                         |
\--------------------------------------------------------------------*/

#include <stdlib.h>

#define MAXVERTS 20000
// numero maximo de vertices (alterar se necessario)


typedef struct arco {
  int no_final;
  struct arco *prox;
} ARCO;

typedef struct no {
  //int label;
  ARCO *adjs;
} NO;

typedef struct graph {
  NO verts[MAXVERTS+1];  // n�s implicitamente numerados de 1 a nvs
  int nvs, narcos;
} GRAFO;

//--- prot�tipos das fun��es dispon�veis----------------------------
//    ATEN��O AOS TIPOS DE ARGUMENTOS E DE RESULTADO


GRAFO *new_graph(int nverts);
/* cria um grafo com nverts vertices e sem arcos */
void destroy_graph(GRAFO *g);
/* liberta o espa�o reservado na cria��o do grafo */
void insert_new_arc(int i, int j, GRAFO *g);
/* insere arco (i,j) no grafo; n�o evita repeti��es */
void remove_arc(ARCO *arco, int i, GRAFO *g);
/* retira adjacente arco da lista de adjacentes de i */
ARCO *find_arc(int i, int j, GRAFO *g);
/* retorna um apontador para o arco (i,j) ou NULL se n�o existir */

//--- macros de acesso aos campos da estrutura --------------------------

#define NUM_VERTICES(g) ( (g) -> nvs )
// numero de vertices
#define NUM_ARCOS(g) ( (g) -> narcos )
// numero de arcos
#define ADJS_NO(i,g) ( (g) -> verts[i].adjs )
// primeiro arco da lista de adjacentes do n� i
#define PROX_ADJ(arco) ((arco) -> prox)
// proximo adjacente
#define ADJ_VALIDO(arco) (((arco) != NULL))
// se arco � v�lido
#define EXTREMO_FINAL(arco) ((arco) -> no_final)
// qual o extremo final de arco


//======  prot�tipos de fun��es auxiliares (privadas) ======
static ARCO* cria_arco(int);
static void free_arcs(ARCO *);


//======  Implementa��o (defini��o das fun��es) ========================

// para criar um grafo com nverts vertices e sem ramos
GRAFO *new_graph(int nverts)
{
  if (nverts > MAXVERTS) {
    fprintf(stderr,"Erro: %d > MAXVERTS\n",nverts);
    exit(EXIT_FAILURE);
  }
  GRAFO *g = (GRAFO *) malloc(sizeof(GRAFO));
  if (g == NULL) {
    fprintf(stderr,"Erro: falta memoria\n");
    exit(EXIT_FAILURE);
  }

  NUM_VERTICES(g) = nverts;
  NUM_ARCOS(g) = 0;
  while (nverts) {
    ADJS_NO(nverts,g) = NULL;
    nverts--;
  }
  return g;
}


// para destruir um grafo criado
void destroy_graph(GRAFO *g)
{ int i;
  if (g != NULL) {
    for (i=1; i<= NUM_VERTICES(g); i++)
      free_arcs(ADJS_NO(i,g));
    free(g);
  }
}

// para inserir um novo arco num grafo
void insert_new_arc(int i, int j, GRAFO *g)
{ /* insere arco (i,j) no grafo g  */

  ARCO *arco = cria_arco(j);
  PROX_ADJ(arco) = ADJS_NO(i,g);
  ADJS_NO(i,g) = arco;  // novo adjacente fica � cabe�a da lista
  NUM_ARCOS(g)++;
}

// para remover um arco de um grafo (se existir na lista de adjs[i])
void remove_arc(ARCO *arco, int i, GRAFO *g)
{
  if (arco != NULL) {
    ARCO *aux = ADJS_NO(i,g), *prev = NULL;
    while (aux != arco && ADJ_VALIDO(aux)) {
      prev = aux;
      aux = PROX_ADJ(aux);
    }
    if (aux == arco) {
      if (prev == NULL) {
	ADJS_NO(i,g)  = PROX_ADJ(arco);
      } else PROX_ADJ(prev) = PROX_ADJ(arco);
      free(arco);
      NUM_ARCOS(g)--;
    }
  }
}

// retorna um apontador para o arco (i,j) ou NULL se n�o existir
ARCO *find_arc(int i, int j, GRAFO *g){
  ARCO *adj = ADJS_NO(i,g);

  while(adj != NULL && EXTREMO_FINAL(adj) != j)
    adj = PROX_ADJ(adj);

  return adj;
}


// ----  as duas funcoes abaixo sao auxiliares nao publicas ----

// reservar memoria para um novo arco e inicializa-lo
static ARCO *cria_arco(int j)
{ // cria um novo adjacente
  ARCO *arco = (ARCO *) malloc(sizeof(ARCO));
  if (arco == NULL) {
    fprintf(stderr,"ERROR: cannot create arc\n");
    exit(EXIT_FAILURE);
  }
  EXTREMO_FINAL(arco) = j;
  PROX_ADJ(arco) = NULL;
  return arco;
}

// libertar uma lista de arcos
static void free_arcs(ARCO *arco)
{ // liberta lista de adjacentes
  if (arco == NULL) return;
  free_arcs(PROX_ADJ(arco));
  free(arco);
}

/*--------------------------------------------------------------------\
| Defini��o de um tipo abstracto de dados QUEUE:                      |
|   filas  (FIFO) com valores do tipo int                             |
|                                                                     |
|   A.P.Tom�s, CC211 (material para prova pratica), DCC-FCUP, 2012    |
|   Last modified: 2012.12.28                                         |
\--------------------------------------------------------------------*/



typedef enum {FALSE,TRUE} BOOL;


typedef struct fila {
  int inicio, fim, nmax;
  int *queue;
} QUEUE;


// criar fila com capacidade para n inteiros
QUEUE *mk_empty_queue(int n);
// colocar valor na fila
void enqueue(int v,QUEUE *f);
// retirar valor na fila
int dequeue(QUEUE *f);
// verificar se a fila est� vazia
BOOL queue_is_empty(QUEUE *f);
// verificar se a fila n�o admite mais elementos
BOOL queue_is_full(QUEUE *f);
// liberta fila
void free_queue(QUEUE *f);


//-------------- Implementa��o ---------------------------------------




// funcao auxiliar (privada)

static void queue_exit_error(char *msg);

static void queue_exit_error(char *msg)
{
  fprintf(stderr,"Error: %s.\n",msg);
  exit(EXIT_FAILURE);
}




// criar fila com capacidade para n inteiros
QUEUE *mk_empty_queue(int n)
{
  QUEUE *q = (QUEUE *) malloc(sizeof(QUEUE));
  if (q == NULL)
    queue_exit_error("sem memoria");

  q -> queue =  (int *) malloc(sizeof(int)*n);
  if (q -> queue == NULL)
    queue_exit_error("sem memoria");

  q -> nmax = n;
  q -> inicio = -1;
  q -> fim = 0;
  return q;
}

// libertar fila
void free_queue(QUEUE *q)
{
  if (q != NULL) {
    free(q -> queue);
    free(q);
  } else
    queue_exit_error("fila mal construida");
}


// colocar valor na fila
void enqueue(int v,QUEUE *q)
{
  if (queue_is_full(q) == TRUE)
    queue_exit_error("fila sem lugar");

  if (q -> queue == NULL)
    queue_exit_error("fila mal construida");

  if (queue_is_empty(q)==TRUE)
    q -> inicio = q -> fim; // fila fica com um elemento
  q -> queue[q->fim] = v;
  q -> fim = (q -> fim+1)%(q->nmax);
}

// retirar valor na fila
int dequeue(QUEUE *q)
{
  int aux;
  if (queue_is_empty(q) == TRUE)
    queue_exit_error("fila sem valores");

  if (q -> queue == NULL)
    queue_exit_error("fila mal construida");

  aux = q ->queue[q ->inicio];
  q -> inicio = (q -> inicio+1)%(q -> nmax);
  if (q -> inicio ==  q -> fim) {  // se s� tinha um elemento
    q -> inicio = -1; q -> fim = 0;
  }
  return aux;
}

// verificar se a fila est� vazia
BOOL queue_is_empty(QUEUE *q)
{
  if (q == NULL)
    queue_exit_error("fila mal construida");

  if (q -> inicio == -1) return TRUE;
  return FALSE;
}

// verificar se a fila n�o admite mais elementos
BOOL queue_is_full(QUEUE *q)
{
  if (q == NULL)
    queue_exit_error("fila mal construida");

  if (q -> fim == q -> inicio) return TRUE;
  return FALSE;
}




int bfs(GRAFO* grafo, int no) {
    int vertices = NUM_VERTICES(grafo);

    QUEUE *fila = mk_empty_queue(vertices);

    int visitados[vertices+1], i;

    for(i=1; i<=vertices; i++) {
        visitados[i] = FALSE;
        //pai[i] = -1;
    }

    enqueue(no,fila);
    //pai[no]=-1;
    visitados[no] = TRUE;

    int max = no;

    while(!queue_is_empty(fila)) {
        int v = dequeue(fila);
        ARCO *a = ADJS_NO(v,grafo);

        if(v>max)
            max = v;

        while(a != NULL) {
            int w = EXTREMO_FINAL(a);
            if(!visitados[w]) {
                //pai[w] = v;
                visitados[w] = TRUE;
                enqueue(w,fila);
            }
            a = PROX_ADJ(a);
        }
    }
    free_queue(fila);
    return max;
}

int main () {
    int nos, ramos,a,b,i,q, no;
    scanf("%d %d", &nos, &ramos);

    int final[nos+1];

    GRAFO *grafo = new_graph(nos);



    for(i=0; i<ramos; i++) {
        scanf("%d %d", &a,&b);
        insert_new_arc(a,b,grafo);
        insert_new_arc(b,a,grafo);
    }


    scanf("%d", &q);

    for(i=1; i<=nos; i++) {
        final[i] = 0;
    }

    for(i=0; i<q; i++) {
        scanf("%d", &no);
        if(final[no]== 0)
            final[no] = bfs(grafo, no);

        printf("No %d: %d\n", no,final[no]);
    }
}