A tree is an undirected graph with exactly one simple path between each pair of vertices. We call a set of simple paths k-valid if each vertex of the tree belongs to no more than one of these paths (including endpoints) and each path consists of exactly k vertices.

You are given a tree with n vertices. For each k from 1 to n inclusive find what is the maximum possible size of a k-valid set of simple paths.

Input

The first line of the input contains a single integer n (2 ≤ n ≤ 100 000) — the number of vertices in the tree.

Then following n - 1 lines describe the tree, each of them contains two integers v, u (1 ≤ v, u ≤ n) — endpoints of the corresponding edge.

It is guaranteed, that the given graph is a tree. 

Output

Output n numbers, the i-th of which is the maximum possible number of paths in an i-valid set of paths.

Examples

Input

7
1 2
2 3
3 4
4 5
5 6
6 7


Output

7
3
2
1
1
1
1



Input

6
1 2
2 3
2 4
1 5
5 6


Output

6
2
2
1
1
0

Note

One way to achieve the optimal number of paths for the second sample is illustrated in the following picture:

<image>
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 7, mod = 1e9 + 7, MAXN = 1e6 + 7;
const double eps = 1e-9;
const long long inf = 1e18;
mt19937 rnd(time(0));
int n;
vector<int> gr[maxn];
pair<int, int> dfs(int u, int pr, int k) {
  int ans = 0;
  int mx1 = 0, mx2 = 0;
  for (auto v : gr[u]) {
    if (v == pr) continue;
    pair<int, int> t = dfs(v, u, k);
    ans += t.first;
    if (mx1 < t.second) {
      mx2 = mx1;
      mx1 = t.second;
    } else if (mx2 < t.second) {
      mx2 = t.second;
    }
  }
  if (mx1 + mx2 + 1 >= k) {
    return {ans + 1, 0};
  }
  return {ans, mx1 + 1};
}
int get(int k) { return dfs(0, 0, k).first; }
int binn(int x, int cnt) {
  int l = x;
  int m;
  int r = n;
  while (l + 1 < r) {
    m = (l + r) / 2;
    if (get(m) == cnt)
      l = m;
    else
      r = m;
  }
  return l;
}
struct state {
  int l, r, cnt;
};
int tin[maxn];
int tm228 = 0;
vector<int> gr1[maxn];
void dfs(int u, int pr) {
  tin[u] = tm228++;
  for (auto v : gr[u]) {
    if (v != pr) dfs(v, u);
  }
}
void rebuild() {
  dfs(0, 0);
  for (int i = 0; i < n; ++i) {
    for (auto v : gr[i]) {
      gr1[tin[i]].push_back(tin[v]);
    }
  }
  for (int i = 0; i < n; ++i) {
    gr[tin[i]] = gr1[tin[i]];
  }
}
int block = 1000;
void solve() {
  cin >> n;
  for (int i = 0; i < n - 1; ++i) {
    int a, b;
    cin >> a >> b, --a, --b;
    gr[a].push_back(b);
    gr[b].push_back(a);
  }
  rebuild();
  block = min(block, n);
  for (int i = 1; i < block; ++i) {
    cout << get(i) << '\n';
  }
  vector<state> res;
  for (int l = block; l <= n;) {
    int cnt = get(l);
    int r = binn(l, cnt);
    res.push_back({l, r, cnt});
    l = r + 1;
  }
  for (auto v : res) {
    for (int i = v.l; i <= v.r; ++i) cout << v.cnt << '\n';
  }
}
signed main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.precision(20);
  cout << fixed;
  int t = 1;
  for (int i = 0; i < t; ++i) {
    solve();
  }
  return 0;
}
