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 N = 1e6 + 5;
const int inf = 0x3f3f3f3f;
vector<pair<int, int> > S;
vector<pair<int, int> > Q;
int n;
vector<int> g[N];
int mx[N], dep[N], f[N];
void dfs(int u, int p) {
  f[u] = p;
  S.push_back(pair<int, int>(0, u));
  for (int i = (0); i < ((int)g[u].size()); i++)
    if (g[u][i] == p) g[u].erase(g[u].begin() + i);
  for (auto v : g[u]) {
    dep[v] = dep[u] + 1;
    dfs(v, u);
    mx[u] = max(mx[u], mx[v] + 1);
    S.push_back(pair<int, int>(mx[v] + 1, u));
    Q.push_back(pair<int, int>(mx[v] + 1, u));
  }
}
void gao(int u, int val) {
  if (u != 1) {
    S.push_back(pair<int, int>(val, u));
  }
  vector<int> pre, suf;
  pre.resize((int)g[u].size() + 1);
  suf.resize((int)g[u].size() + 1);
  pre[0] = -1;
  for (int i = (0); i < ((int)g[u].size() - 1); i++)
    pre[i + 1] = max(pre[i], mx[g[u][i]]);
  for (int i = (int)g[u].size() - 1; i > 0; --i) {
    suf[i - 1] = max(suf[i], mx[g[u][i]]);
  }
  if ((int)g[u].size()) suf[(int)g[u].size() - 1] = -1;
  for (int i = (0); i < ((int)g[u].size()); i++) {
    int t = max(max(val, pre[i] + 1), suf[i] + 1) + 1;
    gao(g[u][i], t);
  }
}
int ans[N];
int cnt[N], a[N], b[N];
bool vis[N];
bool cmp(pair<int, int> x, pair<int, int> y) {
  if (x.first != y.first) return x.first < y.first;
  return dep[x.second] > dep[y.second];
}
int main() {
  scanf("%d", &n);
  int u, v;
  for (int i = (1); i < (n); i++) {
    scanf("%d%d", &u, &v);
    g[u].push_back(v), g[v].push_back(u);
  }
  dfs(1, 0);
  gao(1, 0);
  sort(S.begin(), S.end(), cmp);
  sort(Q.begin(), Q.end(), cmp);
  int mx = (n + 1) / 2;
  while ((int)S.size() && S.back().first > mx) {
    cnt[S.back().second]++;
    ans[mx * 2] = max(ans[mx * 2], cnt[S.back().second]);
    ans[mx * 2 - 1] = max(ans[mx * 2 - 1], cnt[S.back().second]);
    S.pop_back();
  }
  while ((int)Q.size() && Q.back().first > mx) {
    a[Q.back().second]++;
    Q.pop_back();
  }
  vector<int> vec;
  for (int i = mx; i >= 0; --i) {
    while ((int)S.size() && S.back().first == i) {
      u = S.back().second;
      cnt[u]++;
      ans[i * 2] = max(ans[i * 2], cnt[S.back().second]);
      ans[i * 2] = max(ans[i * 2], cnt[u] + b[u]);
      if (i > 0) ans[i * 2 - 1] = max(ans[i * 2 - 1], cnt[S.back().second]);
      if (!vis[u]) {
        ans[i * 2 + 1] = max(ans[i * 2 + 1], cnt[u]);
      }
      vis[u] = 1;
      S.pop_back();
      vec.push_back(u);
    }
    while ((int)Q.size() && Q.back().first == i) {
      u = Q.back().second;
      a[u]++;
      if (f[u]) ans[i * 2] = max(ans[i * 2], cnt[f[u]] + a[u] - 1);
      b[f[u]] = max(b[f[u]], a[u] - 1);
      Q.pop_back();
    }
    for (auto v : vec) vis[v] = 0;
    vec.clear();
  }
  for (int i = n; i >= 1; --i) {
    ans[i] = max(ans[i + 2], ans[i]);
  }
  for (int i = (1); i < (n + 1); i++) {
    ans[i] = max(ans[i], 1);
    printf(" %d" + (i == 1), ans[i]);
  }
  return 0;
}