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;
int const N = 500000;
int an[N + 1 << 1], d[N + 1], n;
vector<int> tr[N + 1], jmp[N + 1];
vector<pair<int, int> > dp[N + 1];
map<int, int> mp[N + 1];
void pl1(int v = 1, int p = 0) {
  for (int i = 0; i < (int)(tr[v].size()); ++i) {
    int u = tr[v][i];
    if (u == p) continue;
    pl1(u, v);
    dp[v][i] = make_pair(1 + d[u], u);
    d[v] = max(d[v], 1 + d[u]);
  }
}
void up(int &x, int y) {
  if (y > x) x = y;
}
void pl2(int v = 1, int p = 0, int z = 0) {
  for (int i = 0; i < (int)(tr[v].size()); ++i) {
    int u = tr[v][i];
    if (u == p) dp[v][i] = make_pair(z, p);
  }
  int mx1 = -1, mx2 = -1;
  for (int i = 0; i < (int)(tr[v].size()); ++i) {
    if (mx1 == -1 || dp[v][i].first > dp[v][mx1].first)
      mx2 = mx1, mx1 = i;
    else if (mx2 == -1 || dp[v][i].first > dp[v][mx2].first)
      mx2 = i;
  }
  for (int i = 0; i < (int)(tr[v].size()); ++i) {
    int u = tr[v][i];
    if (u == p) continue;
    pl2(u, v,
        mx1 == i ? mx2 == -1 ? 1 : dp[v][mx2].first + 1 : dp[v][mx1].first + 1);
  }
}
void go(int a, int b) {
  int i = 0, j = 0, sa = mp[a][b], sb = mp[b][a];
  while (i < (int)dp[a].size() && j < (int)dp[b].size()) {
    int t = min(dp[a][i].first, dp[b][j].first) << 1;
    int fr = dp[a].size() - i + dp[b].size() - j;
    if (sa >= i) --fr;
    if (sb >= j) --fr;
    if (t <= n) up(an[t], fr);
    if (dp[a][i] < dp[b][j])
      i = jmp[a][i];
    else
      j = jmp[b][j];
  }
}
int main() {
  scanf("%d", &n);
  for (int i = 1; i < (int)(n); ++i) {
    int a, b;
    scanf("%d%d", &a, &b);
    tr[a].push_back(b);
    tr[b].push_back(a);
  }
  for (int i = 1; i < (int)(n + 1); ++i) dp[i].resize(tr[i].size());
  pl1();
  pl2();
  for (int i = 1; i < (int)(n + 1); ++i) up(an[1], tr[i].size() + 1);
  for (int i = 1; i < (int)(n + 1); ++i) {
    sort(dp[i].begin(), dp[i].end());
    for (int j = 0; j < (int)(dp[i].size()); ++j) {
      int t = dp[i][j].first << 1, fr = dp[i].size() - j;
      if (t <= n) {
        up(an[t - 1], fr + (j > 0 && dp[i][j - 1].first + 1 == dp[i][j].first));
        up(an[t], fr);
      }
      if (j > 0 && dp[i][j].first != dp[i][j - 1].first)
        up(an[(dp[i][j - 1].first + 1 << 1) - 1], fr + 1);
    }
  }
  for (int i = 1; i < (int)(n + 1); ++i)
    for (int j = 0; j < (int)(dp[i].size()); ++j) mp[i][dp[i][j].second] = j;
  for (int i = 1; i < (int)(n + 1); ++i) jmp[i].resize(dp[i].size());
  for (int i = 1; i < (int)(n + 1); ++i)
    for (int j = 0; j < (int)(dp[i].size()); ++j) {
      int k = j;
      while (k + 1 < (int)dp[i].size() && dp[i][k + 1].first == dp[i][k].first)
        ++k;
      jmp[i][j] = k + 1;
      j = k;
    }
  for (int i = 1; i < (int)(n + 1); ++i)
    for (int u : tr[i])
      if (u > i) go(i, u);
  an[n] = 1;
  up(an[n - 1], 1);
  for (int i = n - 2; i > 1; --i) up(an[i], an[i + 2]);
  printf("%d", an[1]);
  for (int i = 2; i < (int)(n + 1); ++i) printf(" %d", an[i]);
  printf("\n");
}