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;
vector<vector<int> > G;
vector<bool> vis;
vector<int> ans;
vector<pair<int, int> > mx, E;
vector<vector<int> > arr0, arr1;
vector<int> deg;
int dfs2(int root) {
  vis[root] = true;
  mx[root].first = 0, mx[root].second = 0;
  int p;
  for (int i = 0; i < G[root].size(); i++) {
    int v = G[root][i];
    if (!vis[v]) {
      p = dfs2(v);
      p++;
      arr1[root].push_back(p);
      if (p > mx[root].first) {
        mx[root].second = mx[root].first;
        mx[root].first = p;
      } else if (p > mx[root].second)
        mx[root].second = p;
    }
  }
  return mx[root].first;
}
void dfs3(int root, int big) {
  vis[root] = true;
  if (root != 0) arr1[root].push_back(big);
  for (int i = 0; i < G[root].size(); i++) {
    int v = G[root][i];
    if (!vis[v]) {
      int y;
      if (mx[root].first == mx[v].first + 1)
        y = mx[root].second;
      else
        y = mx[root].first;
      y = max(y, big);
      y++;
      dfs3(v, y);
    }
  }
}
int main() {
  int n;
  cin >> n;
  G.resize(n);
  arr0.resize(n);
  arr1.resize(n);
  mx.resize(n);
  vis.resize(n);
  deg.resize(n);
  ans.resize(2 * n + 1, 1);
  int i, j, k;
  for (i = 0; i < n - 1; i++) {
    int x, y;
    cin >> x >> y;
    x--, y--;
    E.push_back(make_pair(x, y));
    G[x].push_back(y);
    G[y].push_back(x);
    deg[x]++;
    deg[y]++;
  }
  dfs2(0);
  vis.clear();
  vis.resize(n);
  for (i = 0; i < n; i++) dfs3(0, 0);
  vector<vector<pair<int, int> > > arr(n);
  for (i = 0; i < n; i++) {
    sort(arr1[i].begin(), arr1[i].end(), greater<int>());
    for (j = 0; j < arr1[i].size();) {
      for (k = j; j < arr1[i].size(); j++)
        if (arr1[i][j] != arr1[i][k]) break;
      arr[i].push_back(make_pair(arr1[i][k], j - k));
    }
  }
  for (i = 0; i < n; i++) {
    int sz = arr1[i].size();
    for (j = 0; j < sz; j++) {
      int upd = min(2 * arr1[i][j] - 1, 2 * n);
      ans[upd] = max(ans[upd], j + 1);
      if (j + 1 < sz) {
        upd = min(upd, 2 * arr1[i][j + 1] + 1);
        ans[upd] = max(ans[upd], j + 2);
      }
    }
    for (j = 0; j < sz; j++) {
      int upd = min(2 * arr1[i][j], 2 * n);
      ans[upd] = max(ans[upd], j + 1);
    }
    ans[1] = max(ans[1], deg[i] + 1);
  }
  int x, y;
  for (i = 0; i < n - 1; i++) {
    x = E[i].first, y = E[i].second;
    j = 0, k = 0;
    int c1 = 0, c2 = 0;
    while (j < arr[x].size() && k < arr[y].size()) {
      if (arr[x][j].first > arr[y][k].first) {
        c1 += arr[x][j].second;
        int upd = min(2 * arr[y][k].first, 2 * n);
        ans[upd] = max(ans[upd], c1 + c2 - 2);
        upd = min(2 * arr[x][j].first, 2 * n);
        ans[upd] = max(ans[upd], c1 + c2 - 2);
        j++;
      } else {
        c2 += arr[y][k].second;
        int upd = min(2 * arr[y][k].first, 2 * n);
        ans[upd] = max(ans[upd], c1 + c2 - 2);
        upd = min(2 * arr[x][j].first, 2 * n);
        ans[upd] = max(ans[upd], c1 + c2 - 2);
        k++;
      }
    }
    while (j < arr[x].size()) {
      c1 += arr[x][j].second;
      int upd = min(2 * arr[x][j].first, 2 * n);
      ans[upd] = max(ans[upd], c1 + c2 - 2);
      j++;
    }
    while (k < arr[y].size()) {
      c2 += arr[y][k].second;
      int upd = min(2 * arr[y][k].first, 2 * n);
      ans[upd] = max(ans[upd], c1 + c2 - 2);
      k++;
    }
  }
  int tmp = 1;
  for (i = 2 * n; i >= 1; i -= 2) {
    tmp = max(tmp, ans[i]);
    ans[i] = tmp;
  }
  tmp = 1;
  for (i = 2 * n - 1; i >= 1; i -= 2) {
    tmp = max(tmp, ans[i]);
    ans[i] = tmp;
  }
  for (i = 1; i <= n; i++) cout << ans[i] << " ";
}