Problem: Let G be a simple graph. Let W be a non-empty subset of vertices. Then W is almost-k-uniform if for each pair of distinct vertices u,v ∈ W the distance between u and v is either k or k+1.

You are given a tree on n vertices. For each i between 1 and n, find the maximum size of an almost-i-uniform set.

Input

The first line contains a single integer n (2 ≤ n ≤ 5 ⋅ 10^5) – the number of vertices of the tree.

Then n-1 lines follows, the i-th of which consisting of two space separated integers u_i, v_i (1 ≤ u_i, v_i ≤ n) meaning that there is an edge between vertices u_i and v_i. 

It is guaranteed that the given graph is tree. 

Output

Output a single line containing n space separated integers a_i, where a_i is the maximum size of an almost-i-uniform set.

Examples

Input


5
1 2
1 3
1 4
4 5


Output


4 3 2 1 1


Input


6
1 2
1 3
1 4
4 5
4 6


Output


4 4 2 1 1 1

Note

Consider the first example. 

  * The only maximum almost-1-uniform set is \{1, 2, 3, 4\}. 
  * One of the maximum almost-2-uniform sets is or \{2, 3, 5\}, another one is \{2, 3, 4\}. 
  * A maximum almost-3-uniform set is any pair of vertices on distance 3. 
  * Any single vertex is an almost-k-uniform set for k ≥ 1. 



In the second sample there is an almost-2-uniform set of size 4, and that is \{2, 3, 5, 6\}.

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
mt19937 gene(233);
inline char GET_CHAR() {
  const int maxn = 131072;
  static char buf[maxn], *p1 = buf, *p2 = buf;
  return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, maxn, stdin), p1 == p2)
             ? EOF
             : *p1++;
}
inline int getInt() {
  int res(0);
  char c = getchar();
  while (c < '0') c = getchar();
  while (c >= '0') {
    res = res * 10 + (c - '0');
    c = getchar();
  }
  return res;
}
inline int fastpo(int x, int n, int mod) {
  int res(1);
  while (n) {
    if (n & 1) {
      res = res * (long long)x % mod;
    }
    x = x * (long long)x % mod;
    n /= 2;
  }
  return res;
}
inline string itoa(int x, int width = 0) {
  string res;
  if (x == 0) res.push_back('0');
  while (x) {
    res.push_back('0' + x % 10);
    x /= 10;
  }
  while ((int)res.size() < width) res.push_back('0');
  reverse(res.begin(), res.end());
  return res;
}
const int N = 500033;
const int LOG = 20;
const int mod = 1e9 + 7;
const int inf = 1e9 + 7;
int n, m;
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
vector<int> e[N];
vector<int> vv[N], nxt[N];
int vst[N], fa[N], ans[N], a1[N], fl[999][999], siz[N], dep[N], d2[N], up[N];
int debug = 0;
int main() {
  if (debug) {
    n = 500000;
  } else {
    scanf("%d", &n);
  }
  unsigned seed = std::chrono::system_clock::now().time_since_epoch().count();
  std::mt19937 generator(seed);
  for (int i(1); i < n; i++) {
    int x, y;
    if (debug) {
      x = 1;
      y = i + 1;
    } else {
      scanf("%d%d", &x, &y);
    }
    e[x].push_back(y);
    e[y].push_back(x);
  }
  vector<int> q;
  q.push_back(1);
  vst[1] = 1;
  for (int op = 0; op < n; op++) {
    int v = q[op];
    for (int y : e[v]) {
      if (!vst[y]) {
        fa[y] = v;
        vst[y] = 1;
        q.push_back(y);
      }
    }
  }
  for (int i(n - 1); i >= 0; i--) {
    int v = q[i];
    int nw = dep[v] + 1;
    siz[v]++;
    siz[fa[v]] += siz[v];
    if (nw > dep[fa[v]]) {
      d2[fa[v]] = dep[fa[v]];
      dep[fa[v]] = nw;
    } else if (nw > d2[fa[v]])
      d2[fa[v]] = nw;
  }
  ans[n] = 1;
  for (int v : q) {
    up[v] = v == 1 ? 0 : up[fa[v]] + 1;
    if (v != 1)
      up[v] =
          max(up[v], dep[v] + 1 == dep[fa[v]] ? d2[fa[v]] + 1 : dep[fa[v]] + 1);
    vector<int> vec;
    vec.push_back(up[v]);
    for (int y : e[v]) {
      if (fa[y] == v) vec.push_back(dep[y] + 1);
    }
    if (up[v] != 0) {
      vec.push_back(0);
    }
    sort(vec.begin(), vec.end());
    for (int i(0); i < (int)vec.size(); i++) {
      ans[vec[i] * 2] = max(ans[vec[i] * 2], (int)vec.size() - i);
      if (i && vec[i - 1] < vec[i]) {
        ans[vec[i - 1] * 2 + 1] =
            max(ans[vec[i - 1] * 2 + 1], (int)vec.size() - i + 1);
      }
    }
    vv[v] = vec;
  }
  for (int i(n - 1); i >= 1; i--) ans[i] = max(ans[i], ans[i + 1]);
  for (int i(1); i <= n; i++) {
    nxt[i] = vv[i];
    for (int j(0), k; j < (int)vv[i].size(); j = k) {
      for (k = j; k < (int)vv[i].size() && vv[i][j] == vv[i][k]; k++)
        ;
      for (int l = j; l < k; l++) nxt[i][l] = k;
    }
  }
  for (int v : q) {
    if (!fa[v]) continue;
    for (int i(0), p(0); i < (int)vv[v].size(); i = nxt[v][i]) {
      int cnt = vv[v].size() - i;
      int lb = vv[v][i];
      if (lb > siz[v] || lb > n - siz[v]) break;
      if (lb == 0) continue;
      if (up[v] - 1 >= lb) cnt--;
      if (cnt <= 0) continue;
      while (p < (int)vv[fa[v]].size() && vv[fa[v]][p] < lb) p++;
      cnt += (int)vv[fa[v]].size() - p;
      cnt--;
      ans[lb * 2] = max(ans[lb * 2], cnt);
    }
    for (int i(0), p(0); i < (int)vv[fa[v]].size(); i = nxt[fa[v]][i]) {
      int cnt = vv[fa[v]].size() - i;
      int lb = vv[fa[v]][i];
      if (lb > siz[v] || lb > n - siz[v]) break;
      if (lb == 0) continue;
      if (dep[v] >= lb) cnt--;
      while (p < (int)vv[v].size() && vv[v][p] < lb) p++;
      cnt += (int)vv[v].size() - p;
      cnt--;
      ans[lb * 2] = max(ans[lb * 2], cnt);
    }
  }
  for (int i = (n - 1) / 2 * 2; i >= 0; i -= 2)
    ans[i] = max(ans[i], ans[i + 2]);
  for (int i = 1; i <= n; i++) printf("%d%c", ans[i], i == n ? '\n' : ' ');
}