#include <iostream>
#include <bits/stdc++.h>

using namespace std;
int T, N, M, u, v, n;
vector<vector<int>> neighbors;
vector<vector<string>> Y;
vector<int> cardinality, degree;
vector<bool> open, deleted, closed;
vector<string> label;
list<int> open_cycle;

//todo
void traverse(int node, int parent) {
    if(closed[node]) return;
    open[node] = true;
    cout << "NODE: " << node << " PARENT: " << parent << " CHILDREN: " << neighbors[node].size() << endl;
    for (int i = 0; i < neighbors[node].size(); ++i) {
        cout << "\nCHILD: " << neighbors[node][i] << endl;
        if (neighbors[node][i] == parent) continue;
        if (open[neighbors[node][i]]) {
            open_cycle.push_back(neighbors[node][i]);
        } else {
            traverse(neighbors[node][i], node);
        }
    }
    if (!open_cycle.empty()) {
        cout << "-BACHA-\n";
        if (open_cycle.front() == node) {
            vector<int> newNeighbors;
            for (int c : open_cycle) {
                deleted[c] = true;
                for (int neighbor : neighbors[c]) {
                    if (open[neighbor]) continue;
                    int j = 0;
                    while (neighbors[neighbor][j] != c) j++;
                    neighbors[neighbor][j] = node;
                    newNeighbors.push_back(neighbor);
                }
            }
            deleted[node] = false;
            cardinality[node] = open_cycle.size();
            degree[node] = newNeighbors.size();
            n -= cardinality[node] - 1;
            neighbors[node] = newNeighbors;
            open_cycle.clear();
        } else {
            open_cycle.push_back(node);
        }
    }
    open[node] = false;
    closed[node] = true;
    cout << "CLOSED: " << node << endl;
}

string node_label(int node) {
    // Y[node].push_back(label[node].substr(1, label[node].size() - 2));
    sort(Y[node].begin(), Y[node].end());
    label[node] = "";
    for (const auto &element : Y[node]) label[node] += element;
    if (cardinality[node] > 1) label[node] += "c" + to_string(cardinality[node]) + "e";
    return "0" + label[node] + "1";
}

string certificate() {
    stack<int> leaves;
    for (int i = 0; i < N; ++i) if (degree[i] == 1 && !deleted[i]) leaves.push(i);

    while (n > 2) {
        stack<int> leaves2;
        while (!leaves.empty()) {
            int leaf = leaves.top();
            leaves.pop();
            for (int parent : neighbors[leaf]) {
                if (degree[parent] < 1) continue;
                degree[parent]--;
                degree[leaf]--;
                n--;
                Y[parent].push_back(node_label(leaf));
                if (degree[parent] == 1) leaves2.push(parent);
            }
        }
        leaves = leaves2;
    }
    string result;
    while (!leaves.empty()) {
        int leaf = leaves.top();
        leaves.pop();
        string lbl = node_label(leaf);
        if (lbl > result) {
            result += lbl;
        } else {
            result = lbl + result;
        }
    }
    return result;
}

int main() {
    cin >> T >> N >> M;
    vector<string> certificates;

    neighbors.resize(N);
    Y.resize(N);
    label.resize(N);
    cardinality.resize(N);
    degree.resize(N);
    open.resize(N);
    closed.resize(N);
    deleted.resize(N);

    for (int i = 0; i < T; ++i) {
        cout << i << endl;
        n = N;
        for (int k = 0; k < N; ++k) {
            neighbors[k].clear();
            Y[k].clear();
            cardinality[k] = 0;
            degree[k] = 0;
            open[k] = false;
            closed[k] = false;
            deleted[k] = false;
            label[k] = "01";
        }

        for (int j = 0; j < M; ++j) {
            cin >> u >> v;
            degree[--u]++;
            degree[--v]++;
            neighbors[u].push_back(v);
            neighbors[v].push_back(u);
        }

        /*for (int node: nodes) {
            cout << "\n Node: " << node << endl << "Neighbors: ";
            for (int neighbor: neighbors[node]) {
                cout << neighbor << " ";
            }
        }*/
        cout << "Traversal:\n";
        traverse(0,0);
        cout << "certs\n" << certificate() << endl;
        certificates.push_back(certificate());
    }
    sort(certificates.begin(), certificates.end());
    int current = 1;
    vector<int> output;
    for (int i = 1; i < certificates.size(); ++i) {
        if (certificates[i] == certificates[i - 1]) {
            current++;
        } else {
            output.push_back(current);
            current = 1;
        }
    }
    output.push_back(current);
    sort(output.begin(), output.end());
    cout << "nazdar";
    for (int i : output) {
        cout << i << " ";
    }
    cout << endl;
    return 0;
}