#include <iostream>
#include <vector>
using namespace std;

struct my_pair
{
    int a;
    int b;
};

struct vertex
{
    bool isterminal;
    int adj_list[26];
};

struct cart_vertex
{
    int u;
    int v;
    bool isvisited;
    struct my_pair adj_list[26];
    vector<int> reverse_adj_list;
    int list_size = 0;
};

void addEdge(int i, int j, char symbol, struct vertex* DFA)
{
    int symbol_idx = static_cast<int>(symbol) - 97;
    DFA[i].adj_list[symbol_idx] = j;
}

void clean_DFA(struct vertex* DFA, int n)
{
    for (int i = 0; i < n; ++i)
    {
        DFA[i].isterminal = false;
        for (int j = 0; j < 26; ++j)
            DFA[i].adj_list[j] = -1;
    }
}


void Fill_DFA(int n, int k, int l, struct vertex* DFA)
{
    int u, v;
    int number_terminal;
    char c;

    clean_DFA(DFA, n);

    for (int i = 0; i < k; ++i)
    {
        std::cin >> number_terminal;
        DFA[number_terminal].isterminal = true;
    }

    for (int i = 0; i < n * l; ++i)
    {
        std::cin >> u >> c >> v;
        addEdge(u, v, c, DFA);
    }

    return;
}

void clean_DFA_two(struct cart_vertex* DFA, int n)
{
    for (int i = 0; i < n; ++i)
    {
        DFA[i].isvisited = false;
        DFA[i].list_size = 0;
        //for (int j = 0; j < 26; ++j)
        //    DFA[i].reverse_adj_list[j] = -1;
    }
}

void cart_product(struct cart_vertex* dec_graph,
            struct vertex* DFA_one, int n_one, std::vector<int>& list_of_terminals)
{

    int N = n_one * n_one;

    clean_DFA_two(dec_graph, N);

    for (int i = 0; i < n_one; ++i)
    {
        for (int j = 0; j < n_one; ++j)
        {
            int idx = i * n_one + j;

            dec_graph[idx].u = i;
            dec_graph[idx].v = j;




            if (DFA_one[i].isterminal != DFA_one[j].isterminal)
            {
                list_of_terminals.push_back(idx);
            }

            for (int k = 0; k < 26; ++k)
            {
                if (DFA_one[i].adj_list[k] >= 0 && DFA_one[j].adj_list[k] >= 0)
                {
                    dec_graph[idx].adj_list[k].a = DFA_one[i].adj_list[k];
                    dec_graph[idx].adj_list[k].b = DFA_one[j].adj_list[k];
                }
                else
                {
                    dec_graph[idx].adj_list[k].a = -1;
                    dec_graph[idx].adj_list[k].b = -1;
                }
            }
        }
    }
}

void reverse_cart_graph(struct cart_vertex* graph, int N, int n_one)
{
    int a,b,idx;
    for (int i = 0; i < N; ++i)
    {
        for (int j = 0; j < 26; ++j)
        {
            a = graph[i].adj_list[j].a;
            b = graph[i].adj_list[j].b;
            idx = a * n_one + b;

            if (a >= 0 && b >= 0)
            {
                graph[idx].reverse_adj_list.push_back(i);
                graph[idx].list_size++;
            }
            //else
            //    graph[idx].reverse_adj_list[j] = -5;
        }

    }
}

void display2(struct cart_vertex* DFA, int n)
{
    std::cout << "\n print:" << std::endl;
    for (int i = 0; i < n; i++)
    {
        std::cout << "vertex: (" << DFA[i].u << "," << DFA[i].v << ") ";


        std::cout << "adj_vertexes: ";
        for (int j = 0; j < 26; ++j)
        {
            if (DFA[i].adj_list[j].a != -1)
                std::cout << char(j + 97) << "->(" << DFA[i].adj_list[j].a << ","
                          << DFA[i].adj_list[j].b << "); ";
        }
        std::cout << std::endl;
    }
}

