OI XXXIII - ukr (Alt)

// https://szkopul.edu.pl/problemset/problem/_RHi9wOdNMRwWpB0piclsoL0/site/?key=statement

#include <bits/stdc++.h>

const int MAXN = 1000;
const int L = 11;
const int NUM_CODES = 1 << L;

int assigned_codes[MAXN + 1][2];
int code_to_id[NUM_CODES];

void init_codes() {
    std::mt19937 rng(42);

    std::vector<bool> used(NUM_CODES, false);

    for (int v = 1; v <= MAXN; ++v) {
        while (true) {
            int r = rng() % NUM_CODES;
            int r_comp = r ^ (NUM_CODES - 1);

            if (!used[r] && !used[r_comp] && r != r_comp) {
                assigned_codes[v][0] = r;
                assigned_codes[v][1] = r_comp;

                used[r] = true;
                used[r_comp] = true;

                code_to_id[r] = v;
                code_to_id[r_comp] = v;
                break;
            }
        }
    }
}

struct Edge {
    int to;
    int id;
    int rev_id;
    int index_in_adj;
};

void run_encoder() {
    int t;
    std::cin >> t;

    while (t--) {
        int n;
        std::cin >> n;

        std::vector<std::pair<int, int>> edges_input;
        std::vector<std::vector<std::pair<int, int>>> adj(n + 1);

        for (int i = 0; i < n - 1; ++i) {
            int u, v;
            std::cin >> u >> v;
            edges_input.push_back({u, v});
            adj[u].push_back({v, i});
            adj[v].push_back({u, i});
        }

        std::vector<std::map<int, int>> bit_indices(n + 1);

        for (int v = 1; v <= n; ++v) {
            std::sort(adj[v].begin(), adj[v].end(), [](const std::pair<int, int>& a, const std::pair<int, int>& b) { return a.second < b.second; });
            for (int k = 0; k < adj[v].size(); ++k) {
                bit_indices[v][adj[v][k].first] = k;
            }
        }

        std::vector<bool> is_active(n + 1, false);
        for (int v = 1; v <= n; ++v) {
            if (adj[v].size() >= L) {
                is_active[v] = true;
            }
        }

        std::string res_bits(n - 1, '0');

        std::vector<int> final_code(n + 1, -1);
        std::vector<bool> visited(n + 1, false);

        for (int i = 1; i <= n; ++i) {
            if (is_active[i] && !visited[i]) {
                std::vector<int> q;
                q.push_back(i);
                visited[i] = true;

                final_code[i] = assigned_codes[i][0];

                int head = 0;
                while (head < q.size()) {
                    int u = q[head++];

                    for (auto& edge : adj[u]) {
                        int v = edge.first;
                        int edge_idx = edge.second;

                        if (is_active[v]) {
                            if (!visited[v]) {
                                visited[v] = true;
                                int u_bit_pos = bit_indices[u][v];

                                int required_bit = 0;
                                if (u_bit_pos < L) {
                                    required_bit = (final_code[u] >> (L - 1 - u_bit_pos)) & 1;
                                } else {
                                    required_bit = 0;
                                }

                                int v_bit_pos = bit_indices[v][u];

                                if (v_bit_pos < L) {
                                    int code0 = assigned_codes[v][0];
                                    int bit0 = (code0 >> (L - 1 - v_bit_pos)) & 1;

                                    if (bit0 == required_bit) {
                                        final_code[v] = code0;
                                    } else {
                                        final_code[v] = assigned_codes[v][1];
                                    }
                                } else {
                                    final_code[v] = assigned_codes[v][0];
                                }

                                res_bits[edge_idx] = required_bit ? '1' : '0';

                                q.push_back(v);
                            }
                        } else {
                            int u_bit_pos = bit_indices[u][v];
                            if (u_bit_pos < L) {
                                int bit = (final_code[u] >> (L - 1 - u_bit_pos)) & 1;
                                res_bits[edge_idx] = bit ? '1' : '0';
                            } else {
                                res_bits[edge_idx] = '0';
                            }
                        }
                    }
                }
            }
        }

        std::cout << res_bits << "\n";
    }
    std::cout << L << "\n";
}

void run_decoder() {
    std::string line;
    while (std::cin >> line && line != "end") {
        int val = 0;
        for (int i = 0; i < L && i < line.size(); ++i) {
            val = (val << 1) | (line[i] - '0');
        }

        std::cout << code_to_id[val] << "\n";
    }
}

int main() {
    std::ios_base::sync_with_stdio(0);
    std::cin.tie(0);
    std::cout.tie(0);

    init_codes();

    std::string role;
    if (std::cin >> role) {
        if (role == "encoder") {
            run_encoder();
        } else {
            run_decoder();
        }
    }
    return 0;
}