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

/*
 * Formát vstupu:
 * První řádek obsahuje číslo S = počet stromů.
 * (pro potřeby výstupu předpokládejme, že jsou stromy číslované 1 .. S)
 * Následuje S popisů stromů, každý z nich má následující formát:
 *
 *   První řádek obsahuje dvě čísla N a K
 *    - N udává počet vrcholů stromu (1 .. N)
 *    - K určuje, který vrchol je kořen
 *   Následujících N řádků popisuje postupně potomky jednotlivých vrcholů ve správném pořadí:
 *     každý řádek obsahuje nejprve číslo P = počet potomků a následně P čísel s identifikátory potomků.
 *
 * Pozor, program nekontroluje validitu vstupu.
 *
 * Příklad vstupu ze zadání:
 * (Pro lepši čitelnost jsme jednotlivé stromy oddělili prázdným řádkem.
 * Tento program prázdné řádky ignoruje.)
------------
4

6 1
2 2 3
3 4 5 6
0
0
0
0

6 1
2 5 4
0
0
3 2 3 6
0
0

4 4
0
0
1 1
2 3 2

4 3
1 2
0
2 1 4
0
------------
 */

/*
 * Samotný strom obsahuje N vrcholů a N-1 hran. Interně jsou všechny vrcholy
 * číslovány od 0. Ve vrcholu si pamatujeme dvě čísla (zacatek a konec), která
 * jsou indexy v poli hran. Potomci vrcholu "i" tak jsou vrcholy s čísly:
 *
 *   strom.hrany[strom.vrcholy[i].zacatek]
 *   strom.hrany[strom.vrcholy[i].zacatek + 1]
 *     ...
 *   strom.hrany[strom.vrcholy[i].konec - 2]
 *   strom.hrany[strom.vrcholy[i].konec - 1]
 *
 * Počet potomků vrcholu "i" je:
 *   strom.vrcholy[i].konec - strom.vrcholy[i].zacatek
 */

struct vrchol {
	int zacatek;
	int konec;
};

struct strom {
	int cislo_stromu;
	int N; // počet vrcholů
	int K; // číslo kořene
	struct vrchol *vrcholy;
	int *hrany;
	char *retezec;
};

struct spojovy_seznam { // spojový seznam s čísly stromů v trii
	struct spojovy_seznam *dalsi;
	int cislo_stromu;
};

struct trie { // jeden vrchol trie
	struct trie *D;
	struct trie *N;
	struct spojovy_seznam *stromy; // seznam řetězců, končících v tomto vrcholu
};

int S; // počet stromů
struct trie koren_trie; // kořen globální trie

struct strom nacti_strom(int cislo_stromu) {
	struct strom str;
	str.cislo_stromu = cislo_stromu;
	scanf("%d%d", &str.N, &str.K);
	str.K--; // Interně číslujeme vrcholy od nuly.
	str.vrcholy = malloc(sizeof(struct vrchol) * str.N);
	str.hrany = malloc(sizeof(int) * (str.N - 1)); // počet hran je N - 1
	str.retezec = malloc(sizeof(char) * (str.N * 2 + 1)); // Délka řetězce je 2N. Navíc potřebujeme jeden byte na ukončení řetězce '\0'.

	int aktualni_hrana = 0;
	for (int i = 0; i < str.N; i++) {
		int P;
		scanf("%d", &P); // počet potomků
		str.vrcholy[i].zacatek = aktualni_hrana;
		for (int j = 0; j < P; j++) {
			int potomek;
			scanf("%d", &potomek);
			str.hrany[aktualni_hrana] = potomek - 1; // Interně číslujeme vrcholy od nuly, na vstupu se číslují od jedničky.
			aktualni_hrana++;
		}
		str.vrcholy[i].konec = aktualni_hrana;
	}
	return str;
}

// Procházení stromu do hloubky a generování řetězce. Funkce vrací pozici v řetězci, na kterou se má zapsat další znak.
int dfs_pruchod(struct strom *str, int vrchol, int zacatek_retezce) {
	str->retezec[zacatek_retezce] = 'D'; // Právě po hraně vstupujeme do vrcholu z otce.
	zacatek_retezce++;

	for (int i = str->vrcholy[vrchol].zacatek; i < str->vrcholy[vrchol].konec; i++) {
		zacatek_retezce = dfs_pruchod(str, str->hrany[i], zacatek_retezce);
	}

	str->retezec[zacatek_retezce] = 'N'; // Návrat po hraně nahoru do otce.
	zacatek_retezce++;
	return zacatek_retezce;
}

void zakoduj_do_retezce(struct strom *str) {
	int konec_retezce = dfs_pruchod(str, str->K, 0);
	str->retezec[konec_retezce] = '\0'; // znak konce řetězce
}

// Přidání řetězce do trie bez rekurze
void trie_pridej(struct trie *aktualni, const char *retezec, int cislo_stromu){
	while (retezec[0]) {
		if (retezec[0] == 'D') {
			if (!aktualni->D) {
				// V případě potřeby nejprve vrchol vytvoříme
				aktualni->D = malloc(sizeof(struct trie));
				aktualni->D->D = NULL;
				aktualni->D->N = NULL;
				aktualni->D->stromy = NULL;
			}
			aktualni = aktualni->D; // posun v trii
		}
		else if (retezec[0] == 'N') {
			if (!aktualni->N) {
				aktualni->N = malloc(sizeof(struct trie));
				aktualni->N->D = NULL;
				aktualni->N->N = NULL;
				aktualni->N->stromy = NULL;
			}
			aktualni = aktualni->N;
		}
		retezec++; // posun v řetězci
	}

	// Nyní jsme prošli v trii celý řetězec. Do aktuálního vrcholu proto přidáme číslo řetězce/stromu.

	struct spojovy_seznam *zaznam = malloc(sizeof(struct spojovy_seznam));
	zaznam->cislo_stromu = cislo_stromu;
	zaznam->dalsi = aktualni->stromy;
	aktualni->stromy = zaznam;
}

void pridej_retezec_do_trie(struct strom str) {
	//printf("pridavam retezec cislo %i: %s\n", str.cislo_stromu, str.retezec);
	trie_pridej(&koren_trie, str.retezec, str.cislo_stromu);
}

// Výpis jedné hromádky izomorfních stromů
void vypis_spojovy_seznam(struct spojovy_seznam *aktualni) {
	char oddelovac = '{';
	while (aktualni) {
		printf("%c%i", oddelovac, aktualni->cislo_stromu);
		oddelovac = ',';
		aktualni = aktualni->dalsi;
	}
	printf("}\n");
}

// Rekurzivně projdeme trii a všechny neprázdné spojové seznamy vypíšeme.
void vypis_skupiny_z_trie(struct trie *aktualni) {
	if (aktualni->stromy)
		vypis_spojovy_seznam(aktualni->stromy);
	if (aktualni->D)
		vypis_skupiny_z_trie(aktualni->D);
	if (aktualni->N)
		vypis_skupiny_z_trie(aktualni->N);
}

int main(void) {
	koren_trie.D = NULL;
	koren_trie.N = NULL;
	koren_trie.stromy = NULL;

	scanf("%d", &S); // počet stromů

	for (int i = 1; i <= S; i++) {
		struct strom str = nacti_strom(i);

		zakoduj_do_retezce(&str);
		pridej_retezec_do_trie(str);

		free(str.vrcholy);
		free(str.hrany);
		free(str.retezec);
	}

	vypis_skupiny_z_trie(&koren_trie);
	return 0;
}