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;
template <typename T>
bool vmin(T& a, T b) {
  return (a > b) ? (a = b, true) : (false);
}
template <typename T>
bool vmax(T& a, T b) {
  return (a < b) ? (a = b, true) : (false);
}
template <typename T>
T smax(T x) {
  return x;
}
template <typename T, typename... K>
T smax(T a, const K&... args) {
  return max(a, smax(args...));
}
template <typename T>
T smin(T x) {
  return x;
}
template <typename T, typename... K>
T smin(T a, const K&... args) {
  return min(a, smin(args...));
}
template <typename A, typename B>
ostream& operator<<(ostream& os, const pair<A, B>& z) {
  os << "(" << z.first << ", " << z.second << ')';
  return os;
}
template <typename T>
ostream& operator<<(ostream& os, const vector<T>& a) {
  bool isfirst = true;
  os << "{";
  for (auto z : a) {
    if (!isfirst) {
      os << ", ";
    }
    os << z;
    isfirst = false;
  }
  os << '}';
  return os;
}
const int inf = (signed)(~0u >> 2);
const long long llf = (signed long long)(~0ull >> 2);
template <typename T>
int vsize(vector<T>& x) {
  return (signed)x.size();
}
template <typename T>
void discrete(T* a, int* b, int n) {
  vector<T> v(a + 1, a + n + 1);
  sort(v.begin(), v.end());
  for (int i = 1; i <= n; i++)
    b[i] = lower_bound(v.begin(), v.end(), a[i]) - v.begin() + 1;
}
mt19937 rng(time(NULL));
const int N = 5e5 + 5;
int n;
int tg[N << 1];
int fd[N], fu[N];
vector<int> G[N];
vector<pair<int, int> > Gd[N];
void dfs1(int p, int fa) {
  fd[p] = 0;
  for (auto e : G[p]) {
    if (e ^ fa) {
      dfs1(e, p);
      vmax(fd[p], fd[e] + 1);
    }
  }
}
void dfs2(int p, int fa) {
  int mx = fu[p];
  for (auto e : G[p]) {
    if (e ^ fa) {
      vmax(fu[e], mx + 1);
      vmax(mx, fd[e] + 1);
    }
  }
  reverse(G[p].begin(), G[p].end());
  mx = 0;
  for (auto e : G[p]) {
    if (e ^ fa) {
      vmax(fu[e], mx + 1);
      vmax(mx, fd[e] + 1);
    }
  }
  reverse(G[p].begin(), G[p].end());
  for (auto e : G[p]) {
    if (e ^ fa) {
      dfs2(e, p);
    }
  }
}
void dfs3(int p, int fa) {
  vmax(tg[1], vsize(G[p]) + 1);
  vector<int> d;
  auto& D = Gd[p];
  for (auto e : G[p])
    if (e ^ fa) d.push_back(fd[e] + 1);
  if (fa) d.push_back(fu[p]);
  sort(d.begin(), d.end());
  for (auto t : d) {
    if (D.empty() || D.back().first ^ t) {
      D.emplace_back(t, 1);
    } else {
      D.back().second++;
    }
  }
  auto& Dfa = Gd[fa];
  auto itx = lower_bound(Dfa.begin(), Dfa.end(), pair<int, int>(fd[p] + 1, 0));
  auto ity = lower_bound(D.begin(), D.end(), pair<int, int>(fu[p], 0));
  if (fa) (*itx).second--, (*ity).second--;
  vector<pair<int, int> > E;
  auto p1 = D.begin(), _p1 = D.end();
  auto p2 = Dfa.begin(), _p2 = Dfa.end();
  while (p1 != _p1 && p2 != _p2) {
    if ((*p1).first == (*p2).first) {
      E.emplace_back((*p1).first, (*p1).second + (*p2).second);
      p1++, p2++;
    } else if ((*p1).first < (*p2).first) {
      E.push_back(*(p1++));
    } else {
      E.push_back(*(p2++));
    }
  }
  while (p1 != _p1) E.push_back(*p1++);
  while (p2 != _p2) E.push_back(*p2++);
  int cnt = 0;
  reverse(E.begin(), E.end());
  for (auto e : E) {
    cnt += e.second;
    vmax(tg[e.first * 2], cnt);
  }
  if (fa) (*itx).second++, (*ity).second++;
  reverse(D.begin(), D.end());
  cnt = 0;
  for (auto e : D) {
    if (e.second) {
      vmax(tg[e.first * 2 + 1], cnt + 1);
      cnt += e.second;
      vmax(tg[e.first * 2], cnt);
      vmax(tg[e.first * 2 - 1], cnt);
    }
  }
  reverse(D.begin(), D.end());
  for (auto e : G[p])
    if (e ^ fa) dfs3(e, p);
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0), cout.tie(0);
  cin >> n;
  for (int i = 1, u, v; i < n; i++) {
    cin >> u >> v;
    G[u].push_back(v);
    G[v].push_back(u);
  }
  dfs1(1, 0);
  dfs2(1, 0);
  dfs3(1, 0);
  for (int i = (n * 2); i > 1; i--) {
    tg[i] = max(tg[i], 1);
    vmax(tg[i - 2], tg[i]);
  }
  for (int i = 1; i <= n; i++) {
    cout << tg[i] << " ";
  }
  return 0;
}