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 = 5e5 + 10, mod = 1e9 + 7;
int dp1[maxn], dp2[maxn];
vector<int> v[maxn], ds[maxn];
vector<pair<int, int> > dsp[maxn];
int ans[maxn], arr1[maxn], arr2[maxn];
void mxs(int &a, int b) { a = max(a, b); }
void dfsdn(int u, int par = 0) {
  for (int y : v[u]) {
    if (y != par) dfsdn(y, u), dp1[u] = max(dp1[u], dp1[y] + 1);
  }
}
void dfsup(int u, int par = 0) {
  int mx1 = -1, mx2 = -1;
  for (int y : v[u]) {
    if (y != par) {
      if (mx1 == -1 || dp1[mx1] < dp1[y])
        mx2 = mx1, mx1 = y;
      else if (mx2 == -1 || dp1[mx2] < dp1[y])
        mx2 = y;
    }
  }
  for (int y : v[u]) {
    if (y != par) {
      if (y == mx1) {
        dp2[y] = dp2[u] + 1;
        if (mx2 != -1) dp2[y] = max(dp2[y], dp1[mx2] + 2);
      } else {
        dp2[y] = max(dp2[u] + 1, dp1[mx1] + 2);
      }
      dfsup(y, u);
      ds[u].push_back(1 + dp1[y]);
    }
  }
  if (par != 0) {
    ds[u].push_back(dp2[u]);
  }
  sort(ds[u].begin(), ds[u].end(), greater<int>());
  for (int i = 1; i < int((ds[u]).size()); i++) {
    mxs(arr1[ds[u][i]], i + 1);
    if (ds[u][i - 1] != ds[u][i]) mxs(ans[2 * ds[u][i] + 1], i + 1);
  }
  for (int x : ds[u]) {
    if (dsp[u].empty() || dsp[u].back().first != x)
      dsp[u].push_back({x, 1});
    else
      dsp[u][int((dsp[u]).size()) - 1].second++;
  }
}
void dfs(int u, int par = 0) {
  for (int y : v[u]) {
    if (y != par) {
      dfs(y, u);
      int cnt1 = 0, cnt2 = 0, val1 = dp1[y] + 1, val2 = dp2[y];
      auto l1 = dsp[u].begin(), r1 = dsp[u].end();
      auto l2 = dsp[y].begin(), r2 = dsp[y].end();
      while (l1 != r1 || l2 != r2) {
        pair<int, int> p;
        if ((l2 == r2) || (l1 != r1 && (l1->first) >= (l2->first))) {
          p = *l1, l1++;
          if (p.first == val1) p.second--;
          cnt1 += p.second;
        } else {
          p = *l2, l2++;
          if (p.first == val2) p.second--;
          cnt2 += p.second;
        }
        if (cnt1 > 0 && cnt2 > 0) mxs(arr2[p.first], cnt1 + cnt2);
      }
    }
  }
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie();
  int n;
  cin >> n;
  for (int i = 0; i < n - 1; i++) {
    int a, b;
    cin >> a >> b;
    v[a].push_back(b);
    v[b].push_back(a);
  }
  dfsdn(1);
  dfsup(1);
  dfs(1);
  if (n > 1) {
    mxs(ans[1], 2);
  }
  for (int i = 1; i <= n; i++) {
    mxs(ans[i], 1);
    mxs(ans[1], int((v[i]).size()) + 1);
  }
  for (int i = n; i >= 1; i--) {
    mxs(arr1[i], arr1[i + 1]);
    mxs(arr2[i], arr2[i + 1]);
    mxs(ans[2 * i], arr2[i]);
    mxs(ans[2 * i], arr1[i]);
    mxs(ans[2 * i - 1], arr1[i]);
  }
  for (int i = 1; i <= n; i++) {
    cout << ans[i] << " ";
  }
  return cout << endl, 0;
}