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 + 5;
vector<int> adj[maxn];
int N, f[maxn], longest[maxn];
int res[maxn], ok[maxn];
signed main(void) {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  cin >> N;
  for (int i = 1; i < N; ++i) {
    int u, v;
    cin >> u >> v;
    adj[u].emplace_back(v);
    adj[v].emplace_back(u);
  }
  vector<int> vec;
  vector<int> par(N + 5);
  function<void(int, int)> dfs = [&](int u, int p) {
    par[u] = p;
    for (int v : adj[u])
      if (v != p) {
        dfs(v, u);
      }
    vec.emplace_back(u);
  };
  dfs(1, -1);
  auto solve = [&](int len) {
    if (ok[len]) return res[len];
    ok[len] = 1;
    for (auto& u : vec) {
      f[u] = 0;
      int mx1 = 0, mx2 = 0;
      for (int v : adj[u])
        if (v != par[u]) {
          f[u] += f[v];
          if (mx1 < longest[v]) {
            mx2 = mx1;
            mx1 = longest[v];
          } else if (mx2 < longest[v]) {
            mx2 = longest[v];
          }
        }
      if (mx1 + mx2 + 1 >= len) {
        f[u]++;
        longest[u] = 0;
      } else {
        longest[u] = mx1 + 1;
      }
    }
    return res[len] = f[1];
  };
  int k = 1;
  for (; k * k <= N; ++k) cout << solve(k) << '\n';
  while (k <= N) {
    int l = k + 1, r = N, mid;
    int now = solve(k);
    while (l <= r) {
      mid = (l + r) / 2;
      if (solve(mid) == now)
        l = mid + 1;
      else
        r = mid - 1;
    }
    for (int i = k; i <= r; ++i) {
      cout << now << '\n';
    }
    k = l;
  }
}
