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;
inline int read() {
  int f = 1, x = 0;
  char ch;
  do {
    ch = getchar();
    if (ch == '-') f = -1;
  } while (ch < '0' || ch > '9');
  do {
    x = x * 10 + ch - '0';
    ch = getchar();
  } while (ch >= '0' && ch <= '9');
  return f * x;
}
const int N = 5e5;
int n;
struct Edge {
  int to, next;
} edge[(N << 1) + 1];
int start[N + 1], tot;
int d[N + 1], maxdis[N + 1];
vector<int> dis[N + 1], alldis[N + 1];
int ans[(N << 1) + 1];
inline void addedge(int u, int v) {
  edge[++tot] = Edge{v, start[u]};
  start[u] = tot;
  d[u]++;
  edge[++tot] = Edge{u, start[v]};
  start[v] = tot;
  d[v]++;
  return;
}
inline bool compare(int x, int y) { return x > y; }
inline void dfs1(int u, int fa) {
  for (int i = start[u]; i; i = edge[i].next) {
    int v = edge[i].to;
    if (v != fa) {
      dfs1(v, u);
      dis[u].push_back(maxdis[v] + 1);
      maxdis[u] = max(maxdis[u], maxdis[v] + 1);
    }
  }
  alldis[u] = dis[u];
  return;
}
inline void dfs2(int u, int fa) {
  if (fa) {
    if (alldis[fa][0] == maxdis[u] + 1) {
      if (alldis[fa].size() > 1)
        alldis[u].push_back(alldis[fa][1] + 1);
      else if (fa == 1)
        alldis[u].push_back(1);
    } else {
      alldis[u].push_back(alldis[fa][0] + 1);
    }
  }
  sort(alldis[u].begin(), alldis[u].end(), compare);
  for (int i = 0; i < alldis[u].size(); i++) {
    int diss = alldis[u][i];
    ans[diss * 2] = max(ans[diss * 2], i + 1);
    ans[diss * 2 - 1] = max(ans[diss * 2 - 1], i + 1);
    if (i != 0 && alldis[u][i - 1] > diss)
      ans[diss * 2 + 1] = max(ans[diss * 2 + 1], i + 1);
  }
  unordered_map<int, int> p;
  vector<int> di;
  for (int i = 0; i < alldis[u].size(); i++) p[alldis[u][i]]++;
  for (int i = start[u]; i; i = edge[i].next) {
    int v = edge[i].to;
    if (v != fa) {
      p[maxdis[v] + 1]--;
      for (int j = 0; j < dis[v].size(); j++) p[dis[v][j]]++;
      for (unordered_map<int, int>::iterator it = p.begin(); it != p.end();
           it++)
        if ((*it).second) di.push_back((*it).first);
      sort(di.begin(), di.end());
      for (int j = di.size() - 1, k = 0; j >= 0; j--) {
        int diss = di[j];
        k += p[diss];
        ans[diss * 2] = max(ans[diss * 2], k);
      }
      for (int j = 0; j < dis[v].size(); j++) p[dis[v][j]]--;
      p[maxdis[v] + 1]++;
      di.clear();
      dfs2(v, u);
    }
  }
  return;
}
int main() {
  n = read();
  for (int i = 1; i < n; i++) addedge(read(), read());
  dfs1(1, 0);
  dfs2(1, 0);
  for (int i = 2 * n - 2; i >= 1; i--) ans[i] = max(max(ans[i], ans[i + 2]), 1);
  for (int i = 1; i <= n; i++) ans[1] = max(ans[1], d[i] + 1);
  for (int i = 1; i <= n; i++) printf("%d ", ans[i]);
  printf("\n");
  return 0;
}