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 JAVA):

Solution:
import java.util.*;
    import java.io.*;
    public class F{
        static PrintWriter out;
        static InputReader in;
        public static void main(String args[]){
            out = new PrintWriter(System.out);
            in = new InputReader();
            new F();
            out.flush(); out.close();
        }   
        F(){
            solve();
        }
        class pair{
            int F, S;
            pair(int a, int b){
                F = a; S = b;
            }
            public String toString(){
                return "(" + F + "-" + S + ")";
            }
        }
        pair base;
        final int max = 500010;
        int n;
        int ja[][], from[], to[], c[], d[], bd[], parent[];
        ArrayList<pair> al[] = new ArrayList[max];
        int ans[] = new int[2 * max], ans2[] = new int[2 * max];
        void dfs(int u, int pa){
            for(int v : ja[u]){
                if(v == pa)continue;
                dfs(v, u);
                parent[v] = u;
                d[u] = Math.max(d[v] + 1, d[u]);
            }
        }
        void bdfs(int u, int pa){
            int max1 = bd[u], n1 = pa, max2 = 0, n2 = 0;
            for(int v : ja[u]){
                if(v == pa)continue;
                int val = d[v] + 1;
                if(val > max1){
                    max2 = max1; n2 = n1;
                    max1 = val; n1 = v;
                }else if(val > max2){
                    max2 = val; n2 = v;
                }
            }
            for(int v : ja[u]){
                if(v == pa)continue;
                bd[v] = (v == n1 ? max2 : max1) + 1;
                bdfs(v, u);
            }
        }
        ArrayList<pair> merge(ArrayList<pair> a){
            ArrayList<pair> m = new ArrayList<>();
            for(int i = 0; i < a.size(); i++){
                pair p = a.get(i);
                if(m.size() == 0)m.add(p);
                else{
                    pair p1 = m.get(m.size() - 1);
                    if(p1.F == p.F)p1.S++;
                    else m.add(p);
                }
            }
            m.add(base);
            a.clear();
            return m;
        }
        void solve(){
            base = new pair(0, 0);
            Arrays.fill(ans, 1);
            n = in.nextInt();
            ja = new int[n + 1][]; from = new int[n - 1]; to = new int[n - 1]; c = new int[n + 1];
            for(int i = 0; i < n - 1; i++){
                int u = in.nextInt(), v = in.nextInt();
                from[i] = u; to[i] = v; c[u]++; c[v]++;
            }
            for(int i = 1; i <= n; i++){
                ja[i] = new int[c[i]]; c[i] = 0;
            }
            for(int i = 0; i < n - 1; i++){
                ja[from[i]][c[from[i]]++] = to[i];
                ja[to[i]][c[to[i]]++] = from[i];
            }
            d = new int[n + 1]; bd = new int[n + 1]; parent = new int[n + 1];
            dfs(1, 0);
            bdfs(1, 0);
            for(int nd = 1; nd <= n; nd++){
                int u = nd;
                al[u] = new ArrayList<>();
                for(int v : ja[u]){
                    if(v == parent[u])al[u].add(new pair(bd[u], 1));
                    else{
                        al[u].add(new pair(d[v] + 1, 1));
                    }
                }
                Collections.sort(al[u], (A, B) -> B.F - A.F);
                al[u] = merge(al[u]);
            }
            for(int nd = 1; nd <= n; nd++){
                int u = nd;
                //point
                int tot = 0;
                for(int i = 1; i < al[u].size(); i++){
                    pair p1 = al[u].get(i), p = al[u].get(i - 1);
                    tot += p.S;
                    int key = 2 * p.F;
                    ans[key] = Math.max(ans[key], tot);
                    key = 2 * p1.F + 1; 
                    ans[key] = Math.max(ans[key], tot + 1);
                }
                //edge
                for(int v : ja[u]){
                    if(v == parent[u])continue;
                    int szu = al[u].size(), szv = al[v].size(), ptu = 0, ptv = 0;
                    boolean cu = false, cv = false;
                    tot = 0; int pr = 0;
                    while(ptu < szu && ptv < szv){
                        pair pu = al[u].get(ptu), pv = al[v].get(ptv);
                        int now = 0, vu = pu.F == d[v] + 1 ? pu.S - 1 : pu.S, vv = pv.F == bd[v] ? pv.S - 1 : pv.S, value = 0;
                        boolean can = cu & cv;
                        if(pu.F > pv.F){
                            now = pu.F; value = vu;
                            cu = true; ptu++;
                        }else if(pu.F < pv.F){
                            now = pv.F; value = vv;
                            cv = true; ptv++;
                        }else{
                            now = pu.F; value = vu + vv;
                            cu = cv = true; ptu++; ptv++;
                        }
                        if(can){
                            int key = 2 * pr;
                            ans2[key] = Math.max(ans2[key], tot);
                        }
                        tot += value; pr = now;
                    }
                }
            }
            for(int i = n; i >= 2; i--){
                ans[i - 1] = Math.max(ans[i - 1], ans[i]);
                ans2[i - 2] = Math.max(ans2[i - 2], ans2[i]);
            }
            for(int i = 1; i <= n; i++){
                out.print(Math.max(ans[i], ans2[i]) + " ");
            }
        }
        public static class InputReader{
            BufferedReader br;
            StringTokenizer st;
            InputReader(){
                br = new BufferedReader(new InputStreamReader(System.in));
            }
            public int nextInt(){
                return Integer.parseInt(next());
            }
            public long nextLong(){
                return Long.parseLong(next());
            }
            public double nextDouble(){
                return Double.parseDouble(next());
            }
            public String next(){
                while(st == null || !st.hasMoreTokens()){
                    try{
                        st = new StringTokenizer(br.readLine());
                    }catch(IOException e){}
                }
                return st.nextToken();
            }
        }
    }
//print the result