//Richard Andrei Aquino dos Santos
//AED2

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct dado {
	char valor;
	struct dado *prox;
} Hash;

void insereNovo(Hash **tabela, int i, char letra);
void insereHash(Hash** tabela, char valorA, char valorB, int tamanho);
void ordena(Hash** tabela, int i);
int tamanho;

int main() {
	int nTestes, C, k, i, j,l,m;
	char letra, a, b;
	Hash** tabela;
	Hash* tmp;
	scanf("%d", &nTestes);          //nTestes serve para fazer varios testes de hashs de entradas diferentes
	tabela = (Hash **)malloc(sizeof(Hash*));
	m = 0;
	for (k = 0; k < nTestes; k++) {
		letra = 'a';
		scanf("%d %d", &tamanho, &C);       //tamanho = tamanho do vertice , C numero de arestas
		tabela = (Hash **)realloc(tabela, tamanho * sizeof(Hash*)); // aloca tabela com tamanho inicial maximo

		for (i = 0; i < tamanho; i++) { // insere todos as letras usadas em cada posição inicial na tabela
			insereNovo(tabela, i, letra);
			letra++;//a +1  = b // b + 1 = c
		}/*
		for (i = 0; i < tamanho; i++) {
			printf("%d %c\n", i, tabela[i]->valor);//testando se inserções foram corretas
		}*/

		for (i = 0; i < C; i++) { // recebendo valores para serem inseridos
			fflush(stdin);
			scanf("\n%c \n%c",&a,&b);
			insereHash(tabela, a, b, tamanho);
		}
		j = 0;
		l = 0;
		printf("Case #%d:\n", m);
		m++;
		while (j < tamanho) {                     // j = indica a chave

			tmp = tabela[j];
			if (tmp != NULL) {
				l++;

			}
			while (tmp != NULL) {                 //Enquanto existir algo
				printf("%c,", tmp->valor);    //imprime o valor e
				tmp = tmp->prox;                // avança pro proximo
			}
			if(tabela[j] != NULL)
				printf("\n");
			j++;

		}
		printf("%d connected components\n\n", l);
	}
		//free(tabela);
		return 0;
}

void insereHash(Hash** tabela, char valorA, char valorB, int tamanho) {
		Hash *novoA, *novoB, *auxA, *auxB;
		int i, matchA = 0, matchB = 0, aux = 0, ia = 1000, ib = 1000, iaux;
		//printf("%c %c", valorA, valorB);
		for (i = 0; i < tamanho; i++) {
			novoA = tabela[i];
			novoB = tabela[i];
			/*while (novoA == NULL) {
				i++;
				novoA = tabela[i];
				novoB = tabela[i];
			}*/
			aux = 0;
			if(novoA != NULL){
			if (matchA == 0) { // matchA indica quando foi encontrado na tabela o valorA recebido
				while (aux == 0) { //aux indica se foi encontrado ou chegou em NULL
					//printf("novoA %c valorA %c\n", novoA->valor, valorA);
					if (novoA->valor == valorA) {
						matchA = 1;
						aux = 1;
						ia = i;
					}
					else {
						novoA = novoA->prox;
					}
					if (novoA == NULL) {//não esta nessa lista então vamos pra proxima
						aux = 1;
					}

				}
			}
			aux = 0;
			if (matchB == 0) {// matchB indica quando foi encontrado na tabela o valorB recebido
				while (aux == 0) {//aux indica se foi encontrado ou chegou em NULL					printf("%c\n", novoB->valor);
					//printf("%c\n", novoB->valor);
					if (novoB->valor == valorB) {
						matchB = 1;
						aux = 1;
						ib = i;
					}
					else {
						novoB = novoB->prox;
					}
					if (novoB == NULL) {
						aux = 1;
					}

				}
			}
			}

		}
		aux = 0;
		novoA = tabela[ia]; //ia aponta em qual lista foi encontrado o valorA
		novoB = tabela[ib]; //ib aponta em qual lista foi encontrado o valorB
		if (ia < ib) {// Se a lista os valores da lista A são menores que da lista B
			while (novoA->prox != NULL)
				novoA = novoA->prox;
			novoA->prox = novoB; // coloca a lista ja encontrada em novoB no fim da lista de novoA
			//printf("%d %d\n", matchA, matchB);
			//printf("%d %d", ia, ib);
			ordena(tabela, ia);// ordena a nova lista formada por A e B
			tabela[ib] = NULL;//diz que a tabela onde a lista B estava não será mais utilizada
		}
		else {
			if (ia > ib) {// Se a lista os valores da lista B são menores que da lista A
				while (novoB->prox != NULL)
					novoB = novoB->prox;
				novoB->prox = novoA;// coloca a lista ja encontrada em novoA no fim da lista de novoB
				//printf("%d %d\n", matchA, matchB);
				//printf("%d %d", ia, ib);
				ordena(tabela, ib);// ordena a nova lista formada por A e B
				tabela[ia] = NULL;//diz que a tabela onde a lista A estava não será mais utilizada
			}


		}
		auxA = tabela[0];
		while (auxA != NULL) {
			//printf("%c", auxA->valor);
			auxA = auxA->prox;
		}
	}

	void ordena(Hash** tabela, int i){// ordena a lista
		Hash *A,*B,*aux;
		char vA,vB;
		A = tabela[i];
		vA = A->valor;
		while (A->prox != NULL) {
			B = A->prox;
			while (B != NULL) {
			vB = B->valor;
				if (A->valor > B->valor) {
					A->valor = vB;
					B->valor = vA;
				}
				B = B->prox;
			}
			A = A->prox;
			vA = A->valor;
		}
	}

void insereNovo(Hash **tabela, int i, char letra) {
	Hash *tmp;
	tmp = (Hash *)malloc(sizeof(Hash));
	tmp->valor = letra;
	tmp->prox = NULL;
	tabela[i] = tmp;
}