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;
vector<int> nei[1000000];
int DP[1000000];
int UP[1000000];
int n;
bool visited[1000000];
int p[1000000];
vector<int> child[1000000];
int answer[1000000];
void DFS(int node) {
  visited[node] = true;
  for (auto a : nei[node]) {
    if (!visited[a]) {
      DFS(a);
      p[a] = node;
      child[node].push_back(a);
    }
  }
}
void calc(int node) {
  DP[node] = 0;
  for (auto a : child[node]) {
    calc(a);
    DP[node] = max(DP[node], DP[a] + 1);
  }
}
void calc2(int node) {
  if (child[node].size() == 0) return;
  priority_queue<int> pq;
  for (auto a : child[node]) {
    pq.push(-DP[a]);
    if (pq.size() > 2) pq.pop();
  }
  int second, best;
  if (pq.size() == 2) {
    second = -pq.top();
    pq.pop();
    best = -pq.top();
    pq.pop();
  } else {
    best = -pq.top();
    pq.pop();
    second = -100000000;
  }
  for (auto a : child[node]) {
    UP[a] = max(UP[a], UP[node] + 1);
    if (DP[a] != best) {
      UP[a] = max(UP[a], best + 2);
    } else {
      UP[a] = max(UP[a], second + 2);
    }
  }
  for (auto a : child[node]) {
    calc2(a);
  }
}
vector<pair<int, int> > operations;
int counting[1000000];
vector<int> BT;
int L[1000000];
int R[1000000];
int pos[1000000];
int ST[4000000];
int lazy[4000000];
vector<pair<int, pair<int, int> > > op;
void build(int a, int b, int node) {
  ST[node] = 0;
  lazy[node] = 0;
  if (a == b) return;
  int mid = (a + b) / 2;
  build(a, mid, 2 * node);
  build(mid + 1, b, 2 * node + 1);
}
void propag(int a, int b, int node) {
  ST[node] += lazy[node];
  if (a != b) {
    lazy[2 * node] += lazy[node];
    lazy[2 * node + 1] += lazy[node];
  }
  lazy[node] = 0;
}
void update(int a, int b, int node, int x, int y, int val) {
  propag(a, b, node);
  if (y < a || b < x) return;
  if (x <= a && b <= y) {
    lazy[node] += val;
    propag(a, b, node);
    return;
  }
  int mid = (a + b) / 2;
  update(a, mid, 2 * node, x, y, val);
  update(mid + 1, b, 2 * node + 1, x, y, val);
  ST[node] = max(ST[2 * node], ST[2 * node + 1]);
}
int query() {
  propag(0, n - 1, 1);
  return ST[1];
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cin >> n;
  for (int i = 0; i < n - 1; i++) {
    int x, y;
    cin >> x >> y;
    x--;
    y--;
    nei[x].push_back(y);
    nei[y].push_back(x);
  }
  for (int i = 0; i < n; i++) {
    visited[i] = false;
  }
  DFS(0);
  calc(0);
  for (int i = 0; i < n; i++) {
    answer[i] = 1;
    UP[i] = 0;
  }
  UP[0] = 0;
  calc2(0);
  for (int i = 0; i < n; i++) counting[i] = 0;
  for (int i = 0; i < n; i++) {
    for (auto a : child[i]) {
      operations.push_back(pair<int, int>(DP[a] + 1, i));
    }
    if (i != 0) operations.push_back(pair<int, int>(UP[i], i));
  }
  sort(operations.begin(), operations.end());
  reverse(operations.begin(), operations.end());
  int cluster1[n];
  for (int i = 0; i < n; i++) cluster1[i] = 0;
  int M = 0;
  int best[n];
  for (int i = 0; i < n; i++) best[i] = 100000000;
  for (int i = 0; i < operations.size(); i++) {
    counting[operations[i].second]++;
    if (best[operations[i].second] > operations[i].first) {
      answer[2 * operations[i].first + 1] = max(
          answer[2 * operations[i].first + 1], counting[operations[i].second]);
    }
    best[operations[i].second] = operations[i].first;
    M = max(M, counting[operations[i].second]);
    cluster1[operations[i].first] = max(cluster1[operations[i].first], M);
  }
  for (int i = n - 2; i > -1; i--) {
    cluster1[i] = max(cluster1[i], cluster1[i + 1]);
  }
  for (int i = 0; i < n; i++) {
    answer[2 * i] = max(answer[2 * i], cluster1[i]);
    answer[2 * i - 1] = max(answer[2 * i - 1], cluster1[i]);
  }
  for (int i = 1; i < n; i++) {
    if (cluster1[i] > 0) answer[i] = max(answer[i], 2);
  }
  queue<int> q;
  q.push(0);
  BT.push_back(0);
  pos[0] = 0;
  while (!q.empty()) {
    int u = q.front();
    q.pop();
    L[u] = BT.size();
    for (auto a : child[u]) {
      pos[a] = BT.size();
      BT.push_back(a);
      q.push(a);
    }
    R[u] = BT.size() - 1;
  }
  build(0, n - 1, 1);
  for (int i = 0; i < n; i++) {
    for (auto a : child[i]) {
      op.push_back(
          pair<int, pair<int, int> >(DP[a] + 1, pair<int, int>(i, -a)));
    }
    if (i != 0)
      op.push_back(pair<int, pair<int, int> >(UP[i], pair<int, int>(i, 1)));
  }
  sort(op.begin(), op.end());
  reverse(op.begin(), op.end());
  int cluster2[n];
  for (int i = 0; i < n; i++) cluster2[i] = 0;
  for (int i = 0; i < op.size(); i++) {
    if (op[i].second.second <= 0) {
      int v = op[i].second.first;
      int a = -op[i].second.second;
      update(0, n - 1, 1, L[v], R[v], 1);
      update(0, n - 1, 1, pos[a], pos[a], -1);
      update(0, n - 1, 1, pos[v], pos[v], 1);
    } else {
      int v = op[i].second.first;
      if (child[v].size() > 0) update(0, n - 1, 1, L[v], R[v], 1);
    }
    cluster2[op[i].first] = query();
  }
  for (int i = n - 2; i > -1; i--)
    cluster2[i] = max(cluster2[i], cluster2[i + 1]);
  for (int i = 0; i < n; i++) {
    answer[2 * i] = max(answer[2 * i], cluster2[i]);
  }
  for (int i = 0; i < n; i++) {
    answer[1] = max(answer[1], (int)nei[i].size() + 1);
  }
  for (int i = 1; i < n; i++) cout << answer[i] << " ";
  cout << 1 << endl;
  return 0;
}