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;
namespace IO {
const int ios = 1 << 17;
char R[ios], *Rc = R, *RB = R;
int pass;
inline int gec() {
  return (Rc == RB && (RB = (Rc = R) + fread(R, 1, ios, stdin), Rc == RB))
             ? EOF
             : *Rc++;
}
template <typename Tp>
inline int read(Tp& A) {
  static int c, sg;
  c = gec();
  sg = 0;
  A = 0;
  while (!isdigit(c) && c != EOF) sg |= (c == '-'), c = gec();
  if (c == EOF) return EOF;
  while (isdigit(c)) A = (A << 3) + (A << 1) + (c ^ '0'), c = gec();
  return A = sg ? -A : A, 0;
}
inline int read() { return read(pass), pass; }
}  // namespace IO
using IO::gec;
using IO::read;
const int N = 5e5 + 5;
template <typename T>
void cmax(T& a, T b) {
  if (b > a) a = b;
}
vector<int> e[N];
vector<pair<int, int> > a[N];
int du[N], up[N], res[N];
int n;
void DFS1(int x, int FAQ) {
  for (int to : e[x])
    if (to != FAQ) DFS1(to, x), cmax(du[x], du[to] + 1);
}
void DFS2(int x, int upon) {
  pair<int, int> b[2];
  b[0] = make_pair(up[x] = (upon + 1), -1);
  b[1] = make_pair(-1, -1);
  for (int to : e[x])
    if (du[to] < du[x]) {
      pair<int, int> su = make_pair(du[to] + 1, to);
      for (int k = 0; k < 2; k++)
        if (su > b[k]) swap(su, b[k]);
    }
  for (int to : e[x])
    if (du[to] < du[x]) DFS2(to, b[b[0].second == to].first);
}
int main() {
  read(n);
  for (int i = 1, u, v; i < n; i++) {
    read(u);
    read(v);
    --u;
    --v;
    e[u].push_back(v);
    e[v].push_back(u);
  }
  DFS1(0, -1);
  DFS2(0, -1);
  vector<int> cur;
  for (int x = 0; x < n; x++) {
    cur.clear();
    if (up[x]) cur.push_back(up[x]);
    for (int to : e[x])
      if (du[to] < du[x]) cur.push_back(du[to] + 1);
    sort(cur.begin(), cur.end());
    for (int dd : cur)
      if (a[x].empty() || a[x].back().first != dd)
        a[x].push_back(make_pair(dd, 1));
      else
        a[x].back().second++;
  }
  for (int i = 1; i <= n; i++) res[i] = 1;
  int diam = 0;
  for (int x = 0; x < n; x++) cmax(diam, a[x].back().first);
  for (int i = 1; i <= diam; i++) res[i] = 2;
  for (int x = 0; x < n; x++) cmax(res[1], (int)e[x].size() + 1);
  for (int x = 0; x < n; x++) {
    int sum = e[x].size();
    for (int i = 0, ios = a[x].size(); i < ios; i++) {
      cmax(res[(a[x][i].first << 1) - 1], sum);
      if (i > 0) cmax(res[(a[x][i - 1].first << 1) + 1], sum + 1);
      cmax(res[(a[x][i].first << 1)], sum);
      sum -= a[x][i].second;
    }
  }
  for (int x = 0; x < n; x++) {
    for (int to : e[x])
      if (du[to] < du[x]) {
        int sum = e[x].size() + e[to].size() - 2, c1 = 0, c2 = 0;
        for (auto QwQ : a[x])
          if (QwQ.first == du[to] + 1) QwQ.second--;
        for (auto QwQ : a[to])
          if (QwQ.first == up[to]) QwQ.second--;
        while (c1 < a[x].size() && c2 < a[to].size()) {
          int t = min(a[x][c1].first, a[to][c2].first);
          cmax(res[t << 1], sum);
          if (t == a[x][c1].first) sum -= a[x][c1++].second;
          if (t == a[to][c2].first) sum -= a[to][c2++].second;
        }
        for (auto QwQ : a[x])
          if (QwQ.first == du[to] + 1) QwQ.second++;
        for (auto QwQ : a[to])
          if (QwQ.first == up[to]) QwQ.second++;
      }
  }
  for (int i = n - 2; i >= 1; i--) cmax(res[i], res[i + 2]);
  for (int i = 1; i <= n; i++) printf("%d ", res[i]);
  return 0;
}