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;
long long read() {
  long long x = 0, f = 0;
  char ch = getchar();
  while (!isdigit(ch)) f = ch == '-', ch = getchar();
  while (isdigit(ch)) x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
  return f ? -x : x;
}
template <class T>
void ckmax(T &x, const T &y) {
  if (x < y) x = y;
}
template <class T>
void ckmin(T &x, const T &y) {
  if (x > y) x = y;
}
long long absl(long long x) { return x < 0 ? -x : x; }
const int N = 500005 * 2;
int n;
vector<int> e[N];
int ans[N];
pair<int, int> mx1[N], mx2[N];
void dfs1(int x, int pre) {
  for (auto y : e[x])
    if (y != pre) {
      dfs1(y, x);
      pair<int, int> tmp = make_pair(mx1[y].first + 1, y);
      if (tmp > mx1[x]) swap(tmp, mx1[x]);
      if (tmp > mx2[x]) swap(tmp, mx2[x]);
    }
}
void dfs2(int x, int pre) {
  for (auto y : e[x])
    if (y != pre) {
      pair<int, int> tmp = make_pair(
          mx1[x].second != y ? mx1[x].first + 1 : mx2[x].first + 1, x);
      if (tmp > mx1[y]) swap(tmp, mx1[y]);
      if (tmp > mx2[y]) swap(tmp, mx2[y]);
      dfs2(y, x);
    }
}
void solver1(int x) {
  vector<int> len;
  for (auto y : e[x])
    len.push_back((mx1[y].second != x ? mx1[y].first : mx2[y].first) + 1);
  sort(len.begin(), len.end(), greater<int>());
  int las = -2, cnt = 0;
  for (auto i : len) {
    cnt++;
    ckmax(ans[i * 2], cnt);
    ckmax(ans[i * 2 - 1], cnt);
    if (las > i) ckmax(ans[i * 2 + 1], cnt);
    las = i;
  }
}
int Size, RT;
int sz[N], mxs[N], vis[N];
void getrt(int x, int pre) {
  sz[x] = 1, mxs[x] = 0;
  for (auto y : e[x])
    if (!vis[y] && y != pre) {
      getrt(y, x);
      sz[x] += sz[y];
      ckmax(mxs[x], sz[y]);
    }
  ckmax(mxs[x], Size - sz[x]);
  if (!RT || mxs[x] < mxs[RT]) RT = x;
}
int cnt[N];
void solve(int x, int SZ) {
  Size = SZ, RT = 0;
  getrt(x, 0);
  x = RT;
  vector<pair<int, int> > val;
  cnt[x] = 0;
  for (auto y : e[x]) {
    val.push_back(
        make_pair(mx1[y].second != x ? mx1[y].first + 1 : mx2[y].first + 1, x));
    if (!vis[y]) {
      cnt[y] = 0;
      for (auto z : e[y])
        val.push_back(make_pair(
            mx1[z].second != y ? mx1[z].first + 1 : mx2[z].first + 1, y));
    }
  }
  sort(val.begin(), val.end(), greater<pair<int, int> >());
  int mx = -1;
  for (auto p : val) {
    cnt[p.second]++;
    if (p.second != x) ckmax(mx, cnt[p.second]);
    if (mx > 0 && cnt[x] > 0) ckmax(ans[p.first * 2], cnt[x] + mx - 2);
  }
  vis[x] = 1;
  for (auto y : e[x])
    if (!vis[y]) solve(y, sz[y] < sz[x] ? sz[y] : SZ - sz[x]);
}
int main() {
  n = read();
  for (int i = (1); i <= (n - 1); i++) {
    int x = read(), y = read();
    e[x].push_back(y), e[y].push_back(x);
  }
  for (int i = (1); i <= (n); i++) {
    ckmax(ans[i], 1);
    ckmax(ans[1], (int)e[i].size() + 1);
  }
  dfs1(1, 0);
  dfs2(1, 0);
  for (int x = (1); x <= (n); x++) solver1(x);
  solve(1, n);
  for (int i = (n - 2); i >= (1); i--) ckmax(ans[i], ans[i + 2]);
  for (int i = (1); i <= (n); i++) printf("%d ", ans[i]);
  puts("");
  return 0;
}