OI XXXIII - ukr

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

#include <bits/stdc++.h>

// #define GARY_DBG
#define GARY_LIB

constexpr int sizik = 10 * 1001;

#define ar std::array

typedef std::vector<std::vector<std::pair<int, int>>> _kra;

int ans[sizik];

void DFS(int v, int p, const _kra& kra, int p_edge, int p_edge_val) {
    if (p_edge >= 1) {
        ans[p_edge] = p_edge_val;
    }
    std::vector<int> ids;
    ids.reserve(kra[v].size());
    for (const auto& [u, idx] : kra[v]) {
        ids.push_back(idx);
    }
    assert(std::is_sorted(ids.begin(), ids.end()));
    if (ids.size() >= 11) {
        bool rev = false;
        if (ids[0] == p_edge) {
            rev = p_edge_val;
        } else {
            for (int i = 1; i <= 10; i++) {
                if (ids[i] == p_edge) {
                    rev = (p_edge_val != (!!(v & (1 << (i - 1)))));
                    break;
                }
            }
        }
        int cnt = 0;
        for (const auto& [u, idx] : kra[v]) {
            if (u == p) {
                cnt++;
                continue;
            }
            bool c = cnt > 0 ? !!(v & (1 << (cnt - 1))) : 0;
            bool V = cnt > 11 ? 0 : cnt == 0 ? rev : rev ? !c : c;
            cnt++;
            DFS(u, v, kra, idx, V);
        }
    } else {
        for (const auto& [u, idx] : kra[v]) {
            if (u == p) continue;
            DFS(u, v, kra, idx, 0);
        }
    }
}

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

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

        _kra kra(n + 1);

        for (int i = 1; i <= n - 1; i++) {
            int a, b;
            std::cin >> a >> b;

            kra[a].push_back({b, i});
            kra[b].push_back({a, i});
        }

        DFS(1, -1, kra, -1, 0);

        for (int i = 1; i <= n - 1; i++) {
            std::cout << ans[i];
        }
        std::cout << '\n';
    }

    std::cout << "11\n";
}

void decoder() {
    std::string s;
    while (true) {
        std::cin >> s;
        if (s == "end") {
            break;
        }
        bool isRev = s[0] - '0';
        int res = 0;
        for (int i = 1; i <= 10; i++) {
            if ((isRev && s[i] == '0') || (!isRev && s[i] == '1')) {
                res |= (1 << (i - 1));
            }
        }
        std::cout << res << '\n';
    }
}

void solve() {
    std::string s;
    std::cin >> s;

    if (s[0] == 'e') {
        encoder();
    } else {
        decoder();
    }
}

int32_t main() {
#ifndef GARY_DBG
    std::ios_base::sync_with_stdio(0);
    std::cin.tie(0);
    std::cout.tie(0);
#endif

    int t = 1;
    // std::cin >> t;

    for (; t > 0; t--) {
        solve();
    }

    return 0;
}