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 = 100100;
int N;
vector<int> edge[MAXN];
int nord;
int ord[MAXN];
int par[MAXN];
int res[MAXN];
void flood(int cloc, int last) {
  ord[nord++] = cloc;
  par[cloc] = last;
  for (int i = 0; i < edge[cloc].size(); i++) {
    int neigh = edge[cloc][i];
    if (neigh == last) continue;
    flood(neigh, cloc);
  }
}
int ans;
int m1[MAXN], m2[MAXN];
int get_res(int K) {
  for (int i = 0; i < N; i++) m1[i] = m2[i] = 0;
  ans = 0;
  for (int i = N - 1; i >= 0; i--) {
    int cloc = ord[i];
    if (m1[cloc] + m2[cloc] + 1 >= K)
      ans++;
    else if (i > 0) {
      if (m1[cloc] + 1 > m2[par[cloc]]) {
        m2[par[cloc]] = m1[cloc] + 1;
      }
      if (m2[par[cloc]] > m1[par[cloc]]) swap(m1[par[cloc]], m2[par[cloc]]);
    }
  }
  res[K] = ans;
  return ans;
}
void run(int lo, int hi, int rlo, int rhi) {
  if (lo > hi) return;
  if (rlo == rhi) {
    for (int i = lo; i <= hi; i++) res[i] = rlo;
    return;
  }
  int mid = (lo + hi) / 2;
  int mval = get_res(mid);
  run(lo, mid - 1, mval, rhi);
  run(mid + 1, hi, rlo, mval);
}
int main() {
  ios_base::sync_with_stdio(0);
  cin >> N;
  for (int i = 0; i < N - 1; i++) {
    int x, y;
    cin >> x >> y;
    x--, y--;
    edge[x].push_back(y);
    edge[y].push_back(x);
  }
  nord = 0;
  flood(0, -1);
  run(1, N, 0, N);
  for (int i = 1; i <= N; i++) cout << res[i] << "\n";
}
