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 = 1e5 + 14;
struct Dp {
  int p, l;
};
mt19937 rnd(time(0));
vector<int> g[maxn];
int n, ans[maxn];
Dp dfs(int k, int v = 0, int p = -1) {
  Dp ret = {};
  int best = 0, sbest = 0;
  for (auto &u : g[v])
    if (u != p) {
      Dp c = dfs(k, u, v);
      ret.p += c.p;
      ret.l = max(ret.l, c.l);
      if (c.l > best)
        sbest = best, best = c.l;
      else
        sbest = max(sbest, c.l);
    }
  if (best + sbest + 1 >= k)
    ret.p++, ret.l = 0;
  else
    ret.l++;
  return ret;
}
void solve(int l = 1, int r = n + 1, int s = 0, int e = n) {
  if (r <= l) return;
  if (s == e) {
    fill(ans + l, ans + r, s);
    return;
  }
  int mid = rnd() % (r - l) + l;
  ans[mid] = dfs(mid).p;
  solve(l, mid, ans[mid], e);
  solve(mid + 1, r, s, ans[mid]);
}
int main() {
  ios::sync_with_stdio(0), cin.tie(0);
  memset(ans, -1, sizeof ans);
  cin >> n;
  for (int i = 1; i < n; i++) {
    int v, u;
    cin >> v >> u;
    v--, u--;
    g[v].push_back(u);
    g[u].push_back(v);
  }
  solve();
  for (int i = 1; i <= n; i++) cout << ans[i] << '\n';
}
