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>
#pragma GCC optimize("Ofast", "unroll-loops")
using namespace std;
using ll = long long;
using ld = double;
using pii = pair<int, int>;
using uint = unsigned int;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
default_random_engine generator;
void solve();
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  cout << setprecision(12) << fixed;
  cerr << setprecision(12) << fixed;
  int tests = 1;
  while (tests--) {
    solve();
  }
}
const int MAXN = 500500;
vector<int> g[MAXN];
int ldown[MAXN];
int lup[MAXN];
int res0[MAXN];
int res1[MAXN];
int res2[MAXN];
int res[MAXN];
int dfs0(int v, int p = -1) {
  for (int i = 0; i < (int)(g[v]).size(); ++i) {
    if (g[v][i] == p) {
      swap(g[v][i], g[v].back());
      g[v].pop_back();
      break;
    }
  }
  ldown[v] = 0;
  for (int u : g[v]) {
    ldown[v] = max(ldown[v], 1 + dfs0(u, v));
  }
  return ldown[v];
}
void dfs1(int v, int x = 0) {
  lup[v] = x;
  int d = (int)(g[v]).size();
  vector<int> pref(d + 1), suff(d + 1);
  for (int i = 0; i < d; ++i) {
    pref[i + 1] = max(pref[i], ldown[g[v][i]] + 1);
  }
  for (int i = d - 1; i >= 0; --i) {
    suff[i] = max(suff[i + 1], ldown[g[v][i]] + 1);
  }
  for (int i = 0; i < d; ++i) {
    dfs1(g[v][i], 1 + max({x, pref[i], suff[i + 1]}));
  }
}
void dfs2(int v) {
  for (int u : g[v]) {
    dfs2(u);
  }
  int d = (int)(g[v]).size();
  vector<int> len(d);
  for (int i = 0; i < d; ++i) {
    len[i] = ldown[g[v][i]] + 1;
  }
  if (lup[v] != 0) {
    len.push_back(lup[v]);
    ++d;
  }
  sort((len).begin(), (len).end());
  for (int i = 0; i < d; ++i) {
    res0[len[i]] = max(res0[len[i]], d - i);
    if (i == d - 1) {
      continue;
    }
    if (len[i + 1] >= len[i] + 1) {
      res1[len[i]] = max(res1[len[i]], d - i);
    }
    res1[len[i] - 1] = max(res1[len[i] - 1], d - i);
  }
  vector<pii> vct;
  set<pii> setik;
  vector<int> cnt(d);
  for (int i = 0; i < (int)(g[v]).size(); ++i) {
    int u = g[v][i];
    for (int w : g[u]) {
      vct.push_back({ldown[w] + 1, i});
    }
    if ((int)(g[u]).size() > 0) {
      setik.insert({(int)(g[u]).size(), i});
    }
    cnt[i] = (int)(g[u]).size();
  }
  if (lup[v] != 0) {
    vct.push_back({lup[v] - 1, d - 1});
    cnt[d - 1] = 1;
    setik.insert({1, d - 1});
  }
  sort((vct).begin(), (vct).end());
  for (int i = 0; i < (int)(vct).size();) {
    int j = i;
    while (j < (int)(vct).size() && vct[i].first == vct[j].first) {
      ++j;
    }
    int val = (int)(setik).size();
    for (int k = i; k < j; ++k) {
      int id = vct[k].second;
      setik.erase({cnt[id], id});
      --cnt[id];
      if (cnt[id] > 0) {
        setik.insert({cnt[id], id});
      }
    }
    if (setik.empty()) {
      break;
    }
    auto it = setik.end();
    --it;
    val += it->first - 1;
    res2[vct[i].first + 1] = max(res2[vct[i].first + 1], val);
    i = j;
  }
  for (int u : g[v]) {
    vector<int> c;
    for (int w : g[u]) {
      c.push_back(ldown[w]);
    }
    sort((c).begin(), (c).end());
    for (int i = 0; i < (int)(c).size(); ++i) {
      int val = len.end() - lower_bound((len).begin(), (len).end(), c[i] + 1);
      val += (int)(c).size() - i;
      --val;
      res2[c[i] + 1] = max(res2[c[i] + 1], val);
    }
  }
}
void solve() {
  int n;
  cin >> n;
  for (int i = 1; i < n; ++i) {
    int u, v;
    cin >> u >> v;
    --u;
    --v;
    g[u].push_back(v);
    g[v].push_back(u);
  }
  for (int i = 0; i < n; ++i) {
    res[1] = max(res[1], (int)(g[i]).size() + 1);
  }
  dfs0(0);
  dfs1(0);
  dfs2(0);
  for (int i = n - 1; i >= 0; --i) {
    res0[i] = max(res0[i], res0[i + 1]);
    res1[i] = max(res1[i], res1[i + 1]);
    res2[i] = max(res2[i], res2[i + 1]);
  }
  for (int k = 1; 2 * k <= n; ++k) {
    res[2 * k] = max(res0[k], res2[k]);
    res[2 * k + 1] = max(res0[k + 1], res1[k]);
  }
  for (int i = 1; i <= n; ++i) {
    res[i] = max(res[i], 1);
    cout << res[i] << " ";
  }
  cout << endl;
}