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;
using LL = long long;
using PII = pair<int, int>;
inline void umax(int& a, int b) {
  if (a < b) a = b;
}
const int N = 5e5 + 10;
vector<int> adj[N];
int brute_ans[N];
void brute(int n) {
  vector<vector<int>> dis(n + 1, vector<int>(n + 1, N));
  for (int u = 1; u <= n; u++) {
    dis[u][u] = 0;
    for (int v : adj[u]) {
      dis[u][v] = 1;
    }
  }
  for (int w = 1; w <= n; w++) {
    for (int u = 1; u <= n; u++) {
      for (int v = 1; v <= n; v++) {
        dis[u][v] = min(dis[u][v], dis[u][w] + dis[w][v]);
      }
    }
  }
  for (int i = 1; i <= n; i++) {
    brute_ans[i] = 1;
  }
  for (int mask = 1; mask < (1 << n); mask++) {
    int lo = 1e8, hi = -1;
    vector<int> cur;
    for (int u = 1; u <= n; u++) {
      if (mask & (1 << (u - 1))) {
        for (int v : cur) {
          lo = min(lo, dis[v][u]);
          hi = max(hi, dis[v][u]);
        }
        cur.push_back(u);
      }
    }
    if (cur.size() <= 1) continue;
    if (lo + 1 >= hi) {
      umax(brute_ans[lo], cur.size());
    }
  }
}
int dep[N];
pair<int, int> best[N];
vector<int> deps[N];
void compute(int u, int p) {
  dep[u] = 0;
  best[u] = {0, 0};
  for (int v : adj[u]) {
    if (v == p) continue;
    compute(v, u);
    if (dep[v] + 1 > best[u].second) {
      best[u].second = dep[v] + 1;
    }
    if (best[u].first < best[u].second) {
      swap(best[u].first, best[u].second);
    }
    deps[u].emplace_back(dep[v] + 1);
    dep[u] = max(dep[u], dep[v] + 1);
  }
}
int ans[2 * N], sum[N];
vector<PII> freq[N];
int compress(vector<PII>& vec, int sz = -1) {
  if (sz == -1) sz = vec.size();
  sort(vec.begin(), vec.begin() + sz);
  int j = 0;
  for (int i = 1; i < sz; i++) {
    if (vec[i].first == vec[j].first) {
      if (j < i) vec[j].second += vec[i].second;
    } else {
      j++;
      vec[j] = vec[i];
    }
  }
  return j + 1;
}
vector<PII> tmp;
void solve(int u, int p, int d) {
  int tot = 0;
  freq[u].reserve(adj[u].size());
  for (int dd : deps[u]) {
    freq[u].emplace_back(dd, 1);
    tot++;
  }
  if (d > 0) {
    freq[u].emplace_back(d, 1);
    tot++;
  }
  int len = compress(freq[u]);
  freq[u].resize(len);
  sum[u] = tot;
  int prv = -1;
  for (auto& e : freq[u]) {
    int sz = e.first;
    umax(ans[2 * sz], tot);
    umax(ans[2 * sz - 1], tot);
    if (prv != -1) {
      umax(ans[2 * prv + 1], tot + 1);
    }
    tot -= e.second;
    prv = sz;
  }
  for (int v : adj[u]) {
    if (v == p) continue;
    int dd = d + 1;
    if (dep[v] + 1 == best[u].first) {
      dd = 1 + max(d, best[u].second);
    } else {
      dd = 1 + max(d, best[u].first);
    }
    solve(v, u, dd);
  }
  if (u == p) return;
  int usz = freq[u].size(), psz = freq[p].size();
  tot = sum[u] + sum[p] - 1;
  if (d > 0) tot--;
  for (int i = 0, j = 0; i < usz || j < psz;) {
    int sz = -1, rem = 0;
    if (i < usz && j < psz && freq[u][i].first == freq[p][j].first) {
      sz = freq[u][i].first;
      rem = freq[u][i].second + freq[p][j].second;
      if (sz == d) rem--;
      if (sz == dep[u] + 1) rem--;
      i++;
      j++;
    } else if (i < usz && (j >= psz || freq[u][i].first < freq[p][j].first)) {
      sz = freq[u][i].first;
      rem = freq[u][i].second;
      if (sz == d) rem--;
      i++;
    } else {
      sz = freq[p][j].first;
      rem = freq[p][j].second;
      if (sz == dep[u] + 1) rem--;
      j++;
    }
    umax(ans[2 * sz], tot);
    tot -= rem;
  }
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  int n;
  cin >> n;
  for (int i = 0; i < n - 1; i++) {
    int u, v;
    cin >> u >> v;
    adj[u].push_back(v);
    adj[v].push_back(u);
  }
  compute(1, 1);
  tmp.resize(N);
  solve(1, 1, 0);
  for (int i = 2 * n; i >= 1; i--) {
    umax(ans[i], ans[i + 2]);
    umax(ans[i], 1);
  }
  for (int i = 1; i <= n; i++) {
    umax(ans[1], adj[i].size() + 1);
  }
  for (int i = 1; i <= n; i++) {
    cout << ans[i] << ' ';
  }
  cout << endl;
  return 0;
}