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 Tp>
inline void read(Tp &x) {
  static char c;
  static bool neg;
  x = 0, c = getchar(), neg = false;
  for (; !isdigit(c); c = getchar()) {
    if (c == '-') {
      neg = true;
    }
  }
  for (; isdigit(c); c = getchar()) {
    x = x * 10 + c - '0';
  }
  if (neg) {
    x = -x;
  }
}
const int N = 100000 + 5;
int n, k;
int head[N], E = 0;
struct Edge {
  int to, next;
} e[N * 2];
inline void addEdge(int u, int v) {
  e[++E] = (Edge){v, head[u]};
  head[u] = E;
}
int dep[N], far[N], maxDep, maxDepNode;
bool vis[N];
int fa[N], dfn[N], tim = 0;
void dfs(int u, int far) {
  fa[u] = far;
  for (int i = head[u], v; i; i = e[i].next) {
    v = e[i].to;
    if (v != far) {
      dfs(v, u);
    }
  }
  dfn[++tim] = u;
}
int dp[N], ans[N];
inline int solve(int len) {
  int res = 0;
  fill(dp + 1, dp + n + 1, 1);
  for (int i = 1, u, far; i <= n; ++i) {
    u = dfn[i], far = fa[u];
    if (far != 0 && dp[far] != -1) {
      if (dp[u] != -1) {
        if (dp[u] + dp[far] >= len) {
          ++res;
          dp[far] = -1;
        } else {
          dp[far] = std::max(dp[far], dp[u] + 1);
        }
      }
    }
  }
  return res;
}
int main() {
  read(n);
  int brute = (int)ceil(sqrt(n * log2(n)));
  for (int i = 1, u, v; i < n; ++i) {
    read(u), read(v);
    addEdge(u, v);
    addEdge(v, u);
  }
  dfs(1, 0);
  ans[1] = n;
  for (int i = 2; i <= brute; ++i) {
    ans[i] = solve(i);
  }
  for (int i = brute + 1, l, r, mid, leftAns, res; i <= n; i = r + 1) {
    l = i, r = n;
    leftAns = solve(l);
    while (l <= r) {
      mid = (l + r) >> 1;
      if (solve(mid) == leftAns) {
        l = mid + 1;
        res = mid;
      } else {
        r = mid - 1;
      }
    }
    fill(ans + i, ans + res + 1, leftAns);
  }
  for (int i = 1; i <= n; ++i) {
    printf("%d\n", ans[i]);
  }
}
