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;
int ri() {
  int x;
  if (scanf(" %d", &x) == EOF) return -1;
  return x;
}
long long int rl() {
  long long int x;
  if (cin >> x) return x;
  return -1;
}
string rs() {
  string s;
  if (cin >> s) return s;
  return "";
}
void maximize(int& ret, int v) {
  if (ret < v) ret = v;
}
struct Tree {
  int n;
  vector<vector<int>> edges;
  vector<unordered_set<int>> edgeSet;
  vector<int> depth, branchParent;
  vector<vector<int>> lengths;
  int diameter;
  Tree(int n)
      : n(n),
        edges(n),
        edgeSet(n),
        branchParent(n, -1),
        depth(n, -1),
        lengths(n) {}
  map<int, int> evenStar;
  map<int, int> evenBow;
  map<int, int> oddStar;
  void computeEvenBow() {
    vector<pair<int, int>> allLengths;
    for (int i = 0; i < n; ++i)
      for (auto j : lengths[i]) allLengths.push_back({j, i});
    sort(allLengths.begin(), allLengths.end(),
         [](pair<int, int> a, pair<int, int> b) {
           if (a.first != b.first) return a.first > b.first;
           return a.second < b.second;
         });
    vector<int> count(n, 0);
    vector<list<int>> buckets(n);
    vector<list<int>::iterator> pointers;
    for (int u = 0; u < n; ++u) {
      pointers.push_back(buckets[0].insert(buckets[0].begin(), u));
    }
    int maxSum = 0;
    for (auto [L, u] : allLengths) {
      int& c = count[u];
      buckets[c].erase(pointers[u]);
      ++c;
      pointers[u] = buckets[c].insert(buckets[c].begin(), u);
      int r = maxSum + 1 - c;
      if (r >= 0 && r < buckets.size()) {
        const list<int>& B = buckets[r];
        const vector<int>& E = edges[u];
        if (B.size() < E.size()) {
          for (auto v : B)
            if (edgeSet[u].count(v)) {
              maxSum++;
              if (maxSum >= 5) evenBow[2 * L] = maxSum - 2;
              break;
            }
        } else {
          for (auto v : E)
            if (count[v] == r) {
              maxSum++;
              if (maxSum >= 5) evenBow[2 * L] = maxSum - 2;
              break;
            }
        }
      }
    }
  }
  void computeCandidates() {
    computeEvenBow();
    for (int i = 0; i < n; ++i)
      sort(lengths[i].begin(), lengths[i].end(), greater<int>());
    for (int i = 0; i < n; ++i)
      if (lengths[i].size() >= 3) {
        for (int j = 2; j < lengths[i].size(); j++) {
          int least = lengths[i][j];
          int higher = lengths[i][j - 1];
          maximize(evenStar[2 * least], j + 1);
          if (least == higher)
            maximize(oddStar[2 * least - 1], j + 1);
          else
            maximize(oddStar[2 * least + 1], j + 1);
        }
      }
  }
  void printAnswers() {
    vector<int> ret = vector<int>(n, -1);
    int lastEven = 2, lastOdd = 2;
    for (int i = n; i >= 1; --i) {
      if (i & 1) {
        ret[i - 1] = bestOdd(i, lastOdd);
      } else {
        ret[i - 1] = bestEven(i, lastEven);
      }
    }
    for (auto x : ret) cout << x << " ";
    cout << endl;
  }
  int bestOdd(int N, int& last) {
    assert(N % 2 == 1);
    if (N > diameter) return 1;
    if (N == 1) return best1();
    auto it = oddStar.find(N);
    if (it != oddStar.end()) last = max(last, it->second);
    return last;
  }
  int bestEven(int N, int& last) {
    assert(N % 2 == 0);
    if (N > diameter) return 1;
    auto it = evenStar.find(N);
    if (it != evenStar.end()) last = max(last, it->second);
    it = evenBow.find(N);
    if (it != evenBow.end()) last = max(last, it->second);
    return last;
  }
  int best1() {
    int ret = 1;
    for (int i = 0; i < n; ++i) ret = max(ret, 1 + (int)edges[i].size());
    return ret;
  }
  void readInput() {
    for (int i = 0; i < (n - 1); ++i) {
      int u = ri() - 1;
      int v = ri() - 1;
      edges[u].push_back(v);
      edges[v].push_back(u);
      edgeSet[u].insert(v);
      edgeSet[v].insert(u);
    }
  }
  void prepare() {
    dfs(0, -1);
    fillupUpLengths(0, -1, {-1, 0}, {-1, 0}, -100);
    computeDiameter();
    for (int u = 0; u < n; ++u)
      for (int j = 0; j < edges[u].size(); ++j) {
        int v = edges[u][j];
      }
  }
  void computeDiameter() {
    diameter = 0;
    for (int i = 0; i < n; ++i)
      for (auto x : lengths[i]) diameter = max(diameter, x);
  }
  int dfs(int u, int parent) {
    int maxLen = 0;
    depth[u] = (u == 0) ? 0 : (1 + depth[parent]);
    branchParent[u] = (parent == 0) ? u : branchParent[parent];
    lengths[u] = vector<int>(edges[u].size(), -1);
    for (int i = 0; i < edges[u].size(); ++i) {
      int v = edges[u][i];
      if (v == parent) continue;
      int vLen = dfs(v, u);
      lengths[u][i] = 1 + vLen;
      maxLen = max(maxLen, 1 + vLen);
    }
    return maxLen;
  }
  void fillupUpLengths(int u, int parent, pair<int, int> b1, pair<int, int> b2,
                       int parentBest) {
    int R = -1;
    for (int i = 0; i < edges[u].size(); ++i)
      if (edges[u][i] == parent) {
        int& L = lengths[u][i];
        if (b1.first == u)
          L = b2.second;
        else
          L = b1.second;
        L = max(1 + L, 1 + parentBest);
        R = L;
        break;
      }
    pair<int, int> c1 = {-1, 0}, c2 = {-1, 0};
    for (int i = 0; i < edges[u].size(); ++i)
      if (edges[u][i] != parent) {
        int v = edges[u][i], l = lengths[u][i];
        if (l >= c1.second)
          c2 = c1, c1 = {v, l};
        else if (l >= c2.second)
          c2 = {v, l};
      }
    for (auto v : edges[u])
      if (v != parent) {
        fillupUpLengths(v, u, c1, c2, R);
      }
  }
};
struct SingleCase {
  int n;
  bool solveCase() {
    n = ri();
    if (n < 0) return false;
    Tree tree(n);
    tree.readInput();
    tree.prepare();
    tree.computeCandidates();
    tree.printAnswers();
    return true;
  }
};
int main() {
  while (SingleCase().solveCase()) {
  };
  return 0;
}