void display2_reverse(struct cart_vertex* DFA, int n)
{
    std::cout << "\n print:" << std::endl;
    for (int i = 0; i < n; i++)
    {
        std::cout << "vertex: (" << DFA[i].u << "," << DFA[i].v << ") ";

        if (not DFA[i].isvisited)
            std::cout << " (not visited) ";
        std::cout << "adj_vertexes: ";
        for (int j = 0; j < DFA[i].reverse_adj_list.size(); ++j)
        {
            int num = DFA[i].reverse_adj_list[j];
            std::cout << "(" << DFA[num].u << "," << DFA[num].v << "); ";
        }
        std::cout << std::endl;
    }
}

void DFS(int v_idx, struct cart_vertex* graph, int N)
{

    int a, b, idx;
    graph[v_idx].isvisited = true;

    int count = graph[v_idx].list_size;
    for (int k = 0; k < count; ++k)
    {
        idx = graph[v_idx].reverse_adj_list[k];
        if (idx >= 0 && not graph[idx].isvisited)
                DFS(idx, graph, N);
    }

    return;
}

/*
void check_equiv(struct cart_vertex* cart_graph, int N)
{

    for (int i = 0; i < N; ++i)
    {
        if (not cart_graph[i].isvisited)
    }

    if (is_equiv)
        std::cout << "EQUIVALENT";
    else
        std::cout << "NOT EQUIVALENT";
}
*/

bool is_same_group(cart_vertex* a, cart_vertex* b)
{

    return (a->u == b->u || a->u == b->v || a->v == b->u || a->u == b->v);

}

int main()
{

    int n_one, k_one, l_one;

    std::cin >> n_one >> k_one >> l_one;
    vertex DFA_one[n_one];
    Fill_DFA(n_one, k_one, l_one, DFA_one);

    int N = n_one * n_one;
    struct cart_vertex cart_graph[N];
    vector<int> list_of_terminals;

    cart_product(cart_graph, DFA_one, n_one, list_of_terminals);

    display2(cart_graph, N);

    reverse_cart_graph(cart_graph, N, n_one);


    display2_reverse(cart_graph, N);


    for (int i = 0; i < list_of_terminals.size(); ++i)
    {
        cout << "i: " << i << " " << list_of_terminals[i] << "; " << endl;
        DFS(list_of_terminals[i], cart_graph, N);
    }

    display2_reverse(cart_graph, N);


    vector<int> not_visitied_list;
    for (int i =0; i < N; ++i)
    {
        if (not cart_graph[i].isvisited ) //&& cart_graph[i].u != cart_graph[i].v
        {
            not_visitied_list.push_back(i);
            cout << i << " ";
        }
    }
    cout << endl;

    int m = not_visitied_list.size();

    int idx_to_group[n_one];
    for (int i =0; i < n_one; ++i)
        idx_to_group[i] = -1;

    int curr_num_group = -1;

    bool selected[m];
    for (int i =0; i < m; ++i)
        selected[i] = false;


    int idx;
    //idx = not_visitied_list[0];
    //idx_to_group[cart_graph[idx].u] = u;
    //idx_to_group[cart_graph[idx].v] = u;
    for (int i =0; i < m; ++i)
    {
        if (idx_to_group[i] == -1)
        {
            for (int j =0; j < m; ++j)
            {
                int idx = not_visitied_list[j];
                if (cart_graph[idx].u == i || idx_to_group[cart_graph[idx].u] == i)
                {
                    idx_to_group[cart_graph[idx].v] = i;
                }
                if (cart_graph[idx].v == i || idx_to_group[cart_graph[idx].v] == i)
                {
                    idx_to_group[cart_graph[idx].u] = i;
                }

            }

        }

        idx_to_group[i] == i;
    }
    /*
    for (int i =0; i < m; ++i)
    {
        if (not selected[i])
        {
            curr_num_group++;
            idx_to_group[i] = curr_num_group;
            for (int j =i+1; j < m; ++j)
            {
                if (not selected[j])
                {
                    if (is_same_group(&cart_graph[not_visitied_list[i]], &cart_graph[not_visitied_list[j]]))
                    {
                        idx_to_group[j] = curr_num_group;
                        selected[j] = true;
                    }

                }
            }

        }

        selected[i]=true;

    }
    */

    for (int i =0; i < n_one; ++i)
        cout << idx_to_group[i] << ", ";
    cout << "Done" << endl;
    //check_equiv(cart_graph, N);


    return 0;
}