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;
pair<int, int> bfs(const int s, const vector<vector<int>> &g) {
  const int n = int(g.size());
  queue<int> q;
  vector<int> dist(n, -1);
  q.push(s);
  dist[s] = 0;
  while (!q.empty()) {
    const int cur = q.front();
    q.pop();
    for (int dest : g[cur]) {
      if (dist[dest] == -1) {
        q.push(dest);
        dist[dest] = dist[cur] + 1;
      }
    }
  }
  int pos = max_element(dist.begin(), dist.end()) - dist.begin();
  return pair<int, int>(pos, dist[pos]);
}
int cnt_at_least(const vector<int> &v, int what) {
  return v.end() - lower_bound(v.begin(), v.end(), what);
}
void remax(int &x, int y) { x = max(x, y); }
void dfs(int x, int p, const vector<vector<int>> &g, vector<int> &par,
         vector<int> &depth) {
  depth[x] = 0;
  par[x] = p;
  for (int dest : g[x]) {
    if (dest != p) {
      dfs(dest, x, g, par, depth);
      depth[x] = max(depth[x], depth[dest] + 1);
    }
  }
}
void dfs_up(int x, int p, const vector<vector<int>> &g,
            const vector<int> &depth, vector<int> &up) {
  int mx1 = -1, mx2 = -1;
  for (int dest : g[x]) {
    if (dest != p) {
      if (mx1 < depth[dest]) {
        mx2 = mx1;
        mx1 = depth[dest];
      } else if (mx2 < depth[dest]) {
        mx2 = depth[dest];
      }
    }
  }
  for (int dest : g[x]) {
    if (dest != p) {
      up[dest] = 1 + max(up[x], 1 + (depth[dest] == mx1 ? mx2 : mx1));
      dfs_up(dest, x, g, depth, up);
    }
  }
}
void solve(istream &cin = std::cin, ostream &cout = std::cout) {
  int n;
  cin >> n;
  vector<vector<int>> g(n);
  for (int i = 0; i < n - 1; i++) {
    int u, v;
    cin >> u >> v;
    --u, --v;
    g[u].push_back(v);
    g[v].push_back(u);
  }
  int max_len = -1;
  {
    const int u = bfs(0, g).first;
    max_len = bfs(u, g).second;
  }
  vector<int> ans(n + 1, 1);
  for (int i = 1; i <= max_len; i++) ans[i] = max(ans[i], 2);
  vector<int> depth(n), par(n, -1);
  dfs(0, -1, g, par, depth);
  vector<int> up(n, 0);
  dfs_up(0, -1, g, depth, up);
  vector<vector<int>> neigh_depths(n);
  for (int i = 0; i < n; i++) {
    for (int dest : g[i]) {
      if (dest != par[i]) neigh_depths[i].push_back(1 + depth[dest]);
    }
    if (i > 0) {
      assert(par[i] != -1 && up[i] != -1);
      neigh_depths[i].push_back(up[i]);
    }
  }
  for (auto &row : neigh_depths) {
    sort(row.begin(), row.end());
  }
  struct repeat {
    int value, cnt;
    bool operator<(const repeat &o) const { return value < o.value; }
  };
  vector<vector<repeat>> diff_neigh_depths(n);
  for (int i = 0; i < n; i++) {
    auto &row = diff_neigh_depths[i];
    for (int x : neigh_depths[i]) {
      if (row.empty() || row.back().value != x) {
        row.push_back(repeat{x, 1});
      } else {
        row.back().cnt++;
      }
    }
  }
  for (int i = 0; i < n; i++) {
    int low = int(neigh_depths[i].size());
    for (const auto &rep : diff_neigh_depths[i]) {
      const int high = low - rep.cnt;
      const int d = rep.value;
      assert(low >= high);
      if (high >= 2) {
        remax(ans[2 * d + 1], high + (low > high ? 1 : 0));
      }
      if (low >= 2) {
        remax(ans[2 * d], low);
        remax(ans[2 * d - 1], low);
      }
      low = high;
    }
  }
  vector<int> mem(n + 1, -1);
  int tmr = 0;
  vector<int> order(n);
  mt19937 rng;
  iota(order.begin(), order.end(), 0);
  shuffle(order.begin(), order.end(), rng);
  for (int i : order) {
    int max_son = -1;
    for (int dest : g[i]) {
      if (dest != par[i] && (max_son == -1 || depth[max_son] < depth[dest]))
        max_son = dest;
    }
    for (int dest : g[i]) {
      if (dest != max_son && dest != par[i]) {
        int ptr = 0, low = int(neigh_depths[dest].size());
        for (int d = 1; d <= depth[dest] - 1; d++) {
          while (diff_neigh_depths[dest][ptr].value < d) {
            low -= diff_neigh_depths[dest][ptr].cnt;
            ptr++;
          }
          int cur = low;
          cur += cnt_at_least(neigh_depths[i], d);
          cur -= 2;
          if (cur >= 2) remax(ans[2 * d], cur);
        }
        continue;
      }
      static vector<repeat> order;
      order.clear();
      const auto &cur_v = diff_neigh_depths[i];
      const auto &dest_v = diff_neigh_depths[dest];
      order.resize(cur_v.size() + dest_v.size());
      merge(cur_v.begin(), cur_v.end(), dest_v.begin(), dest_v.end(),
            order.begin());
      int low = int(neigh_depths[i].size()) + int(neigh_depths[dest].size());
      for (int i = 0; i < int(order.size()); i++) {
        const int d = order[i].value;
        if (low >= 4) ans[2 * d] = max(ans[2 * d], low - 2);
        low -= order[i].cnt;
      }
    }
  }
  for (int i = 0; i < n; i++) remax(ans[1], int(g[i].size()) + 1);
  for (int i = n - 2; i >= 1; i--) remax(ans[i], ans[i + 2]);
  for (int i = 1; i <= n; i++) cout << ans[i] << " \n"[i == n];
  cout.flush();
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  solve();
  return 0;
}