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;
void re(int& x);
template <class T, class... Ts>
void re(T& t, Ts&... ts);
void pr(int x);
void pr(const char* x);
void ps();
template <class T, class... Ts>
void ps(const T& t, const Ts&... ts);
int n;
int u, v;
vector<int> g[110000];
int r[110000];
pair<int, int> checki(int v, int p, int k) {
  pair<int, int> ret = {0, 1};
  for (int x : g[v])
    if (x != p) {
      pair<int, int> t = checki(x, v, k);
      ret.first += t.first;
      if (ret.second != 0) {
        if (ret.second + t.second - 1 >= k) {
          ret.second = 0;
          ret.first++;
        } else
          ret.second = max(ret.second, t.second);
      }
    }
  ret.second++;
  return ret;
}
int check(int k) {
  int& ret = r[k];
  if (ret == -1) ret = checki(0, -1, k).first;
  return ret;
}
void solve() {
  memset(r, -1, sizeof(r));
  re(n);
  for (int i = 0; i < (n - 1); ++i) {
    re(u, v);
    u--;
    v--;
    g[u].push_back(v);
    g[v].push_back(u);
  }
  ps(n);
  int k = 2;
  for (; k * k <= n; k++) {
    ps(check(k));
  }
  for (int val = n / k; val > 0; val--) {
    int st = k, ed = n / val + 1;
    while (st < ed) {
      int md = (st + ed) / 2;
      if (check(md) < val)
        ed = md;
      else
        st = md + 1;
    }
    for (; k < st; k++) ps(val);
  }
  for (; k <= n; k++) ps(0);
}
int main() { solve(); }
void re(int& x) { scanf("%d", &x); }
template <class T, class... Ts>
void re(T& t, Ts&... ts) {
  re(t);
  re(ts...);
}
void pr(int x) { printf("%d", x); }
void pr(const char* x) { printf("%s", x); }
void ps() { pr("\n"); }
template <class T, class... Ts>
void ps(const T& t, const Ts&... ts) {
  pr(t);
  if (sizeof...(ts)) pr(" ");
  ps(ts...);
}
