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 target("arch=corei7-avx")
using namespace std;
char ss[1 << 20], *A = ss, *B = ss;
inline char gc() {
  if (A == B) {
    B = (A = ss) + fread(ss, 1, 1 << 20, stdin);
  }
  return *A++;
}
inline void read(int &x) {
  x = 0;
  char c = gc();
  for (; !(c <= '9' && c >= '0'); c = gc())
    ;
  for (; (c <= '9' && c >= '0'); c = gc()) x = (x << 3) + (x << 1) + c - '0';
}
int n, ans[101000], f[101000], dft, a[101000], fa[101000];
vector<int> G[101000];
void pre(int x, int fff) {
  a[++dft] = x;
  fa[x] = fff;
  for (auto y : G[x])
    if (y != fff) pre(y, x);
}
int gao(int k) {
  if (~ans[k]) return ans[k];
  int res = 0;
  memset(f, 0, sizeof f);
  for (int i = n; i; --i) {
    int x = a[i], mx = 0, mx2 = 0;
    for (auto &y : G[x])
      if (y != fa[x]) {
        int t = f[y];
        if (t > mx) {
          mx2 = mx;
          mx = t;
        } else if (t > mx2) {
          mx2 = t;
        }
      }
    if (++mx + mx2 >= k)
      ++res, f[x] = 0;
    else
      f[x] = mx;
  }
  return ans[k] = res;
}
void doit(int l, int r) {
  if (gao(l) == gao(r)) {
    for (int i = l; i <= r; ++i) ans[i] = ans[l];
    return;
  }
  if (l + 1 >= r) return;
  int mid = l + r >> 1;
  doit(l, mid);
  doit(mid, r);
}
int main() {
  read(n);
  int u, v;
  for (int i = 1; i < n; ++i) {
    read(u);
    read(v);
    G[u].push_back(v);
    G[v].push_back(u);
  }
  srand(time(0));
  pre(rand() % n + 1, 0);
  memset(ans, -1, sizeof ans);
  ans[1] = n;
  int s;
  for (s = 2; s <= min(1000, n); ++s) gao(s);
  doit(s - 1, n);
  for (int i = 1; i <= n; ++i) printf("%d\n", ans[i]);
}
