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 RLEN = 1 << 18 | 1;
inline char nc() {
  static char ibuf[RLEN], *ib, *ob;
  (ib == ob) && (ob = (ib = ibuf) + fread(ibuf, 1, RLEN, stdin));
  return (ib == ob) ? -1 : *ib++;
}
inline int rd() {
  char ch = nc();
  int i = 0, f = 1;
  while (!isdigit(ch)) {
    if (ch == '-') f = -1;
    ch = nc();
  }
  while (isdigit(ch)) {
    i = (i << 1) + (i << 3) + ch - '0';
    ch = nc();
  }
  return i * f;
}
const int N = 1e5 + 50;
int n, len, ans[N], sum;
int g[N], nt[N * 2], vt[N * 2], ec;
int fa[N], q[N], li[N], tl;
inline void dfs_pre(int x, int f) {
  for (int e = g[x]; e; e = nt[e])
    if (vt[e] != f) dfs_pre(vt[e], x);
  q[++tl] = x;
  fa[x] = f;
}
inline void calc(int k) {
  if (~ans[k]) return;
  sum = 0;
  len = k;
  for (int i = 1; i <= n; i++) {
    int u = q[i], fir = 0, sec = 0;
    for (int j = g[u]; j; j = nt[j]) {
      int v = vt[j];
      if (v == fa[u]) continue;
      int val = li[v];
      if (fir < val)
        sec = fir, fir = val;
      else if (sec < val)
        sec = val;
    }
    if (fir + sec + 1 >= len) ++sum, fir = -1;
    li[u] = fir + 1;
  }
  ans[k] = sum;
}
inline void solve(int l, int r, int low, int up) {
  if (l > r) return;
  if (low == up) {
    for (int i = l; i <= r; i++) ans[i] = low;
    return;
  }
  calc(l);
  calc(r);
  low = ans[l], up = ans[r];
  if (low == up) {
    for (int i = l; i <= r; i++) ans[i] = low;
    return;
  } else {
    int mid = (l + r) >> 1;
    calc(mid);
    solve(l + 1, mid - 1, low, ans[mid]);
    solve(mid + 1, r - 1, ans[mid], up);
  }
}
inline void add(int x, int y) {
  nt[++ec] = g[x];
  g[x] = ec;
  vt[ec] = y;
}
inline void W(int x) {
  if (x >= 10) W(x / 10);
  putchar('0' + x % 10);
}
int main() {
  n = rd();
  memset(ans, -1, sizeof(ans));
  for (int i = 1; i < n; i++) {
    int x = rd(), y = rd();
    add(x, y);
    add(y, x);
  }
  dfs_pre(1, 0);
  solve(1, n, 0, n);
  for (int i = 1; i <= n; i++) W(ans[i]), putchar('\n');
}
