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 uint = unsigned int;
using ll = long long;
using ld = long double;
using ull = unsigned long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
void debug_out() { cerr << endl; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
  cerr << " " << H;
  debug_out(T...);
}
template <typename T1, typename T2>
ostream &operator<<(ostream &out, const pair<T1, T2> &item) {
  out << '(' << item.first << ", " << item.second << ')';
  return out;
}
template <typename T>
ostream &operator<<(ostream &out, const vector<T> &v) {
  for (const auto &item : v) out << item << ' ';
  return out;
}
const int N = 500010;
int ans[N];
int fth[N], depth[N], depth2[N], depthUp[N];
vector<int> adj[N];
vector<pii> cnt[N];
void update(int v, int d) {
  if (d > depth[v])
    depth2[v] = depth[v], depth[v] = d;
  else
    depth2[v] = max(depth2[v], d);
}
void dfs(int v, int p = -1) {
  for (auto u : adj[v]) {
    if (u == p) continue;
    fth[u] = v;
    dfs(u, v);
    update(v, 1 + depth[u]);
  }
}
void dfsUp(int v, int p = -1) {
  for (auto u : adj[v]) {
    if (u == p) continue;
    depthUp[u] =
        1 + max(depthUp[v], (depth[v] == 1 + depth[u] ? depth2[v] : depth[v]));
    dfsUp(u, v);
  }
}
int main() {
  ios_base::sync_with_stdio(false);
  int n, a, b;
  cin >> n;
  for (int i = 1; i < n; ++i) {
    cin >> a >> b;
    adj[a].push_back(b);
    adj[b].push_back(a);
  }
  dfs(1);
  dfsUp(1);
  for (int i = 1; i <= n; ++i) {
    for (auto j : adj[i])
      if (j == fth[i])
        cnt[i].push_back({depthUp[i], 1});
      else
        cnt[i].push_back({1 + depth[j], 1});
    sort(cnt[i].rbegin(), cnt[i].rend());
    int j, k;
    for (k = 0, j = 1; j < cnt[i].size(); ++j)
      if (cnt[i][k].first == cnt[i][j].first)
        ++cnt[i][k].second;
      else
        cnt[i][++k] = cnt[i][j];
    cnt[i].erase(cnt[i].begin() + k + 1, cnt[i].end());
  }
  for (int i = 1; i <= n; ++i) {
    int s = 0;
    for (int j = 0; j < cnt[i].size(); ++j) {
      s += cnt[i][j].second;
      if (s > 1)
        ans[2 * cnt[i][j].first - 1] = max(ans[2 * cnt[i][j].first - 1], s);
      if (j + 1 < cnt[i].size())
        ans[2 * cnt[i][j + 1].first + 1] =
            max(ans[2 * cnt[i][j + 1].first + 1], s + 1);
      if (s > 1) ans[2 * cnt[i][j].first] = max(ans[2 * cnt[i][j].first], s);
    }
  }
  for (int i = 2; i <= n; ++i) {
    int s1 = 0, s2 = 0, f = fth[i], val;
    for (int j = 0, k = 0; j < cnt[i].size() || k < cnt[f].size();) {
      if (j == cnt[i].size() ||
          (k < cnt[f].size() && cnt[i][j].first < cnt[f][k].first))
        s2 += cnt[f][k].second, val = cnt[f][k].first, ++k;
      else
        s1 += cnt[i][j].second, val = cnt[i][j].first, ++j;
      if (s1 && s2 && s1 + s2 > 2)
        ans[2 * val] = max(ans[2 * val], s1 + s2 - 2);
    }
  }
  ans[n + 1] = ans[n + 2] = 1;
  for (int i = n; i >= 1; --i) ans[i] = max(ans[i], ans[i + 2]);
  for (int i = 1; i <= n; ++i) ans[1] = max(ans[1], 1 + (int)adj[i].size());
  for (int i = 1; i <= n; ++i) cout << ans[i] << ' ';
  cout << '\n';
  return 0;
}