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;
vector<int> G[100005];
int num = 0;
int dfs(int u, int pa, int k) {
  int max_rem[2] = {};
  for (int v : G[u])
    if (v != pa) {
      int tem = dfs(v, u, k);
      if (tem >= max_rem[0])
        max_rem[1] = max_rem[0], max_rem[0] = tem;
      else if (tem > max_rem[1])
        max_rem[1] = tem;
    }
  int ret = 0;
  if (1 + max_rem[0] + max_rem[1] >= k)
    num++;
  else
    ret = 1 + max_rem[0];
  return ret;
}
int cal(int k) {
  num = 0;
  dfs(1, 1, k);
  return num;
}
int ans[100005];
void solve(int l, int r, int ql, int qr) {
  if (ql > qr) return;
  if (l == r) {
    for (int i = ql; i <= qr; i++) ans[i] = l;
  } else {
    int mid = (ql + qr) >> 1;
    ans[mid] = cal(mid);
    solve(l, ans[mid], ql, mid - 1);
    solve(ans[mid], r, mid + 1, qr);
  }
}
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  int n;
  cin >> n;
  for (int i = 1, u, v; i < n; i++) {
    cin >> u >> v;
    G[u].push_back(v);
    G[v].push_back(u);
  }
  ans[1] = n;
  ans[n] = cal(n);
  solve(ans[1], ans[n], 2, n - 1);
  for (int i = 1; i <= n; i++) cout << ans[i] << '\n';
  return 0;
}
