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;
using namespace std;
vector<int> ara[700000];
set<pair<int, int> > mylist[700000], query[700000];
int P[700000][22], L[700000], ans[700000], len[700000];
int parentanse[700000];
pair<int, int> roo;
int dia = 0;
vector<int> vc[700000];
int start[700000], pos, en[700000];
int dfs(int v, int par, int lev) {
  ara[lev].push_back(v);
  start[v] = ++pos;
  L[v] = lev;
  P[v][0] = par;
  dia = max(dia, lev);
  roo = max(roo, make_pair(lev, v));
  int ret = 0;
  for (int i = 0; i < vc[v].size(); i++) {
    int w = vc[v][i];
    if (w == par) continue;
    int x = dfs(w, v, lev + 1);
    ret = max(ret, x);
    mylist[v].insert(make_pair(x, w));
  }
  len[v] = ret;
  en[v] = pos;
  return ret + 1;
}
void dfs2(int v, int par, int ansi) {
  parentanse[v] = ansi;
  ansi = max(ansi, 0);
  for (int i = 0; i < vc[v].size(); i++) {
    int w = vc[v][i];
    if (w == par) continue;
    set<pair<int, int> >::iterator it;
    mylist[v].erase(make_pair(len[w] + 1, w));
    int c = ansi;
    if (mylist[v].size()) {
      it = mylist[v].end();
      it--;
      pair<int, int> ps = *it;
      c = max(c, ps.first);
    }
    dfs2(w, v, c + 1);
    mylist[v].insert(make_pair(len[w] + 1, w));
  }
}
void dfs3(int v, int par, int lev) {
  dia = max(dia, lev);
  for (int i = 0; i < vc[v].size(); i++) {
    int w = vc[v][i];
    if (w == par) continue;
    dfs3(w, v, lev + 1);
  }
}
int lca_query(int p, int q) {
  int tmp, log, i;
  if (L[p] < L[q]) tmp = p, p = q, q = tmp;
  log = 1;
  while (1) {
    int next = log + 1;
    if ((1 << next) > L[p]) break;
    log++;
  }
  for (i = log; i >= 0; i--)
    if (L[p] - (1 << i) >= L[q]) p = P[p][i];
  if (p == q) return p;
  for (i = log; i >= 0; i--)
    if (P[p][i] != -1 && P[p][i] != P[q][i]) p = P[p][i], q = P[q][i];
  return P[p][0];
}
void prc(set<int>& dum, set<pair<int, int> >& my, int lev, int v) {
  ans[lev * 2 - L[v] * 2] = max(ans[lev * 2 - L[v] * 2], (int)dum.size());
  int g = dum.size();
  if (my.size()) {
    set<pair<int, int> >::iterator it3;
    it3 = my.end();
    it3--;
    pair<int, int> rs = *it3;
    if (rs.first < lev - 1 - L[v]) g--;
  } else
    g--;
  ans[lev - 1 + lev - L[v] * 2] = max(ans[lev - 1 + lev - L[v] * 2], g + 1);
}
void process(int v) {
  set<pair<int, int> >::iterator it, it2;
  set<int>::iterator it3;
  for (it = query[v].begin(); it != query[v].end();) {
    it2 = it;
    pair<int, int> ps = *it;
    set<int> dum;
    for (; it2 != query[v].end(); it2++) {
      pair<int, int> rs = *it2;
      if (rs.first != ps.first) break;
      mylist[v].erase({len[rs.second] + 1, rs.second});
      dum.insert(rs.second);
    }
    mylist[v].insert(make_pair(0, v));
    if (parentanse[v] >= ps.first - L[v])
      dum.insert(P[v][0]);
    else
      mylist[v].insert(make_pair(parentanse[v], P[v][0]));
    prc(dum, mylist[v], ps.first, v);
    mylist[v].erase(make_pair(0, v));
    if (parentanse[v] >= ps.first - L[v])
      ;
    else
      mylist[v].erase(make_pair(parentanse[v], P[v][0]));
    it = it2;
    for (it3 = dum.begin(); it3 != dum.end(); it3++) {
      int gs = *it3;
      if (gs == P[v][0]) continue;
      mylist[v].insert(make_pair(len[gs] + 1, gs));
    }
  }
}
int findo(int c, int x) {
  assert(L[c] >= x);
  if (L[c] == x) return c;
  for (int i = 20; i >= 0; i--) {
    if (P[c][i] == -1) continue;
    if (L[P[c][i]] > x) {
      c = P[c][i];
    }
  }
  return P[c][0];
}
vector<pair<int, int> > chum[700000];
int query_bin(int v, int c) {
  int x = chum[v].size();
  int g =
      upper_bound(chum[v].begin(), chum[v].end(), make_pair(c - 1, INT_MAX)) -
      chum[v].begin();
  return x - g;
}
int lo_bo(int v, int c) {
  int g =
      upper_bound(chum[v].begin(), chum[v].end(), make_pair(c - 1, INT_MAX)) -
      chum[v].begin();
  if (g == chum[v].size() || chum[v][g].first != c) return 0;
  return 1;
}
int cnt[700000];
int jargon[700000];
int main() {
  memset(P, -1, sizeof P);
  int n, l, k;
  cin >> n;
  for (int i = 1; i < n; i++) {
    scanf("%d%d", &l, &k);
    vc[l].push_back(k);
    vc[k].push_back(l);
  }
  dfs(1, -1, 0);
  dfs2(1, -1, -1);
  dfs3(roo.second, -1, 0);
  for (int j = 1; (1 << j) <= n; j++) {
    for (int i = 1; i <= n; i++) {
      if (P[i][j - 1] == -1) continue;
      P[i][j] = P[P[i][j - 1]][j - 1];
    }
  }
  for (int i = 0; i <= n; i++) {
    for (int j = 1; j < ara[i].size(); j++) {
      int lc = lca_query(ara[i][j - 1], ara[i][j]);
      query[lc].insert({i, findo(ara[i][j - 1], L[lc] + 1)});
      query[lc].insert({i, findo(ara[i][j], L[lc] + 1)});
    }
  }
  for (int i = 1; i <= n; i++) {
    if (query[i].size() == 0) continue;
    process(i);
    query[i].clear();
  }
  for (int i = 1; i <= n; i++) {
    set<pair<int, int> >::iterator it;
    for (it = mylist[i].begin(); it != mylist[i].end(); it++) {
      chum[i].push_back(*it);
    }
  }
  for (int i = 1; i <= n; i++) {
    vector<pair<pair<int, int>, int> > tmp;
    for (int j = 0; j < ara[i].size(); j++) {
      int c = ara[i][j];
      tmp.push_back({{start[c], c}, 0});
    }
    for (int j = 0; j < ara[i + 1].size(); j++) {
      int c = ara[i + 1][j];
      tmp.push_back({{start[c], c}, 1});
    }
    sort(tmp.begin(), tmp.end());
    vector<int> toxic2[2];
    for (int j = 0; j < tmp.size(); j++) {
      int c = tmp[j].first.second;
      int x = tmp[j].second;
      int r = -1;
      for (int j = (int)toxic2[x ^ 1].size() - 1; j >= 0; j--) {
        int w = toxic2[x ^ 1][j];
        if (start[w] <= start[c] && en[w] >= start[c]) continue;
        r = w;
        break;
      }
      if (r != -1) {
        int lca = lca_query(r, c);
        int f = findo(c, L[lca] + 1);
        int g = findo(r, L[lca] + 1);
        if (lca == c || lca == r)
          ;
        else {
          int tar;
          tar = f;
          assert(L[f] - L[lca] == 1 && L[g] - L[lca] == 1);
          int koyta = query_bin(tar, i - L[tar] + 1);
          koyta += query_bin(lca, i - L[lca]);
          if (len[tar] >= i - L[tar] + 1) koyta--;
          if (parentanse[lca] >= i - L[lca]) koyta++;
          ans[i + i - L[lca] * 2] = max(ans[i + i - L[lca] * 2], koyta);
          tar = g;
          koyta = query_bin(tar, i - L[tar] + 1);
          koyta += query_bin(lca, i - L[lca]);
          if (len[tar] >= i - L[tar] + 1) koyta--;
          if (parentanse[lca] >= i - L[lca]) koyta++;
          ans[i + i - L[lca] * 2] = max(ans[i + i - L[lca] * 2], koyta);
          int ko = query_bin(lca, i + 1 - L[lca]);
          if (parentanse[lca] >= i + 1 - L[lca]) ko++;
          if (lo_bo(lca, i - L[lca]) || parentanse[lca] == i - L[lca])
            ;
          else
            ko--;
          ans[i + 1 + i - 2 * L[lca]] =
              max(ans[i + 1 + i - 2 * L[lca]], ko + 1);
        }
      }
      toxic2[x].push_back(c);
    }
  }
  for (int i = 1; i <= n; i++) {
    if (parentanse[i] > -1) mylist[i].insert(make_pair(parentanse[i], P[i][0]));
    int c = mylist[i].size();
    set<pair<int, int> >::iterator it;
    for (it = mylist[i].begin(); it != mylist[i].end(); it++) {
      pair<int, int> rs = *it;
      cnt[rs.first]++;
    }
    for (it = mylist[i].begin(); it != mylist[i].end(); it++) {
      pair<int, int> rs = *it;
      jargon[min(rs.first + rs.first - 1, n)] =
          max(jargon[min(rs.first + rs.first - 1, n)], c);
      int ff = cnt[rs.first + 1];
      jargon[min(rs.first + rs.first + 1, n)] =
          max(jargon[min(rs.first + rs.first + 1, n)], ff + 1);
      c--;
    }
    for (it = mylist[i].begin(); it != mylist[i].end(); it++) {
      pair<int, int> rs = *it;
      cnt[rs.first]--;
    }
  }
  for (int i = n; i >= 1; i--) {
    jargon[i] = max(jargon[i + 1], jargon[i]);
    if (i & 1) ans[i] = max(ans[i], jargon[i]);
    ans[i] = max(ans[i], ans[i + 2]);
  }
  for (int i = 1; i <= n; i++) {
    ans[1] = max(ans[1], (int)vc[i].size() + 1);
  }
  for (int i = 1; i <= n; i++) {
    ans[i] = max(ans[i], 1);
    if (i <= dia) ans[i] = max(ans[i], 2);
    printf("%d ", ans[i]);
  }
}