#include <iostream>
#include <vector>

using namespace std;

/**
Input ejemplo:
6 3
A B
B E
C D
**/

///Declaramos la lista de adyacencia como global,
///así podemos acceder a ella desde cualquier función
vector <vector <char> > ady;
vector <bool> visitados;
vector <char> prov; ///Acá vamos guardando las ciudades que corresponden con cada ciudad

void DFS(char ciudad)
{
    visitados[ciudad - 'A'] = true;
    prov.push_back(ciudad);

    for(int i=0; i<ady[ciudad-'A'].size(); i++)
        if(visitados[ ady[ciudad-'A'][i] - 'A' ] == 0) ///Si no visitó la ciudad vecina,
            DFS(ady[ciudad-'A'][i]);                    ///entonces la visito
}

int main()
{
    int N, M; ///Cantidad de nodos (nodes), cantidad de aristas (edges)
    char C1, C2; ///Variables para describir cada arista/ruta entre Ciudad_1 y Ciudad_2

    cin >> N >> M;

    ady.resize(N); ///Le damos tamaño a la lista de adyacencia

    for(int i=0; i<M; i++) ///Leemos cada una de las rutas
    {
        cin >> C1 >> C2;
        ady[C1-'A'].push_back(C2);
        ady[C2-'A'].push_back(C1);
    }

    ///Hasta acá, lo que se hizo es la lectura del grafo.

    visitados = vector <bool> (N, false); ///El vector visitados es un vector de bool de tamaño N lleno de false (cero)

    int cantidadProvincias = 0;

    for(int i=0; i<N; i++) ///Este for itera por todas las ciudades
    {
        if(visitados[i] == 0) ///Si no visité a esta ciudad,
        {
            DFS('A'+i);       /// la visito
            ///Luego de ejecutar el DFS para esa ciudad, en el vector prov me quedaron las ciudades recorridas
            ///Es decir, las ciudades que van a formar parte de la provincia

            cantidadProvincias++; ///Ahora tenemos una provincia más

            cout << "Provincia " << cantidadProvincias << ": ";
            for(int j=0; j<prov.size(); j++) ///Muestro en una línea las ciudades de esta provincia
                cout << prov[j] << " ";
            cout << endl;

            prov.clear(); ///Dejo el vector de prov listo para la siguiente provincia a detectar
        }
    }

    cout << "Para dividir el pais necesitamos crear " << cantidadProvincias << " provincia/s" << endl;

    return 0;
}