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>
#pragma GCC optimize("Ofast", "inline")
using namespace std;
const int N = 100100;
int ans[N], dfn, a[N], fa[N];
int fst[N], nxt[N << 1], to[N << 1], E;
inline void add(int u, int v) { nxt[++E] = fst[u], fst[u] = E, to[E] = v; }
int len, a1[N], a2[N];
int slv(int x) {
  if (ans[x] != -1) return ans[x];
  memset(a1, 0, sizeof a1);
  memset(a2, 0, sizeof a2);
  int tot = 0;
  for (int i = dfn; i; --i) {
    int u = a[i];
    if (1 + a1[u] + a2[u] >= x)
      ++tot;
    else {
      int get = 1 + a1[u];
      u = fa[u];
      if (get > a1[u])
        a2[u] = a1[u], a1[u] = get;
      else if (a2[u] < get)
        a2[u] = get;
    }
  }
  return ans[x] = tot;
}
void pre(int u) {
  a[++dfn] = u;
  for (int v, i = fst[u]; ~i; i = nxt[i]) {
    v = to[i];
    if (v == fa[u]) continue;
    fa[v] = u, pre(v);
  }
}
int main() {
  memset(fst, -1, sizeof fst);
  memset(ans, -1, sizeof ans);
  int n, u, v;
  scanf("%d", &n);
  int H = min(1000, n);
  for (int i = 1; i < n; i++) {
    scanf("%d%d", &u, &v);
    add(u, v), add(v, u);
  }
  pre(1);
  int qwq = n;
  for (int i = 1; i <= H; i++) slv(i);
  for (int i = H + 1, las; i <= n; i = las + 1) {
    las = i;
    slv(i);
    for (int l = i + 1, r = qwq, mid = l + r >> 1; l <= r; mid = l + r >> 1) {
      if (slv(mid) == ans[i])
        l = mid + 1, las = mid;
      else {
        r = mid - 1;
        if (ans[mid] > ans[i] + 1) qwq = mid;
      }
    }
    for (int j = i + 1; j <= las; j++) ans[j] = ans[i];
  }
  for (int i = 1; i <= n; i++) printf("%d\n", ans[i]);
  return 0;
}
