#include <iostream>
#include <vector>
#include <cmath>
#include "tree.h"
using namespace std;

vector<int> v[100005];
int par[100005];
void dfs(int i, int par) {
    ::par[i]=par;
    for(auto &x : v[i]) {
        if(x==par) continue;
        dfs(x, i);
    }
}

string encode(int n, vector<pair<int, int>> v) {
    for(auto &x : v) {
        ::v[x.first].push_back(x.second);
        ::v[x.second].push_back(x.first);
    }
    dfs(1, -1);
    string ans;
    for(int i = 2; i <= n; i++) {
        for(int j = 0; (1<<j)<=n; j++) {
            ans.push_back((char)('0'+(bool)(par[i]&(1<<j))));
        }
    }
    return ans;
}

vector<pair<int, int>> decode(int n, string s) {
    vector<pair<int,int>> ans;
    int ptr=0;
    for(int i = 2; i <= n; i++) {
        int p=0;
        for(int j = 0; (1<<j)<=n; j++) {
            p|=(1<<j)*(s[ptr]-'0');
            ptr++;
        }
        ans.push_back({p, i});
    }
    return ans;
}