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 optimization_level 3
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
using namespace std;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
int getChar() {
  static char buf[1 << 16];
  static int pos = 0, size = 0;
  if (pos == size) {
    pos = 0;
    size = (int)fread(buf, sizeof(buf[0]), sizeof(buf) / sizeof(buf[0]), stdin);
  }
  return buf[pos++];
}
inline int ni() {
  char c = getChar();
  for (; c == '\n' || c == ' ';) c = getChar();
  int o = 0;
  for (; c != ' ' && c != '\n'; c = getChar()) o = o * 10 + c - '0';
  return o;
}
inline void putChar(int c) {
  static char buf[1 << 16];
  static int pos = 0;
  if (c == EOF || pos == 1 << 16) {
    fwrite(buf, sizeof(buf[0]), pos, stdout);
    pos = 0;
  }
  if (c == EOF) return;
  buf[pos++] = c;
}
void printInt(int val) {
  char buf[7];
  int pos = 0;
  if (val == 0) buf[pos++] = 48;
  for (; val; val /= 10) buf[pos++] = 48 + val % 10;
  for (pos--; pos >= 0;) putChar(buf[pos--]);
  putChar('\n');
}
const int G = 100002;
int a, OPA = -1;
vector<int> l[G];
int skok[G], o[G], zam[G], mxd[G], mxp[G], sz[G], good[G];
pair<int, int> dp[G], GR[G];
int CALC(int v, int p, int D) {
  mxd[v] = 1;
  sz[v] = 1;
  int c1 = 0, c2 = 0;
  for (int h : l[v]) {
    if (h == p) continue;
    int x = CALC(h, v, D + 1);
    mxd[v] = max(mxd[v], x + 1);
    sz[v] += sz[h];
    if (x >= c1)
      c2 = c1, c1 = x;
    else if (x > c2)
      c2 = x;
  }
  mxp[v] = c1 + c2 + 1;
  return mxd[v];
}
int find_centroid(int v, int p) {
  int MX = 0, num = -1;
  for (int h : l[v]) {
    if (h != p && sz[h] > MX) MX = sz[h], num = h;
  }
  return MX > a / 2 ? find_centroid(num, v) : v;
}
void RIP_PAPA(int v, int p) {
  for (int q = 0; q < l[v].size(); q++) {
    if (l[v][q] == p) {
      l[v].erase(l[v].begin() + q);
      break;
    }
  }
  for (int h : l[v]) RIP_PAPA(h, v);
}
int eba = 0;
void rnm(int v) {
  zam[v] = eba++;
  deque<int> dq = {v};
  for (; dq.size();) {
    int x = dq[0];
    dq.pop_front();
    for (int h : l[x]) {
      if (zam[h] != -1) continue;
      dq.push_back(h);
      zam[h] = eba++;
    }
  }
}
int iba = 0;
void rnm2(int v) {
  zam[v] = iba++;
  deque<int> dq = {v};
  for (; dq.size();) {
    int x = dq[0];
    dq.pop_front();
    for (int h : l[x]) {
      if (!good[h]) dq.push_back(h);
      zam[h] = iba++;
    }
  }
}
int ST;
int GA(int LEN) {
  if (o[LEN] != -1) return o[LEN];
  int d1, d2, w, rg;
  for (; ST >= 0 && mxp[ST] < OPA;) ST--;
  for (int q = ST; q >= 0; q--) {
    if (mxp[q] < OPA) continue;
    if (good[q])
      dp[q] = {sz[q] / LEN, sz[q] % LEN};
    else {
      dp[q].first = 0;
      d1 = d2 = 0, w = GR[q].first, rg = GR[q].second;
      for (; w <= rg; w++) {
        dp[q].first += dp[w].first;
        if (dp[w].second >= d1)
          d2 = d1, d1 = dp[w].second;
        else
          d2 = max(d2, dp[w].second);
      }
      if (d1 + d2 + 1 < LEN)
        dp[q].second = d1 + 1;
      else
        dp[q].first++, dp[q].second = 0;
    }
  }
  return o[LEN] = dp[0].first;
}
int main() {
  cin.tie(0);
  cout.tie(0);
  cin.sync_with_stdio(0);
  cout.sync_with_stdio(0);
  ;
  memset(o, -1, sizeof(o));
  memset(zam, -1, sizeof(zam));
  a = ni();
  o[1] = a;
  ST = a - 1;
  for (int q = 1; q <= a; q++) skok[a / q]++;
  for (int &i : skok) i /= 2;
  vector<pair<int, int> > reb(a - 1);
  for (int q = 0; q < a - 1; q++) {
    int x = ni() - 1, y = ni() - 1;
    reb[q] = {x, y};
    l[x].push_back(y);
    l[y].push_back(x);
  }
  CALC(0, -1, 1);
  int C = find_centroid(0, -1);
  rnm(C);
  for (int q = 0; q < a; q++) l[q].clear();
  for (pair<int, int> p : reb) {
    l[zam[p.first]].push_back(zam[p.second]);
    l[zam[p.second]].push_back(zam[p.first]);
  }
  RIP_PAPA(0, -1);
  reb.clear();
  for (int q = 0; q < a; q++)
    for (int h : l[q]) reb.push_back({q, h});
  CALC(0, -1, 1);
  for (int q = 0; q < a; q++) good[q] = sz[q] == mxd[q];
  memset(zam, -1, sizeof(zam));
  zam[0] = 0;
  if (!good[0])
    rnm2(0);
  else
    iba = 1;
  ST = iba - 1;
  for (int q = 0; q < a; q++) {
    if (zam[q] == -1) continue;
    sz[zam[q]] = sz[q];
    mxd[zam[q]] = mxd[q];
    mxp[zam[q]] = mxp[q];
  }
  for (int q = 0; q < a; q++) l[q].clear();
  for (pair<int, int> p : reb) {
    if (min(zam[p.first], zam[p.second]) > -1) {
      l[zam[p.first]].push_back(zam[p.second]);
    }
  }
  for (int q = 0; q < a; q++) {
    if (l[q].size())
      GR[q] = {l[q][0], l[q].back()};
    else
      GR[q] = {a, q};
  }
  for (int q = 0; q < a; q++) good[q] = sz[q] == mxd[q];
  int diam = 0;
  for (int &i : mxp) diam = max(i, diam);
  o[diam] = 1;
  for (int q = diam + 1; q <= a; q++) o[q] = 0;
  int H = min(a - 1, (int)(sqrt(a * log2(a) * 0.7))), I = 2;
  for (; I <= H; I++) {
    o[I] = GA(I);
    OPA = I / 2;
  }
  int tyt;
  for (; I <= a;) {
    OPA = I / 2;
    tyt = GA(I);
    int lf = I, rg = min(a + 1, lf + skok[tyt] + 1);
    if (tyt == 0) break;
    if (tyt == 1) lf = diam, rg = diam + 1;
    for (; lf + 1 < rg;) {
      int md = (lf + rg) / 2;
      if (GA(md) == tyt)
        lf = md;
      else
        rg = md;
    }
    for (; I < rg; I++) o[I] = tyt;
  }
  for (int q = 1; q <= a; q++) {
    printInt(max(0, o[q]));
  }
  putChar(EOF);
}
