#include <iostream>
#include <vector>
#include <map>

using namespace std;

vector<pair<int, int>> graph;
/*
 * E -> C
 * costs(v, u) = c
 * c[i] - сколько получим, поставив i-ую букву на это ребро
 */
map<pair<int, int>, vector<double>> costs;

char get_opt(pair<int, int> edge)
{
    double max = -1.0;
    char opt = 'a';
    vector<double> counts = costs[edge];
    for (int i = 0; i <= 'z' - 'a'; i++)
    {
        if (counts[i] >= max)
        {
            max = counts[i];
            opt = static_cast<char>('a' + i);
        }
    }
    return opt;
}

int main()
{
    freopen("discrete.in", "r", stdin);
    freopen("discrete.out", "w", stdout);
    int n;
    int m;
    cin >> n >> m;
    for (int i = 0; i < n; i++)
    {
        int t0;
        int t1;
        cin >> t0 >> t1;
        graph.emplace_back(t0 - 1, t1 - 1);
        costs[{i, t0 - 1}] = vector<double>(31);
        costs[{i, t1 - 1}] = vector<double>(31);

        for (int j = 0; j <= 'z' - 'a'; j++)
        {
            costs[{i, t0 - 1}][j] = 0.0;
            costs[{i, t1 - 1}][j] = 0.0;
        }
    }
    for (int i = 0; i < m; i++)
    {
        int len;
        string input;
        string output;
        cin >> len >> input >> output;

        int cur_state = 0;

        for (int j = 0; j < len; j++)
        {
            char cur_input = input[j];
            char cur_output = output[j];
            int next_state = -1;
            if (cur_input == '0')
            {
                next_state = graph[cur_state].first;
            }
            else
            {
                next_state = graph[cur_state].second;
            }
            pair<int, int> cur_edge = make_pair(cur_state, next_state);
            costs[cur_edge][cur_output - 'a'] += (static_cast<double>(1) / static_cast<double>(len));
            cur_state = next_state;
        }
    }

    for (int i = 0; i < n; i++)
    {
        int t0 = graph[i].first;
        int t1 = graph[i].second;
        cout << get_opt({i, t0}) << " " <<  get_opt({i, t1}) << endl;
    }
    return 0;
}