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;
template <class T>
void splitstr(const string &s, vector<T> &out) {
  istringstream in(s);
  out.clear();
  copy(istream_iterator<T>(in), istream_iterator<T>(), back_inserter(out));
}
template <class T>
T gcd(T a, T b) {
  return b ? gcd(b, a % b) : a;
}
static void redirect(int argc, const char **argv) {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  if (argc > 1) {
    static filebuf f;
    f.open(argv[1], ios::in);
    cin.rdbuf(&f);
    if (!cin) {
      cerr << "Failed to open '" << argv[1] << "'" << endl;
      exit(1);
    }
  }
  if (argc > 2) {
    static filebuf f;
    f.open(argv[2], ios::out | ios::trunc);
    cout.rdbuf(&f);
    if (!cout) {
      cerr << "Failed to open '" << argv[2] << "'" << endl;
    }
  }
}
struct compare {
  bool operator()(const pair<int, int> &a, const pair<int, int> &b) const {
    return pair<int, int>(a.first, -a.second) <
           pair<int, int>(b.first, -b.second);
  }
};
struct node {
  int paths, extra;
  vector<int> edges;
};
static vector<node> nodes;
static vector<int> order;
static void make_order(int cur, int parent) {
  node &n = nodes[cur];
  order.push_back(cur);
  if (parent != -1) n.edges.erase(find(begin(n.edges), end(n.edges), parent));
  for (int c : n.edges) make_order(c, cur);
}
static int solve(int k) {
  for (int cur : order) {
    node &n = nodes[cur];
    int d1 = 0, d2 = 0;
    n.paths = 0;
    for (int ch : n.edges) {
      const node &c = nodes[ch];
      n.paths += c.paths;
      if (c.extra > d1) {
        d2 = d1;
        d1 = c.extra;
      } else if (c.extra > d2)
        d2 = c.extra;
    }
    if (d1 + d2 + 1 >= k) {
      n.paths++;
      n.extra = 0;
    } else
      n.extra = d1 + 1;
  }
  return nodes[0].paths;
}
int main(int argc, const char **argv) {
  redirect(argc, argv);
  int N;
  cin >> N;
  nodes.resize(N);
  for (int i = 0; i < N - 1; i++) {
    int u, v;
    cin >> u >> v;
    u--;
    v--;
    nodes[u].edges.push_back(v);
    nodes[v].edges.push_back(u);
  }
  make_order(0, -1);
  reverse(begin(order), end(order));
  int S = min(N, 1000);
  vector<int> ans(N + 1);
  for (int i = 1; i <= S; i++) ans[i] = solve(i);
  int prev = S;
  for (int i = ans[S]; i >= 1; i--) {
    int lo = prev;
    int hi = N + 1;
    while (hi - lo > 1) {
      int mid = (lo + hi) / 2;
      if (solve(mid) >= i)
        lo = mid;
      else
        hi = mid;
    }
    for (int j = prev + 1; j < hi; j++) ans[j] = i;
    prev = lo;
  }
  for (int i = 1; i <= N; i++) cout << ans[i] << '\n';
  return 0;
}
