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_MAX = 5e5, magic = 40;
int n, down[N_MAX - 1], up[N_MAX - 1], sol[N_MAX + 1];
bool seen[N_MAX];
pair<int, int> E[N_MAX - 1];
vector<int> G[N_MAX];
int DFS1(int u) {
  int ans = 0;
  seen[u] = true;
  for (int e : G[u]) {
    if (seen[E[e].first] && seen[E[e].second]) continue;
    if (E[e].second == u) swap(E[e].first, E[e].second);
    down[e] = DFS1(E[e].second) + 1;
    ans = max(ans, down[e]);
  }
  return ans;
}
void DFS2(int u) {
  int e1 = -1, e2 = -1, upp = 1;
  for (int e : G[u]) {
    if (E[e].second == u) {
      upp = up[e] + 1;
      continue;
    }
    if (e1 == -1)
      e1 = e;
    else if (down[e] > down[e1]) {
      e2 = e1;
      e1 = e;
    } else if (e2 == -1 || down[e] > down[e2]) {
      e2 = e;
    }
  }
  for (int e : G[u]) {
    if (E[e].second == u) continue;
    up[e] = upp;
    if (e != e1 && down[e1] + 1 > up[e]) up[e] = down[e1] + 1;
    if (e == e1 && e2 != -1 && down[e2] + 1 > up[e]) up[e] = down[e2] + 1;
    DFS2(E[e].second);
  }
}
vector<int> s;
void solve_odd() {
  for (int v = 0; v < n; v++) {
    s.clear();
    for (int e : G[v]) {
      if (E[e].first == v)
        s.push_back(down[e]);
      else
        s.push_back(up[e]);
    }
    sort(s.begin(), s.end(), greater<int>());
    for (int i = 1; i < s.size(); i++) {
      int l = (s[i - 1] > s[i] ? s[i] + 1 : s[i]);
      sol[2 * l - 1] = max(sol[2 * l - 1], i + 1);
      sol[2 * s[i]] = max(sol[2 * s[i]], i + 1);
    }
  }
  sol[1] = 0;
  for (int v = 0; v < n; v++) sol[1] = max(sol[1], (int)G[v].size() + 1);
  for (int k = (n % 2 ? n - 2 : n - 3); 0 < k; k -= 2)
    sol[k] = max(sol[k], sol[k + 2]);
}
int ok[N_MAX];
void solve(int k) {
  k /= 2;
  for (int v = 0; v < n; v++) {
    ok[v] = 0;
    for (int e : G[v]) {
      int x = (E[e].first == v ? down[e] : up[e]);
      if (x >= k) ok[v]++;
    }
  }
  for (int e = 0; e < n - 1; e++) {
    if (ok[E[e].first] > 1 && ok[E[e].second] > 1)
      sol[2 * k] = max(sol[2 * k], ok[E[e].first] + ok[E[e].second] - 2);
  }
}
vector<pair<int, int>> b[N_MAX];
void solve_big_even() {
  for (int v = 0; v < n; v++) {
    for (int e : G[v]) {
      int x = (E[e].first == v ? down[e] : up[e]);
      if (x >= magic) b[v].push_back({x, e});
    }
    sort(b[v].begin(), b[v].end(), greater<pair<int, int>>());
  }
  for (int e = 0; e < n - 1; e++) {
    if (b[E[e].first].size() < 2 || b[E[e].second].size() < 2) continue;
    s.clear();
    int u = E[e].first, v = E[e].second;
    int i1 = (b[u][0].second == e ? 1 : 0);
    int i2 = (b[v][0].second == e ? 1 : 0);
    while (i1 < b[u].size() || i2 < b[v].size()) {
      if (i2 == b[v].size() ||
          (i1 < b[u].size() && b[u][i1].first > b[v][i2].first)) {
        s.push_back(b[u][i1].first);
        i1++;
        if (i1 < b[u].size() && b[u][i1].second == e) i1++;
      } else {
        s.push_back(b[v][i2].first);
        i2++;
        if (i2 < b[v].size() && b[v][i2].second == e) i2++;
      }
    }
    for (int i = 1; i < s.size(); i++)
      sol[2 * s[i]] = max(sol[2 * s[i]], i + 1);
  }
  for (int k = (n % 2 ? n - 3 : n - 2); 2 * magic <= k; k -= 2)
    sol[k] = max(sol[k], sol[k + 2]);
}
int main() {
  cin >> n;
  for (int i = 0; i < n - 1; i++) {
    int u, v;
    cin >> u >> v;
    u--;
    v--;
    E[i] = {u, v};
    G[u].push_back(i);
    G[v].push_back(i);
  }
  DFS1(0);
  DFS2(0);
  for (int k = 1; k <= n; k++) sol[k] = 1;
  solve_odd();
  for (int k = 2; k < 2 * magic; k += 2) solve(k);
  solve_big_even();
  for (int k = 1; k <= n; k++) cout << sol[k] << " ";
  cout << endl;
  return 0;
}