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")
using namespace std;
const int N = 1e5 + 1;
vector<int> adj[N];
int f[N], dis[N];
int ohyeah[N], now;
bool wow[N];
void dfs(int x, int p) {
  int cac1 = 0, cac = 0;
  dis[x] = 1;
  f[x] = 0;
  for (int i : adj[x]) {
    if (i != p) {
      dfs(i, x);
      f[x] += f[i];
      if (dis[i] >= cac) {
        cac1 = cac;
        cac = dis[i];
      } else {
        if (dis[i] > cac1) {
          cac1 = dis[i];
        }
      }
    }
  }
  if (cac + cac1 + 1 >= now) {
    f[x]++;
    dis[x] = 0;
  } else {
    dis[x] = cac + 1;
  }
}
int main() {
  int n, i, j, k, l, lef, rig, mid;
  scanf("%d", &n);
  for (i = 1; i < n; i++) {
    scanf("%d%d", &j, &k);
    adj[j].push_back(k);
    adj[k].push_back(j);
  }
  i = 2;
  wow[1] = true;
  ohyeah[1] = n;
  printf("%d\n", n);
  while (i <= n) {
    if (!wow[i]) {
      wow[i] = true;
      now = i;
      dfs(1, 1);
      ohyeah[i] = f[1];
    }
    lef = i, rig = n;
    for (j = i; j <= n; j++) {
      if (wow[j]) {
        if (ohyeah[j] != ohyeah[i]) {
          rig = j;
          break;
        } else {
          lef = j;
        }
      }
    }
    while (rig > lef) {
      mid = ((lef + rig + 1) >> 1);
      if (!wow[mid]) {
        now = mid;
        dfs(1, 1);
        wow[mid] = true;
        ohyeah[mid] = f[1];
      }
      if (ohyeah[mid] == ohyeah[i]) {
        lef = mid;
      } else {
        rig = mid - 1;
      }
    }
    for (j = i; j <= lef; j++) {
      printf("%d\n", ohyeah[i]);
    }
    i = lef + 1;
  }
}
