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 inf = 2e18;
const int N = 3e6 + 10;
const int maxn = 200020;
const long long mod = 1e9 + 7;
struct node {
  int next, to;
} e[maxn * 2];
int head[maxn], cnt;
int n, fa[maxn], q[maxn], hh, tt, f[maxn];
inline void adde(int x, int y) {
  e[++cnt].to = y;
  e[cnt].next = head[x];
  head[x] = cnt;
}
void dfs(int x) {
  q[tt++] = x;
  for (register int i = head[x]; i; i = e[i].next) {
    if (e[i].to == fa[x]) continue;
    fa[e[i].to] = x, dfs(e[i].to);
  }
}
inline int getans(int len) {
  cnt = 0;
  for (register int i = tt - 1; i >= 0; i--) {
    int x = q[i];
    int mx = 0, mx2 = 0;
    for (register int i = head[x]; i; i = e[i].next) {
      if (e[i].to == fa[x]) continue;
      if (f[e[i].to] > mx)
        mx2 = mx, mx = f[e[i].to];
      else if (f[e[i].to] > mx2)
        mx2 = f[e[i].to];
    }
    if (mx + mx2 + 1 >= len) {
      cnt++;
      f[x] = 0;
    } else
      f[x] = mx + 1;
  }
  return cnt;
}
inline int getnxt(int len, int cur) {
  int l = len, r = n, res = len;
  while (l <= r) {
    int mid = (l + r) >> 1;
    if (getans(mid) == cur)
      res = mid, l = mid + 1;
    else
      r = mid - 1;
  }
  return res;
}
int main() {
  scanf("%d", &n);
  for (register int i = 1; i <= n - 1; i++) {
    int x, y;
    scanf("%d %d", &x, &y);
    adde(x, y), adde(y, x);
  }
  dfs(1);
  printf("%d\n", n);
  for (register int i = 2; i <= min(n, 1000); i++) printf("%d\n", getans(i));
  int len = 1001;
  while (len <= n) {
    int cur = getans(len), nxt = getnxt(len, cur);
    for (register int i = len; i <= nxt; i++) printf("%d\n", cur);
    len = nxt + 1;
  }
}
