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>
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("no-stack-protector")
using namespace std;
int N, B = 400;
vector<int> graph[100005], graph2[100005];
int par[100005];
pair<int, int> dp[100005];
int ans[100005];
int ord[100005], idx;
inline void dfs(int n) {
  for (int e : graph[n]) {
    if (e != par[n]) {
      graph2[n].push_back(e);
      par[e] = n;
      dfs(e);
    }
  }
  ord[++idx] = n;
}
inline void solve(int k) {
  if (ans[k] != -1) {
    dp[1].first = ans[k];
    return;
  }
  for (int i = 1; i <= N; i++) {
    const int n = ord[i];
    int mx1 = 0, mx2 = 0, tot = 0;
    for (int e : graph2[n]) {
      tot += dp[e].first;
      if (dp[e].second >= mx1) {
        mx2 = mx1;
        mx1 = dp[e].second;
      } else if (dp[e].second > mx2) {
        mx2 = dp[e].second;
      }
    }
    mx1++;
    if (mx1 + mx2 >= k) {
      tot++;
      mx1 = 0;
    }
    dp[n].first = tot;
    dp[n].second = mx1;
  }
}
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  cin >> N;
  for (int i = 1; i < N; i++) {
    int a, b;
    cin >> a >> b;
    graph[a].push_back(b);
    graph[b].push_back(a);
  }
  B = 700;
  fill(ans + 1, ans + 1 + N, -1);
  dfs(1);
  for (int i = 1; i <= B; i++) {
    solve(i);
    ans[i] = dp[1].first;
  }
  for (int i = B + 1; i <= N;) {
    solve(i);
    int k = dp[1].first;
    int l = i, r = N, j = i;
    while (l <= r) {
      int mid = l + r >> 1;
      solve(mid);
      if (dp[1].first == k) {
        l = mid + 1;
        j = mid;
      } else {
        r = mid - 1;
      }
    }
    do {
      ans[i] = k;
    } while (++i <= j);
  }
  for (int i = 1; i <= N; i++) {
    cout << ans[i] << "\n";
  }
}
