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 MAXN = 100111;
int N, K;
struct Vert {
  int FE;
  int Len;
} V[MAXN];
struct Edge {
  int y, next;
} E[MAXN << 1];
int Ecnt;
void addE(int a, int b) {
  ++Ecnt;
  E[Ecnt].y = b;
  E[Ecnt].next = V[a].FE;
  V[a].FE = Ecnt;
}
int Ret;
void DFS(int at, int f = 0) {
  int _ = 1, __ = 0, l;
  for (int k = V[at].FE, to; k > 0; k = E[k].next) {
    to = E[k].y;
    if (to == f) continue;
    DFS(to, at);
    l = V[to].Len + 1;
    if (l > __) {
      if (l > _) swap(l, _);
      __ = l;
    }
  }
  if (_ + __ - 1 >= K) {
    ++Ret;
    V[at].Len = 0;
  } else
    V[at].Len = _;
}
int Ans[MAXN];
int C[MAXN];
inline int lowbit(int a) { return a & (-a); }
void Put(int at, int v) {
  for (int i = at; i <= N; i += lowbit(i)) C[i] = min(C[i], v);
}
int Ask(int at) {
  int ret = N;
  for (int i = at; i > 0; i -= lowbit(i)) ret = min(ret, C[i]);
  return ret;
}
int Calc(int k) {
  if (Ans[k] == N) {
    K = k;
    Ret = 0;
    DFS(1);
    Ans[k] = Ret;
    Put(k, Ret);
  }
  return Ans[k];
}
int Find(int l, int r, int v) {
  if (v == 0) return r;
  int m;
  while (l < r) {
    m = (l + r) >> 1;
    if (Ask(m) < v || Calc(m) < v)
      r = m;
    else
      l = m + 1;
  }
  m = (l + r) >> 1;
  return m;
}
int main() {
  ios_base::sync_with_stdio(false);
  cin >> N;
  for (int i = 1, a, b; i < N; ++i) {
    cin >> a >> b;
    addE(a, b);
    addE(b, a);
  }
  for (int i = 1; i <= N; ++i) {
    Ans[i] = N;
    C[i] = N;
  }
  int Bs;
  for (Bs = 1; Bs <= N / Bs; ++Bs)
    ;
  for (int i = 2; i <= Bs; ++i) Calc(i);
  for (int l = Bs + 1, r; l <= N; l = r) {
    Calc(l);
    r = Find(l + 1, N + 1, Ans[l]);
  }
  for (int i = 2; i <= N; ++i) Ans[i] = min(Ans[i], Ans[i - 1]);
  for (int i = 1; i <= N; ++i) cout << Ans[i] << endl;
  return 0;
}
