//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;
	char letra, auxletra = 'a', a = 'a', b = 'a';
	Hash** tabela;
	Hash* tmp;
	scanf("%d", &nTestes);          //nTestes serve para fazer varios testes de hashs de entradas diferentes
	tabela = (Hash **)malloc(sizeof(Hash*));

	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
			scanf("%c %c", &a, &b);
			insereHash(tabela, a, b, tamanho);
		}
		j = 0;
		while (j < tamanho) {                     // j = indica a chave
			printf("Case #%d:\n", j);                 // imprime chave no momento
			tmp = tabela[j];
			while (tmp != NULL) {                 //Enquanto existir algo
				printf("%c,", tmp->valor);    //imprime o valor e
				tmp = tmp->prox;                // avança pro proximo
			}
			printf("\n");
			j++;
		}
	}
		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;

		for (i = 0; i < tamanho; i++) {
			novoA = tabela[i];
			novoB = tabela[i];
			aux = 0;
			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
					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
					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
			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
				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
			}


		}

	}

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

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