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 N = 100010;
int n, tot, tim, head[N], ans[N], f[N], fa[N], ed[N], hpr[N], hpo[N];
struct Edge {
  int suiv, ver;
} e[N << 1];
inline void lnk(int x, int y) {
  e[++tot].ver = y;
  e[tot].suiv = head[x];
  head[x] = tot;
}
inline void dfs(int x) {
  for (int i = head[x]; i; i = e[i].suiv) {
    int y = e[i].ver;
    if (y == fa[x]) continue;
    fa[y] = x, dfs(y);
  }
  ed[++tim] = x;
}
inline int cal(int k) {
  int res = 0;
  for (int i = 1; i <= n; i++) f[i] = hpr[i] = hpo[i] = 0;
  for (int i = 1; i <= n; i++) {
    int x = ed[i];
    if (hpr[x] + hpo[x] + 1 >= k)
      f[x] = 0, res++;
    else
      f[x] = hpr[x] + 1;
    if (!fa[x]) continue;
    if (f[x] > hpr[fa[x]])
      hpo[fa[x]] = hpr[fa[x]], hpr[fa[x]] = f[x];
    else if (f[x] > hpo[fa[x]])
      hpo[fa[x]] = f[x];
  }
  return res;
}
int main() {
  scanf("%d", &n);
  for (int i = 1, x, y; i < n; i++) scanf("%d%d", &x, &y), lnk(x, y), lnk(y, x);
  int block = (int)sqrt(n * log(n) / log(2));
  ans[1] = n;
  dfs(1);
  for (int i = 2; i <= block; i++) ans[i] = cal(i);
  for (int L = block + 1, R; L <= n; L = R + 1) {
    int tem = cal(L), r = n, l = L;
    R = L;
    while (l <= r) {
      int mid = l + r >> 1;
      if (cal(mid) == tem)
        l = mid + 1, R = mid;
      else
        r = mid - 1;
    }
    for (int i = L; i <= R; i++) ans[i] = tem;
  }
  for (int i = 1; i <= n; i++) printf("%d\n", ans[i]);
  return 0;
}
