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;
const long long MAX_N = 5e5 + 25;
long long n, ANS;
long long ans[MAX_N * 2];
long long up[MAX_N];
long long par[MAX_N];
vector<long long> down[MAX_N];
vector<long long> adj[MAX_N];
long long ret[MAX_N];
vector<pair<long long, long long> > vec;
long long cnt[MAX_N];
multiset<long long> Set[MAX_N];
long long dfs1(long long v, long long p = 0) {
  par[v] = p;
  for (long long u : adj[v])
    if (u != p) down[v].push_back(1 + dfs1(u, v));
  sort(down[v].begin(), down[v].end());
  if (down[v].size() == 0) return 0;
  ret[v] = down[v].back();
  return down[v].back();
}
void dfs2(long long v, long long p = 0, long long dis = -1) {
  dis++;
  up[v] = dis;
  for (long long u : adj[v])
    if (u != p) {
      if (ret[u] + 1 != down[v].back())
        dfs2(u, v, max(dis, down[v].back()));
      else {
        if (down[v].size() == 1)
          dfs2(u, v, dis);
        else
          dfs2(u, v, max(dis, down[v][down[v].size() - 2]));
      }
    }
}
void add(long long v) {
  cnt[v]++;
  if (v) {
    ANS = max(ANS, cnt[v] + cnt[par[v]]);
    auto a = Set[par[v]].lower_bound(cnt[v] - 1);
    if (a != Set[par[v]].end() && *a == cnt[v] - 1) Set[par[v]].erase(a);
    Set[par[v]].insert(cnt[v]);
  }
  if (Set[v].size()) {
    auto a = Set[v].end();
    a--;
    ANS = max(ANS, cnt[v] + *a);
  }
}
int main() {
  ios::sync_with_stdio(false), cin.tie(0);
  cin >> n;
  for (long long i = 0; i < n - 1; i++) {
    long long v, u;
    cin >> v >> u;
    v--, u--;
    adj[v].push_back(u);
    adj[u].push_back(v);
  }
  dfs1(0);
  dfs2(0);
  for (long long i = 1; i < n; i++) {
    down[i].push_back(up[i]);
    sort(down[i].begin(), down[i].end());
  }
  for (long long i = 0; i < n; i++) {
    for (long long a : down[i]) vec.push_back({a, i});
  }
  sort(vec.begin(), vec.end());
  for (long long i = 0; i < n; i++) {
    long long len = down[i].size();
    for (long long j = 1; j <= down[i].size(); j++) {
      ans[2 * down[i][len - j]] = max(ans[2 * down[i][len - j]], j);
      if (2 <= j && down[i][len - j] < down[i][len - (j - 1)])
        ans[2 * down[i][len - j] + 1] = max(ans[2 * down[i][len - j] + 1], j);
    }
  }
  for (long long i = 2 * MAX_N - 2; ~i; i--) ans[i] = max(ans[i], ans[i + 1]);
  ans[1]++;
  for (long long i = n; i; i--) {
    while (vec.size() && vec.back().first == i) {
      add(vec.back().second);
      vec.pop_back();
    }
    ans[2 * i] = max(ans[2 * i], ANS - 2);
  }
  for (long long i = 2 * MAX_N - 4; 0 <= i; i -= 2)
    ans[i] = max(ans[i], ans[i + 2]);
  for (long long i = 1; i <= n; i++) cout << max(1LL, ans[i]) << " ";
  return 0;
}