#include <bits/stdc++.h>
using namespace std;

const int MAXN = 300;
const int MAXG = 1'000;
const int MAXT = 1'000'000;
const int MAXL = 15;
const int NUM_CASES = 30;

random_device rd;
mt19937 gen(chrono::steady_clock::now().time_since_epoch().count());

int genNumber(int l, int r) {
    uniform_int_distribution<> distr(l, r);
    return distr(gen);
}

string genString(int len) {
    string s = "";
    while (len--) s += "a";
    for (int i = 0; i < int(s.length()); i++) s[i] += genNumber(0, 25);
    return s;
}

void genRandomCase() {
    int n = genNumber(2*MAXN/3, MAXN);
    int g = genNumber(MAXG/2, MAXG);

    cout << n << " " << g << endl;

    vector<string> locations(n);

    for (int i = 0; i < n; i++) {
        int len = genNumber(MAXL/3, MAXL);
        locations[i] = genString(len);
        int time = genNumber(MAXT/10, MAXT);
        cout << locations[i] << " " << time << endl;
    }

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (i == j) {
                cout << 0;
                if (j != n-1) cout << " ";
                continue;
            }
            int odds = genNumber(1, 15);
            if (odds != 1) {
                cout << -1;
            }
            else {
                cout << genNumber(MAXT/10, MAXT);
            }
            if (j != n-1) cout << " ";
        }
        cout << endl;
    }

    while (g--) {
        int i = genNumber(0, n-1);
        int j = genNumber(0, n-1);
        while (i == j) j = genNumber(0, n-1);
        int d = genNumber(10, n/3);

        cout << locations[i] << " " << locations[j] << " " << d << endl;

        set<int> picked;
        picked.insert(i);
        picked.insert(j);

        for (int iter = 0; iter < d; iter++) {
            int k = genNumber(0, n-1);
            while (picked.count(k) == 0) k = genNumber(0, n-1);
            picked.insert(k);
            cout << locations[k];
            if (iter < d-1) cout << k << " ";
        }
        
        cout << endl;
    }
}

void genMaxCase() {
    int n = MAXN;
    int g = MAXG;

    cout << n << " " << g << endl;

    vector<string> locations(n);

    for (int i = 0; i < n; i++) {
        string s = genString(MAXL);
        cout << s << " " << MAXT << endl;
        locations[i] = s;
    }

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (i == j) {
                cout << 0;
                if (j != n-1) cout << " ";
                continue;
            }
            cout << MAXT;
            if (j != n-1) cout << " ";
        }
        cout << endl;
    }

    while (g--) {
        cout << n-2 << endl;
        int i = genNumber(0, n-1);
        int j = genNumber(0, n-1);
        int d = n-2;
        while (j == i) j = genNumber(0, n-1);

        cout << locations[i] << " " << locations[j] << " " << n-2;

        int iter = 0;
        
        for (int x = 0; x < n; x++) {
            if (x != i && x != j) {
                cout << locations[x];
                iter++;
                if (iter < n-2) cout << " ";
            }
        }

        cout << endl;
    }
}

int main() {

    // genMaxCase();

    for (int i = 0; i < NUM_CASES; i++) {
        cerr << i << endl;
        genRandomCase();
    }
}