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 lint = long long int;
using pint = pair<int, int>;
using plint = pair<lint, lint>;
struct fast_ios {
  fast_ios() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(20);
  };
} fast_ios_;
template <typename T>
void ndarray(vector<T> &vec, int len) {
  vec.resize(len);
}
template <typename T, typename... Args>
void ndarray(vector<T> &vec, int len, Args... args) {
  vec.resize(len);
  for (auto &v : vec) ndarray(v, args...);
}
template <typename T>
bool mmax(T &m, const T q) {
  if (m < q) {
    m = q;
    return true;
  } else
    return false;
}
template <typename T>
bool mmin(T &m, const T q) {
  if (m > q) {
    m = q;
    return true;
  } else
    return false;
}
template <typename T1, typename T2>
pair<T1, T2> operator+(const pair<T1, T2> &l, const pair<T1, T2> &r) {
  return make_pair(l.first + r.first, l.second + r.second);
}
template <typename T1, typename T2>
pair<T1, T2> operator-(const pair<T1, T2> &l, const pair<T1, T2> &r) {
  return make_pair(l.first - r.first, l.second - r.second);
}
template <typename T>
istream &operator>>(istream &is, vector<T> &vec) {
  for (auto &v : vec) is >> v;
  return is;
}
template <typename T>
ostream &operator<<(ostream &os, const vector<T> &vec) {
  os << "[";
  for (auto v : vec) os << v << ",";
  os << "]";
  return os;
}
template <typename T>
ostream &operator<<(ostream &os, const deque<T> &vec) {
  os << "deq[";
  for (auto v : vec) os << v << ",";
  os << "]";
  return os;
}
template <typename T>
ostream &operator<<(ostream &os, const set<T> &vec) {
  os << "{";
  for (auto v : vec) os << v << ",";
  os << "}";
  return os;
}
template <typename T>
ostream &operator<<(ostream &os, const unordered_set<T> &vec) {
  os << "{";
  for (auto v : vec) os << v << ",";
  os << "}";
  return os;
}
template <typename T>
ostream &operator<<(ostream &os, const multiset<T> &vec) {
  os << "{";
  for (auto v : vec) os << v << ",";
  os << "}";
  return os;
}
template <typename T>
ostream &operator<<(ostream &os, const unordered_multiset<T> &vec) {
  os << "{";
  for (auto v : vec) os << v << ",";
  os << "}";
  return os;
}
template <typename T1, typename T2>
ostream &operator<<(ostream &os, const pair<T1, T2> &pa) {
  os << "(" << pa.first << "," << pa.second << ")";
  return os;
}
template <typename TK, typename TV>
ostream &operator<<(ostream &os, const map<TK, TV> &mp) {
  os << "{";
  for (auto v : mp) os << v.first << "=>" << v.second << ",";
  os << "}";
  return os;
}
template <typename TK, typename TV>
ostream &operator<<(ostream &os, const unordered_map<TK, TV> &mp) {
  os << "{";
  for (auto v : mp) os << v.first << "=>" << v.second << ",";
  os << "}";
  return os;
}
int N;
vector<int> lgtail;
vector<int> uptail;
vector<vector<int>> e;
vector<int> par;
vector<map<int, int>> tails;
void dfs_tail(int now, int prv) {
  par[now] = prv;
  for (auto nxt : e[now])
    if (nxt != prv) {
      dfs_tail(nxt, now);
      mmax(lgtail[now], lgtail[nxt] + 1);
    }
}
void dfs_uptail(int now, int prv, int len = 0) {
  for (auto nxt : e[now])
    if (nxt != prv) tails[now][lgtail[nxt] + 1]++;
  if (prv >= 0) {
    uptail[now] = max(uptail[prv], len) + 1;
    tails[now][uptail[now]]++;
  }
  vector<pint> l2id{{0, -1}};
  for (auto nxt : e[now])
    if (nxt != prv) l2id.emplace_back(lgtail[nxt] + 1, nxt);
  sort(l2id.rbegin(), l2id.rend());
  for (auto nxt : e[now])
    if (nxt != prv) {
      int i = 0;
      if (l2id[i].second == nxt) i++;
      dfs_uptail(nxt, now, l2id[i].first);
    }
}
int main() {
  cin >> N;
  e.resize(N);
  for (int i = (0), i_end_ = (N - 1); i < i_end_; i++) {
    int u, v;
    cin >> u >> v;
    u--, v--;
    e[u].emplace_back(v);
    e[v].emplace_back(u);
  }
  par.resize(N, -1);
  lgtail.resize(N);
  dfs_tail(0, -1);
  tails.resize(N);
  uptail.resize(N);
  dfs_uptail(0, -1);
  vector<int> ret(N * 2 + 3, 1);
  for (int i = (0), i_end_ = (N); i < i_end_; i++)
    mmax(ret[1], (int)e[i].size() + 1);
  for (int i = (0), i_end_ = (N); i < i_end_; i++)
    mmax(ret[2], (int)e[i].size());
  for (int i = (0), i_end_ = (N); i < i_end_; i++) {
    int nb = 0;
    for (auto p : tails[i]) nb += p.second;
    for (auto p : tails[i]) {
      if (p.second > 1 and p.first > 1) {
        mmax(ret[p.first * 2 - 1], nb);
      }
      mmax(ret[p.first * 2 + 1], nb - p.second + 1);
      mmax(ret[p.first * 2], nb);
      mmax(ret[p.first], 2);
      nb -= p.second;
    }
  }
  for (int c = (1), c_end_ = (N); c < c_end_; c++) {
    int p = par[c];
    if (tails[p].size() <= 1 or tails[c].size() <= 1) continue;
    map<int, int> ma = tails[p];
    for (auto p : tails[c]) ma[p.first] += p.second;
    ma[lgtail[c] + 1]--;
    ma[uptail[c]]--;
    int nb = 0;
    for (auto p : ma) nb += p.second;
    for (auto p : ma)
      if (p.second) {
        mmax(ret[p.first * 2], nb);
        nb -= p.second;
      }
  }
  for (int i = (N)-1, i_begin_ = (0); i >= i_begin_; i--)
    mmax(ret[i], ret[i + 2]);
  for (int i = (1), i_end_ = (N + 1); i < i_end_; i++) printf("%d ", ret[i]);
  puts("");
}