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>
int a[500002], b[500002], c[500002], tmp[500002], tp, n;
int Last[500002], Next[1000002], End[1000002];
int d[500002], t[500002], s[500002];
std::vector<std::pair<int, int> > v[500002];
std::pair<int, int> g[500002], *top;
void dfs0(int p, int f) {
  int u = 0, v = 0;
  for (int i = Last[p]; i; i = Next[i])
    if (End[i] != f) {
      dfs0(End[i], p);
      if (d[End[i]] + 1 > v) v = d[End[i]] + 1;
      if (v > u) u ^= v ^= u ^= v;
    }
  d[p] = u;
  t[p] = v;
}
void dfs1(int p, int f) {
  for (int i = Last[p]; i; i = Next[i])
    if (End[i] != f) {
      if (d[End[i]] == d[p] - 1)
        s[End[i]] = t[p] + 1;
      else
        s[End[i]] = d[p] + 1;
      if (s[End[i]] < s[p] + 1) s[End[i]] = s[p] + 1;
      dfs1(End[i], p);
    }
}
void dfs2(int p, int f) {
  tp = 0;
  if (s[p]) tmp[tp++] = s[p];
  for (int i = Last[p]; i; i = Next[i])
    if (End[i] != f) tmp[tp++] = d[End[i]] + 1;
  std::sort(tmp, tmp + tp, [](int a, int b) { return a > b; });
  if (a[0] < tp + 1) a[0] = tp + 1;
  for (int i = 1; i < tp; i++) {
    if (a[tmp[i] - (tmp[i] == tmp[i - 1])] < i + 1)
      a[tmp[i] - (tmp[i] == tmp[i - 1])] = i + 1;
    if (b[tmp[i]] < i + 1) b[tmp[i]] = i + 1;
  }
  for (int i = Last[p]; i; i = Next[i])
    if (End[i] != f) dfs2(End[i], p);
}
void dfs3(int p, int f) {
  top = g;
  if (s[p]) *top++ = std::make_pair(s[p], 1);
  for (int i = Last[p]; i; i = Next[i])
    if (End[i] != f) *top++ = std::make_pair(d[End[i]] + 1, 1);
  std::sort(g, top,
            [](std::pair<int, int> a, std::pair<int, int> b) { return a > b; });
  for (std::pair<int, int>* i = g; i != top; i++) {
    if (v[p].empty() || v[p].back().first != i->first)
      v[p].push_back(*i);
    else
      v[p].back().second++;
  }
  for (int i = Last[p]; i; i = Next[i])
    if (End[i] != f) dfs3(End[i], p);
}
void dfs4(int p, int f) {
  for (int i = Last[p]; i; i = Next[i])
    if (End[i] != f) {
      int dec1 = s[End[i]], dec2 = d[End[i]] + 1;
      g->second = 0;
      std::vector<std::pair<int, int> >::iterator p1 = v[p].begin(),
                                                  p2 = v[End[i]].begin(),
                                                  e1 = v[p].end(),
                                                  e2 = v[End[i]].end();
      for (top = g; p1 != e1 || p2 != e2;) {
        if (p2 != e2 && (p1 == e1 || p1->first < p2->first)) {
          if (top == g || (top - 1)->first != p2->first)
            top->first = p2->first, top++, top->second = 0;
          (top - 1)->second += p2->second;
          p2++;
        } else {
          if (top == g || (top - 1)->first != p1->first)
            top->first = p1->first, top++, top->second = 0;
          (top - 1)->second += p1->second;
          p1++;
        }
        if (top != g && (top - 1)->first == dec1)
          if (!--(top - 1)->second) top--;
        if (top != g && (top - 1)->first == dec2)
          if (!--(top - 1)->second) top--;
      }
      int cnt = 0;
      for (std::pair<int, int>* i = g; i != top; i++) {
        cnt += i->second;
        if (c[i->first] < cnt) c[i->first] = cnt;
      }
      dfs4(End[i], p);
    }
}
int main() {
  scanf("%d", &n);
  for (int i = 1, j = 0; i <= n; i += 2, j++) a[j] = 1;
  for (int i = 2, j = 1; i <= n; i += 2, j++) b[j] = c[j] = 1;
  for (int i = 1; i < n + n - 2; i += 2) {
    scanf("%d%d", &End[i + 1], &End[i]);
    Next[i] = Last[End[i + 1]];
    Last[End[i + 1]] = i;
    Next[i + 1] = Last[End[i]];
    Last[End[i]] = i + 1;
  }
  dfs0(1, 0);
  dfs1(1, 0);
  dfs2(1, 0);
  dfs3(1, 0);
  dfs4(1, 0);
  for (int i = n / 2; i > 0; i--) {
    if (a[i - 1] < a[i]) a[i - 1] = a[i];
    if (b[i - 1] < b[i]) b[i - 1] = b[i];
    if (c[i - 1] < c[i]) c[i - 1] = c[i];
  }
  for (int i = 1; i <= n; i++) {
    if (i & 1)
      printf("%d ", a[i >> 1]);
    else
      printf("%d ", b[i >> 1] > c[i >> 1] ? b[i >> 1] : c[i >> 1]);
  }
}