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 = 1.001E5;
int f[MAXN];
int ans[MAXN];
int rev[MAXN];
int fa[MAXN];
vector<int> adj[MAXN];
int n, cc;
void getPre(int u, int pa) {
  rev[++cc] = u;
  for (int v : adj[u])
    if (v != pa) fa[v] = u, getPre(v, u);
}
inline int getAns(int lim) {
  int res = 0;
  for (int i = 1; i <= n; ++i) f[i] = 1;
  for (int i = n; i; --i)
    if (fa[rev[i]] && (f[fa[rev[i]]] != -1) && (f[rev[i]] != -1))
      (f[fa[rev[i]]] + f[rev[i]] >= lim)
          ? (++res, f[fa[rev[i]]] = -1)
          : (f[fa[rev[i]]] = max(f[fa[rev[i]]], f[rev[i]] + 1));
  return res;
}
int main(void) {
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  cin >> n;
  for (int i = 2, a, b; i <= n; ++i)
    cin >> a >> b, adj[a].push_back(b), adj[b].push_back(a);
  getPre(n, n), ans[1] = n;
  int sz = sqrt(n * log2(n));
  for (int i = 2; i <= sz; ++i) ans[i] = getAns(i);
  for (int l = sz + 1, r = sz + 1, a = l, b = n, mid, res = 0, need = getAns(r);
       l <= n && r <= n;
       r = res, l = r + 1, r = l, a = l, b = n, res = 0, need = getAns(r)) {
    while (a <= b)
      (getAns(mid = a + b >> 1) == need) ? (res = mid, a = mid + 1)
                                         : (b = mid - 1);
    for (int j = l; j <= res; ++j) ans[j] = need;
  }
  for (int i = 1; i <= n; ++i) cout << ans[i] << '\n';
  return 0;
}
