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>
const int ms = 100100;
const int bs = 1000;
int n;
std::vector<int> edges[ms];
std::vector<std::pair<int, int>> trans;
void clean(int on, int par) {
  for (int i = 0; i < (int)edges[on].size(); i++) {
    if (edges[on][i] == par) {
      edges[on][i] = edges[on].back();
      edges[on].pop_back();
      i--;
      continue;
    }
    clean(edges[on][i], on);
    trans.emplace_back(on, edges[on][i]);
  }
}
std::pair<int, int> inter[ms];
int mx[ms];
bool got[ms];
int ans[ms];
int getAns(int x) {
  if (ans[x] == -1) {
    for (int i = 1; i <= n; i++) {
      inter[i] = std::pair<int, int>(0, 0);
      mx[i] = 0;
      got[i] = false;
    }
    for (auto e : trans) {
      int u = e.first, v = e.second;
      std::pair<int, int> nxt = inter[v];
      if (got[v]) {
        nxt.first++;
        nxt.second = 0;
      } else {
        nxt.second = mx[v] + 1;
      }
      if (mx[u] + nxt.second + 1 >= x) {
        got[u] = true;
      }
      if (mx[u] < nxt.second) {
        mx[u] = nxt.second;
      }
      inter[u].first += nxt.first;
    }
    if (got[1]) {
      inter[1].first++;
    }
    ans[x] = inter[1].first;
  }
  return ans[x];
}
void solve(int l, int r) {
  if (getAns(l) == getAns(r)) {
    return;
  }
  int mid = (l + r) / 2;
  solve(l, mid);
  solve(mid + 1, r);
}
int main() {
  std::ios_base::sync_with_stdio(false);
  std::cin.tie(NULL);
  std::cin >> n;
  for (int i = 1; i <= n; i++) {
    ans[i] = -1;
  }
  ans[1] = n;
  for (int i = 1; i < n; i++) {
    int u, v;
    u = i, v = i + 1;
    std::cin >> u >> v;
    edges[u].push_back(v);
    edges[v].push_back(u);
  }
  clean(1, 0);
  solve(1, n);
  for (int i = n - 1; i > 0; i--) {
    ans[i] = std::max(ans[i], ans[i + 1]);
  }
  for (int i = 1; i <= n; i++) {
    std::cout << ans[i] << std::endl;
  }
}
