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 + 123, inf = 1e9, mod = 1e9 + 7;
vector<int> g[maxn];
int n, ans[maxn], cur, dp[maxn];
bool was[maxn];
inline void precalc(int v, int p) {
  for (int i = 0; i < g[v].size(); i++) {
    if (p == g[v][i]) swap(g[v][i], g[v][g[v].size() - 1]);
    if (g[v][i] != p) precalc(g[v][i], v);
  }
  if (g[v].back() == p) g[v].pop_back();
}
inline void dfs(int v, int k) {
  int mx1, mx2;
  mx1 = mx2 = 0;
  for (auto to : g[v]) {
    dfs(to, k);
    if (dp[to] >= mx1)
      mx2 = mx1, mx1 = dp[to];
    else if (dp[to] >= mx2)
      mx2 = dp[to];
  }
  if (mx1 + mx2 + 1 >= k)
    cur++, dp[v] = 0;
  else
    dp[v] = mx1 + 1;
}
inline void calc(int k) {
  cur = 0;
  if (was[k]) {
    cur = ans[k];
    return;
  }
  was[k] = 1;
  dfs(1, k);
  ans[k] = cur;
}
int main() {
  scanf("%d", &n);
  for (int i = 1; i < n; i++) {
    int v, u;
    scanf("%d%d", &v, &u);
    g[v].push_back(u);
    g[u].push_back(v);
  }
  precalc(1, 1);
  int last, pos;
  for (int i = 1; i * i <= n; i++) {
    calc(i);
    last = ans[i], pos = i;
  }
  pos++;
  calc(pos);
  for (int i = last; i > 0; i--) {
    if (cur < i) continue;
    int l = pos, r = (n + i - 1) / i + 1;
    while (l <= r) {
      int m = (l + r) / 2;
      calc(m);
      if (cur >= i)
        l = m + 1;
      else
        r = m - 1;
    }
    for (int j = pos; j < l; j++) ans[j] = i;
    pos = l;
    calc(pos);
  }
  for (int i = 1; i <= n; i++) printf("%d\n", ans[i]);
  return 0;
}
