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 int maxn = 1 << 19;
int n, answer[maxn];
vector<int> g[maxn];
array<int, 2> furthest(int v, int p) {
  array<int, 2> ans = {0, v};
  for (auto &i : g[v])
    if (i != p) {
      auto t = furthest(i, v);
      t[0]++;
      ans = max(ans, t);
    }
  return ans;
}
int p[maxn], h[maxn], h2[maxn], th[maxn];
vector<int> ch[maxn];
void dfs(int v) {
  for (auto &i : g[v]) {
    g[i].erase(find(g[i].begin(), g[i].end(), v));
    p[i] = v;
    dfs(i);
    h[v] = max(h[v], h[i] + 1);
    ch[v].push_back(h[i] + 1);
  }
  sort(ch[v].begin(), ch[v].end());
  h2[v] = ch[v].size() > 1 ? ch[v][ch[v].size() - 2] : 0;
}
void top(int v) {
  for (auto &i : g[v]) {
    th[i] = max(th[v] + 1, (h[i] + 1 == h[v] ? h2[v] : h[v]) + 1);
    top(i);
  }
}
int count(int v, int block, int d, int extra) {
  int c = ch[v].end() - lower_bound(ch[v].begin(), ch[v].end(), d);
  if (block != -1) c += (th[v]) >= d;
  if (block >= 0) c -= h[block] >= d;
  if (extra)
    c += !!binary_search(ch[v].begin(), ch[v].end(), d - 1) || (d - 1 == 0) ||
         th[v] == d - 1;
  return c;
}
signed main() {
  cin.tie(0)->sync_with_stdio(0);
  cin >> n;
  for (int f, t, i = 1; i < n; i++) {
    cin >> f >> t;
    g[f].push_back(t);
    g[t].push_back(f);
  }
  int diameter = 0;
  {
    int v1 = furthest(1, 0)[1];
    diameter = furthest(v1, 0)[0];
  }
  dfs(1);
  top(1);
  for (int v = 1; v <= n; v++) {
    for (int d = 1; d <= min(2 * h2[v] + 2, n); d++) {
      int l = d / 2, r = l + 1;
      answer[d] = max(answer[d], count(v, -2, (d & 1) + l, d & 1));
      if ((d & 1) || v == 1) continue;
      answer[d] = max(answer[d], count(v, -1, l, 0) + count(p[v], v, l, 0));
    }
  }
  for (int i = 1; i <= n; i++) {
    answer[i] = max(answer[i], 1 + (i <= diameter));
    cout << answer[i] << " ";
  }
  cout << '\n';
}