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(2)
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#pragma GCC optimize( \
    "inline,-fgcse,-fgcse-lm,-fipa-sra,-ftree-pre,-ftree-vrp,-fpeephole2,-ffast-math,-fsched-spec,unroll-loops,-falign-jumps,-falign-loops,-falign-labels,-fdevirtualize,-fcaller-saves,-fcrossjumping,-fthread-jumps,-funroll-loops,-freorder-blocks,-fschedule-insns,inline-functions,-ftree-tail-merge,-fschedule-insns2,-fstrict-aliasing,-fstrict-overflow,-falign-functions,-fcse-follow-jumps,-fsched-interblock,-fpartial-inlining,no-stack-protector,-freorder-functions,-findirect-inlining,-fhoist-adjacent-loads,-frerun-cse-after-loop,inline-small-functions,-finline-small-functions,-ftree-switch-conversion,-foptimize-sibling-calls,-fexpensive-optimizations,inline-functions-called-once,-fdelete-null-pointer-checks")
using namespace std;
using db = double;
using ll = long long;
using uint = unsigned int;
using pii = pair<int, int>;
template <class T>
void cmax(T& x, const T& y) {
  if (x < y) x = y;
}
template <class T>
void cmin(T& x, const T& y) {
  if (x > y) x = y;
}
template <class T>
void sort(vector<T>& v) {
  sort(v.begin(), v.end());
}
template <class T>
void reverse(vector<T>& v) {
  reverse(v.begin(), v.end());
}
template <class T>
void unique(vector<T>& v) {
  sort(v.begin(), v.end()), v.erase(unique(v.begin(), v.end()), v.end());
}
const int SZ = 1 << 23 | 233;
struct FILEIN {
  char qwq[SZ], *S = qwq, *T = qwq, ch;
  char GETC() {
    return (S == T) && (T = (S = qwq) + fread(qwq, 1, SZ, stdin), S == T)
               ? EOF
               : *S++;
  }
  FILEIN& operator>>(char& c) {
    while (isspace(c = GETC()))
      ;
    return *this;
  }
  FILEIN& operator>>(string& s) {
    while (isspace(ch = GETC()))
      ;
    s = ch;
    while (!isspace(ch = GETC())) s += ch;
    return *this;
  }
  template <class T>
  void read(T& x) {
    bool sign = 0;
    while ((ch = GETC()) < 48) sign ^= (ch == 45);
    x = (ch ^ 48);
    while ((ch = GETC()) > 47) x = (x << 1) + (x << 3) + (ch ^ 48);
    x = sign ? -x : x;
  }
  FILEIN& operator>>(int& x) { return read(x), *this; }
  FILEIN& operator>>(ll& x) { return read(x), *this; }
} in;
struct FILEOUT {
  const static int LIMIT = 1 << 22;
  char quq[SZ], ST[233];
  int sz, O;
  ~FILEOUT() { flush(); }
  void flush() {
    fwrite(quq, 1, O, stdout);
    fflush(stdout);
    O = 0;
  }
  FILEOUT& operator<<(char c) { return quq[O++] = c, *this; }
  FILEOUT& operator<<(string str) {
    if (O > LIMIT) flush();
    for (char c : str) quq[O++] = c;
    return *this;
  }
  template <class T>
  void write(T x) {
    if (O > LIMIT) flush();
    if (x < 0) {
      quq[O++] = 45;
      x = -x;
    }
    do {
      ST[++sz] = x % 10 ^ 48;
      x /= 10;
    } while (x);
    while (sz) quq[O++] = ST[sz--];
  }
  FILEOUT& operator<<(int x) { return write(x), *this; }
  FILEOUT& operator<<(ll x) { return write(x), *this; }
} out;
int n;
const int maxn = 1e5 + 51;
vector<int> g[maxn];
int rev[maxn], fa[maxn], idx = 0;
void dfs(int u, int f) {
  for (int v : g[u])
    if (v != f) dfs(v, u);
  fa[u] = f, rev[++idx] = u;
}
int f[maxn];
int ans[maxn];
int solve(int x) {
  if (ans[x]) return ans[x];
  int cnt = 0;
  for (register int i = (1); i <= (n); ++i) f[i] = 1;
  for (register int i = (1); i <= (n); ++i) {
    int qwq = rev[i];
    if (fa[qwq] && (~f[fa[qwq]]) && (~f[qwq])) {
      if (f[qwq] + f[fa[qwq]] >= x)
        ++cnt, f[fa[qwq]] = -1;
      else
        cmax(f[fa[qwq]], f[qwq] + 1);
    }
  }
  return ans[x] = cnt;
}
signed main() {
  in >> n;
  for (register int i = (2); i <= (n); ++i) {
    int u, v;
    in >> u >> v;
    g[u].emplace_back(v), g[v].emplace_back(u);
  }
  dfs(1, 0);
  int q = min(n, 200);
  ans[1] = n;
  for (register int i = (2); i <= (q); ++i) ans[i] = solve(i);
  int Ans;
  for (int i = q + 1; i <= n; i = Ans + 1) {
    int l = i, r = n;
    int qwq = solve(l);
    while (l <= r) {
      int mid = l + r >> 1;
      if (solve(mid) ^ qwq)
        r = mid - 1;
      else
        l = (Ans = mid) + 1;
    }
    for (int p = i; p <= Ans; p++) ans[p] = qwq;
  }
  for (register int i = (1); i <= (n); ++i) out << ans[i] << '\n';
  return 0;
}
