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;
template <typename T>
istream& operator>>(istream& is, vector<T>& v) {
  for (auto& i : v) is >> i;
  return is;
}
template <typename T>
ostream& operator<<(ostream& os, vector<T>& v) {
  for (auto& i : v) os << i << ' ';
  return os;
}
template <typename T, typename U>
istream& operator>>(istream& is, pair<T, U>& p) {
  is >> p.first >> p.second;
  return is;
}
template <typename T, typename U>
ostream& operator<<(ostream& os, pair<T, U>& p) {
  os << p.first << ' ' << p.second;
  return os;
}
template <typename T, typename U>
pair<T, U> operator-(pair<T, U> a, pair<T, U> b) {
  return make_pair(a.first - b.first, a.second - b.second);
}
template <typename T, typename U>
pair<T, U> operator+(pair<T, U> a, pair<T, U> b) {
  return make_pair(a.first + b.first, a.second + b.second);
}
const int nax = 100007;
array<pair<int, int>, nax> dp;
array<int, nax> mem;
array<int, nax> ans;
int main() {
  mem.fill(-1);
  ans.fill(0);
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  auto start_time = clock();
  int n;
  cin >> n;
  vector<vector<int>> g(n);
  for (int i = 0; i < n - 1; ++i) {
    int u, v;
    cin >> u >> v;
    --u;
    --v;
    g[u].push_back(v);
    g[v].push_back(u);
  }
  vector<vector<int>> g1(n);
  vector<bool> used(n, false);
  vector<int> topsort(n);
  int top_ind = -1;
  function<void(int)> dfs0 = [&](int v) {
    used[v] = true;
    for (auto k : g[v])
      if (!used[k]) {
        g1[v].push_back(k);
        dfs0(k);
      }
    topsort[++top_ind] = v;
  };
  dfs0(0);
  42;
  ;
  auto ask = [&](int k) {
    if (k > n) return 0;
    if (mem[k] != -1) return mem[k];
    for (auto v : topsort) {
      dp[v] = {0, 0};
      int mx1 = 0, mx2 = 0;
      for (auto u : g1[v]) {
        dp[v].first += dp[u].first;
        if (dp[u].second >= mx1) {
          mx2 = mx1;
          mx1 = dp[u].second;
        } else if (dp[u].second > mx2) {
          mx2 = dp[u].second;
        }
      }
      if (mx1 + mx2 + 1 >= k)
        ++dp[v].first;
      else
        dp[v].second = mx1 + 1;
    }
    mem[k] = dp[0].first;
    return dp[0].first;
  };
  int K = min(n, 700);
  for (int i = 1; i <= K; ++i) ans[i] = ask(i);
  int L = K + 1;
  int f = ask(L);
  while (f > 0) {
    int l = L, r = n + 1;
    while (r - l > 1) {
      int c = (l + r) / 2;
      int u = ask(c);
      if (u >= f)
        l = c;
      else
        r = c;
    }
    for (int i = L; i <= l; ++i) ans[i] = f;
    L = r;
    f = ask(L);
    if (1.0 * (clock() - start_time) / CLOCKS_PER_SEC > 6.9) break;
  }
  for (int i = 1; i <= n; ++i) cout << ans[i] << '\n';
  return 0;
}
