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 long long MOD = 998244353;
const int MAXN = 1e5 + 50;
long long powmod(long long a, long long b) {
  long long res = 1;
  a %= MOD;
  assert(b >= 0);
  for (; b; b >>= 1) {
    if (b & 1) res = res * a % MOD;
    a = a * a % MOD;
  }
  return res;
}
long long gcd(long long a, long long b) { return b ? gcd(b, a % b) : a; }
int n;
struct Edge {
  int v, nxt;
  Edge() {}
  Edge(int v0, int n0) {
    v = v0;
    nxt = n0;
  }
} e[MAXN * 2];
int head[MAXN], nume;
inline void addEdge(int u, int v) {
  e[++nume] = Edge(v, head[u]);
  head[u] = nume;
  e[++nume] = Edge(u, head[v]);
  head[v] = nume;
}
struct DP {
  int c, r;
} dp[MAXN];
int ans[MAXN], K;
vector<int> vec[MAXN];
int idx[MAXN], tot;
void dfs(int x, int from) {
  idx[++tot] = x;
  for (int i = head[x]; i; i = e[i].nxt)
    if (e[i].v != from) vec[x].emplace_back(e[i].v), dfs(e[i].v, x);
}
inline int getAns(int K) {
  if (ans[K] != -1) return ans[K];
  for (int p = tot; p >= 1; p--) {
    int x = idx[p];
    dp[x].c = dp[x].r = 0;
    register int mx = 0, cmx = 0;
    for (int v : vec[x]) {
      dp[x].c += dp[v].c;
      if (dp[v].r > mx)
        cmx = mx, mx = dp[v].r;
      else {
        if (dp[v].r > cmx) cmx = dp[v].r;
      }
    }
    if (cmx + mx + 1 >= K)
      dp[x].c++;
    else
      dp[x].r = mx + 1;
  }
  return ans[K] = dp[1].c;
}
inline void solve(int T) {
  scanf("%d", &n);
  nume = 0;
  memset(head, 0, sizeof(head));
  for (int i = 1, x, y; i < n; i++) scanf("%d%d", &x, &y), addEdge(x, y);
  tot = 0;
  dfs(1, 0);
  memset(ans, -1, sizeof(ans));
  ans[1] = n;
  int p;
  for (p = 1; p * p <= n; p++) getAns(p);
  for (int i = p, j = p; i <= n; i = j + 1) {
    j = i;
    ans[i] = getAns(i);
    int left = i + 1, right = n;
    while (left <= right) {
      int mid = (left + right) / 2;
      if (getAns(mid) == ans[i]) {
        j = max(mid, j);
        left = mid + 1;
      } else
        right = mid - 1;
    }
    for (int k = i; k <= j; k++) ans[k] = ans[i];
  }
  for (int i = 1; i <= n; i++) printf("%d\n", ans[i]);
}
int main() {
  solve(0);
  return 0;
}
