#include <bits/stdc++.h>
using namespace std;
class LCASparseTable{
public:
long long len;
vector<vector<int> > up;
vector<int> tin;
vector<int> tout;
int time;
int n;
vector<vector<int> > tree;
LCASparseTable(int n){
this -> n = n;
tree.resize(n + 5);
up.resize(25);
for(int i = 0; i < 25; ++i){
up[i].resize(n + 5);
}
tin.resize(n + 5);
tout.resize(n + 5);
len = 1;
while((1ll << len) <= n){
++len;
}
}
void dfs(int u, int p){
tin[u] = time++;
up[0][u] = p;
for(int i = 1; i < len; ++i){
up[i][u] = up[i - 1][up[i - 1][u]];
}
for(auto v : tree[u]){
if(v != p){
dfs(v, u);
}
}
tout[u] = time++;
}
void build(int root){
dfs(root, root);
}
bool isParent(int parent, int child){
return tin[parent] <= tin[child] && tout[child] <= tout[parent];
}
int lca(int a, int b){
if(isParent(a, b)) return a;
if(isParent(b, a)) return b;
for(int i = len - 1; i >= 0; --i){
if(!isParent(up[i][a], b)){
a = up[i][a];
}
}
return up[0][a];
}
};
int main(){
int n;
cin >> n;
LCASparseTable lcast(n);
int x, y;
for(int i = 0; i < n - 1; ++i){
scanf("%d%d", &x, &y);
lcast.tree[x].push_back(y);
lcast.tree[y].push_back(x);
}
lcast.build(1);
for(int i = 1; i <= n; ++i){
for(int j = 1; j <= n; ++j){
printf("%d-%d: %d\n", i, j, lcast.lca(i, j));
}
}
return 0;
}
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+Cgp1c2luZyBuYW1lc3BhY2Ugc3RkOwoKY2xhc3MgTENBU3BhcnNlVGFibGV7CnB1YmxpYzoKICAgbG9uZyBsb25nIGxlbjsKICAgdmVjdG9yPHZlY3RvcjxpbnQ+ID4gdXA7CiAgIHZlY3RvcjxpbnQ+IHRpbjsKICAgdmVjdG9yPGludD4gdG91dDsKICAgaW50IHRpbWU7CiAgIGludCBuOwogICB2ZWN0b3I8dmVjdG9yPGludD4gPiB0cmVlOwoKICAgTENBU3BhcnNlVGFibGUoaW50IG4pewogICAgICB0aGlzIC0+IG4gPSBuOwogICAgICB0cmVlLnJlc2l6ZShuICsgNSk7CiAgICAgIHVwLnJlc2l6ZSgyNSk7CiAgICAgIGZvcihpbnQgaSA9IDA7IGkgPCAyNTsgKytpKXsKICAgICAgICAgdXBbaV0ucmVzaXplKG4gKyA1KTsKICAgICAgfQogICAgICB0aW4ucmVzaXplKG4gKyA1KTsKICAgICAgdG91dC5yZXNpemUobiArIDUpOwogICAgICBsZW4gPSAxOwogICAgICB3aGlsZSgoMWxsIDw8IGxlbikgPD0gbil7CiAgICAgICAgICsrbGVuOwogICAgICB9CiAgIH0KCiAgIHZvaWQgZGZzKGludCB1LCBpbnQgcCl7CiAgICAgIHRpblt1XSA9IHRpbWUrKzsKICAgICAgdXBbMF1bdV0gPSBwOwogICAgICBmb3IoaW50IGkgPSAxOyBpIDwgbGVuOyArK2kpewogICAgICAgICB1cFtpXVt1XSA9IHVwW2kgLSAxXVt1cFtpIC0gMV1bdV1dOwogICAgICB9CiAgICAgIGZvcihhdXRvIHYgOiB0cmVlW3VdKXsKICAgICAgICAgaWYodiAhPSBwKXsKICAgICAgICAgICAgZGZzKHYsIHUpOwogICAgICAgICB9CiAgICAgIH0KICAgICAgdG91dFt1XSA9IHRpbWUrKzsKICAgfQoKICAgdm9pZCBidWlsZChpbnQgcm9vdCl7CiAgICAgIGRmcyhyb290LCByb290KTsKICAgfQoKICAgYm9vbCBpc1BhcmVudChpbnQgcGFyZW50LCBpbnQgY2hpbGQpewogICAgICByZXR1cm4gdGluW3BhcmVudF0gPD0gdGluW2NoaWxkXSAmJiB0b3V0W2NoaWxkXSA8PSB0b3V0W3BhcmVudF07CiAgIH0KCiAgIGludCBsY2EoaW50IGEsIGludCBiKXsKICAgICAgaWYoaXNQYXJlbnQoYSwgYikpIHJldHVybiBhOwogICAgICBpZihpc1BhcmVudChiLCBhKSkgcmV0dXJuIGI7CiAgICAgIGZvcihpbnQgaSA9IGxlbiAtIDE7IGkgPj0gMDsgLS1pKXsKICAgICAgICAgaWYoIWlzUGFyZW50KHVwW2ldW2FdLCBiKSl7CiAgICAgICAgICAgIGEgPSB1cFtpXVthXTsKICAgICAgICAgfQogICAgICB9CiAgICAgIHJldHVybiB1cFswXVthXTsKICAgfQp9OwoKaW50IG1haW4oKXsKICAgaW50IG47CiAgIGNpbiA+PiBuOwogICBMQ0FTcGFyc2VUYWJsZSBsY2FzdChuKTsKICAgaW50IHgsIHk7CiAgIGZvcihpbnQgaSA9IDA7IGkgPCBuIC0gMTsgKytpKXsKICAgICAgc2NhbmYoIiVkJWQiLCAmeCwgJnkpOwogICAgICBsY2FzdC50cmVlW3hdLnB1c2hfYmFjayh5KTsKICAgICAgbGNhc3QudHJlZVt5XS5wdXNoX2JhY2soeCk7CiAgIH0KICAgbGNhc3QuYnVpbGQoMSk7CiAgIGZvcihpbnQgaSA9IDE7IGkgPD0gbjsgKytpKXsKICAgICAgZm9yKGludCBqID0gMTsgaiA8PSBuOyArK2opewogICAgICAgICBwcmludGYoIiVkLSVkOiAlZFxuIiwgaSwgaiwgbGNhc3QubGNhKGksIGopKTsKICAgICAgfQogICB9CiAgIHJldHVybiAwOwp9Cg==