#include <bits/stdc++.h>
#define all(v) begin(v), end(v)
using namespace std;
const int MX = 1e5;
struct Tree{
vector<int> adj[MX];
int depth[MX];
int parent[MX];
vector<int> layers[MX];
int maxDepth;
void addEdge(int u, int v) {
adj[u].push_back(v);
adj[v].push_back(u);
}
void dfs(int u, int p = -1) {
maxDepth = max(maxDepth, depth[u]);
parent[u] = p;
layers[depth[u]].push_back(u);
for (int v : adj[u]) {
if (v == p) continue;
depth[v] = depth[u] + 1;
dfs(v, u);
}
}
vector<int> encode(int root, int n) { //O(n log n)
//The code will have size exactly 2n - 1
maxDepth = 0;
depth[root] = 0;
dfs(root);
vector<int> label(n);
vector<int> code;
vector<vector<int>> childrenCode(n);
auto cmpNode = [&](int &u, int &v) {
return childrenCode[u] < childrenCode[v];
};
for (int d = maxDepth; d >= 0; d--) {
sort(layers[d].begin(), layers[d].end(), cmpNode);
for (int i = 0; i < layers[d].size(); i++) {
//***************Label Assignment**********************
int u = layers[d][i];
if (i == 0) label[u] = 1;
else {
int prev = layers[d][i - 1];
label[u] = label[prev];
if (childrenCode[u] != childrenCode[prev]) {
label[u]++;
}
}
//Keep building childrenCode of the parent of u
if (d != 0) childrenCode[parent[u]].push_back(label[u]);
//***************Code generation**********************
code.push_back(0); //group separator
copy(all(childrenCode[u]), back_inserter(code));
}
layers[d].clear();
}
return code;
}
} tree;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
//USAGE
int n;
cin >> n;
for (int i = 0; i < n - 1; i++) {
int u, v;
cin >> u >> v;
u--;
v--;
tree.addEdge(u, v);
}
int root = 0;
auto code = tree.encode(root, n);
for (int x : code) cout << x << " ";
cout << "\n";
return 0;
}
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CiNkZWZpbmUgYWxsKHYpIGJlZ2luKHYpLCBlbmQodikKdXNpbmcgbmFtZXNwYWNlIHN0ZDsKCmNvbnN0IGludCBNWCA9IDFlNTsKc3RydWN0IFRyZWV7Cgl2ZWN0b3I8aW50PiBhZGpbTVhdOwoJaW50IGRlcHRoW01YXTsKCWludCBwYXJlbnRbTVhdOwoJdmVjdG9yPGludD4gbGF5ZXJzW01YXTsKCWludCBtYXhEZXB0aDsKCQoJdm9pZCBhZGRFZGdlKGludCB1LCBpbnQgdikgewoJCWFkalt1XS5wdXNoX2JhY2sodik7CgkJYWRqW3ZdLnB1c2hfYmFjayh1KTsKCX0KCQoJdm9pZCBkZnMoaW50IHUsIGludCBwID0gLTEpIHsKCQltYXhEZXB0aCA9IG1heChtYXhEZXB0aCwgZGVwdGhbdV0pOwoJCXBhcmVudFt1XSA9IHA7CgkJbGF5ZXJzW2RlcHRoW3VdXS5wdXNoX2JhY2sodSk7CgkJZm9yIChpbnQgdiA6IGFkalt1XSkgewoJCQlpZiAodiA9PSBwKSBjb250aW51ZTsKCQkJZGVwdGhbdl0gPSBkZXB0aFt1XSArIDE7CgkJCWRmcyh2LCB1KTsKCQl9Cgl9CgkKCXZlY3RvcjxpbnQ+IGVuY29kZShpbnQgcm9vdCwgaW50IG4pIHsgLy9PKG4gbG9nIG4pCgkJLy9UaGUgY29kZSB3aWxsIGhhdmUgc2l6ZSBleGFjdGx5IDJuIC0gMQoJCW1heERlcHRoID0gMDsKCQlkZXB0aFtyb290XSA9IDA7CgkJZGZzKHJvb3QpOwoJCQoJCXZlY3RvcjxpbnQ+IGxhYmVsKG4pOwoJCXZlY3RvcjxpbnQ+IGNvZGU7CgkJdmVjdG9yPHZlY3RvcjxpbnQ+PiBjaGlsZHJlbkNvZGUobik7CgkJYXV0byBjbXBOb2RlID0gWyZdKGludCAmdSwgaW50ICZ2KSB7CgkJCXJldHVybiBjaGlsZHJlbkNvZGVbdV0gPCBjaGlsZHJlbkNvZGVbdl07CgkJfTsKCQlmb3IgKGludCBkID0gbWF4RGVwdGg7IGQgPj0gMDsgZC0tKSB7CgkJCXNvcnQobGF5ZXJzW2RdLmJlZ2luKCksIGxheWVyc1tkXS5lbmQoKSwgY21wTm9kZSk7CgkJCWZvciAoaW50IGkgPSAwOyBpIDwgbGF5ZXJzW2RdLnNpemUoKTsgaSsrKSB7CgkJCQkvLyoqKioqKioqKioqKioqKkxhYmVsIEFzc2lnbm1lbnQqKioqKioqKioqKioqKioqKioqKioqCgkJCQlpbnQgdSA9IGxheWVyc1tkXVtpXTsKCQkJCWlmIChpID09IDApIGxhYmVsW3VdID0gMTsKCQkJCWVsc2UgewoJCQkJCWludCBwcmV2ID0gbGF5ZXJzW2RdW2kgLSAxXTsKCQkJCQlsYWJlbFt1XSA9IGxhYmVsW3ByZXZdOwoJCQkJCWlmIChjaGlsZHJlbkNvZGVbdV0gIT0gY2hpbGRyZW5Db2RlW3ByZXZdKSB7CgkJCQkJCWxhYmVsW3VdKys7CgkJCQkJfQoJCQkJfQoJCQkJLy9LZWVwIGJ1aWxkaW5nIGNoaWxkcmVuQ29kZSBvZiB0aGUgcGFyZW50IG9mIHUKCQkJCWlmIChkICE9IDApIGNoaWxkcmVuQ29kZVtwYXJlbnRbdV1dLnB1c2hfYmFjayhsYWJlbFt1XSk7CgkJCQkvLyoqKioqKioqKioqKioqKkNvZGUgZ2VuZXJhdGlvbioqKioqKioqKioqKioqKioqKioqKioKCQkJCWNvZGUucHVzaF9iYWNrKDApOyAvL2dyb3VwIHNlcGFyYXRvcgoJCQkJY29weShhbGwoY2hpbGRyZW5Db2RlW3VdKSwgYmFja19pbnNlcnRlcihjb2RlKSk7CgkJCX0KCQkJbGF5ZXJzW2RdLmNsZWFyKCk7CgkJfQoJCXJldHVybiBjb2RlOwoJfQp9IHRyZWU7CgppbnQgbWFpbigpIHsKCWlvc19iYXNlOjpzeW5jX3dpdGhfc3RkaW8oZmFsc2UpOwoJY2luLnRpZSgwKTsKCQoJLy9VU0FHRQoJaW50IG47CgljaW4gPj4gbjsKCWZvciAoaW50IGkgPSAwOyBpIDwgbiAtIDE7IGkrKykgewoJCWludCB1LCB2OwoJCWNpbiA+PiB1ID4+IHY7CgkJdS0tOwoJCXYtLTsKCQl0cmVlLmFkZEVkZ2UodSwgdik7Cgl9CglpbnQgcm9vdCA9IDA7CglhdXRvIGNvZGUgPSB0cmVlLmVuY29kZShyb290LCBuKTsKCWZvciAoaW50IHggOiBjb2RlKSBjb3V0IDw8IHggPDwgIiAiOwoJY291dCA8PCAiXG4iOwoJcmV0dXJuIDA7Cn0K