A tree is an undirected graph with exactly one simple path between each pair of vertices. We call a set of simple paths k-valid if each vertex of the tree belongs to no more than one of these paths (including endpoints) and each path consists of exactly k vertices.

You are given a tree with n vertices. For each k from 1 to n inclusive find what is the maximum possible size of a k-valid set of simple paths.

Input

The first line of the input contains a single integer n (2 ≤ n ≤ 100 000) — the number of vertices in the tree.

Then following n - 1 lines describe the tree, each of them contains two integers v, u (1 ≤ v, u ≤ n) — endpoints of the corresponding edge.

It is guaranteed, that the given graph is a tree. 

Output

Output n numbers, the i-th of which is the maximum possible number of paths in an i-valid set of paths.

Examples

Input

7
1 2
2 3
3 4
4 5
5 6
6 7


Output

7
3
2
1
1
1
1



Input

6
1 2
2 3
2 4
1 5
5 6


Output

6
2
2
1
1
0

Note

One way to achieve the optimal number of paths for the second sample is illustrated in the following picture:

<image>
//package com.company;

import java.io.*;
import java.util.*;

public class Main {
    static long TIME_START, TIME_END;

    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
//        Scanner sc = new Scanner(new FileInputStream("Test.in"));
        PrintWriter pw = new PrintWriter(System.out);
//        PrintWriter pw = new PrintWriter(new FileOutputStream("Test.in"));
//        PrintWriter pw = new PrintWriter(new FileOutputStream("Test.out"));

        Runtime runtime = Runtime.getRuntime();
        long usedMemoryBefore = runtime.totalMemory() - runtime.freeMemory();
        TIME_START = System.currentTimeMillis();
        Task t = new Task();
//        int sz = 100000;
//        int[][] edges = t.generateRandomTree(sz);
//        pw.println(sz);
//        for(int i = 0; i < edges.length; i++) {
//            pw.println((edges[i][0] + 1) + " " + (edges[i][1] + 1));
//        }
        t.solve(sc, pw);
        TIME_END = System.currentTimeMillis();
        long usedMemoryAfter = runtime.totalMemory() - runtime.freeMemory();
        pw.close();
        System.out.println("Memory increased:" + (usedMemoryAfter - usedMemoryBefore) / 1000000);
        System.out.println("Time used: " + (TIME_END - TIME_START) + ".");
    }

    public static class Task {

        public int[][] generateRandomTree(int n) {
            Random rnd = new Random();
            int root = 0;
            ArrayDeque<Integer> ard = new ArrayDeque<>();
            ard.push(root);
            int[][] edges = new int[n - 1][2];
            int idx = 0;
            while (idx < n - 1) {
                int deg = rnd.nextInt(Math.min(n - 1 - idx, 10)) + 1;
                int cut = ard.poll();
                for (int i = 0; i < deg; i++) {
                    idx++;
                    int nt = idx;
                    edges[idx - 1][0] = cut;
                    edges[idx - 1][1] = nt;
                    ard.push(nt);
                }
            }
            return edges;
        }

        static int[] firstChild;
        static int[] nextSibling;
        static int nextId;
        int[] answers;
        int[] max;
        int n;

        private int solveOne(int k) {
            if (answers[k] >= 0) return answers[k];
            int got = 0;
            for (int i = n - 1; i >= 0; --i) {
                int max1 = 0;
                int max2 = 0;
                int j = firstChild[i];
                while (j >= 0) {
                    if (max[j] > max1) {
                        max2 = max1;
                        max1 = max[j];
                    } else if (max[j] > max2) {
                        max2 = max[j];
                    }
                    j = nextSibling[j];
                }
                if (max1 + 1 + max2 >= k) {
                    ++got;
                    max[i] = 0;
                } else {
                    max[i] = max1 + 1;
                }
            }
            return answers[k] = got;
        }

        static class Vertex {
            List<Vertex> adj = new ArrayList<>();

            public int dfs(Vertex parent) {
                int id = nextId++;
                firstChild[id] = -1;
                for (Vertex v : adj)
                    if (v != parent) {
                        int cid = v.dfs(this);
                        nextSibling[cid] = firstChild[id];
                        firstChild[id] = cid;
                    }
                return id;
            }

        }


        public void solve(Scanner sc, PrintWriter pw) throws IOException {
            n = sc.nextInt();
            Vertex[] vs = new Vertex[n];
            for (int i = 0; i < n; ++i) vs[i] = new Vertex();
            for (int i = 0; i < n - 1; ++i) {
                Vertex a = vs[sc.nextInt() - 1];
                Vertex b = vs[sc.nextInt() - 1];
                a.adj.add(b);
                b.adj.add(a);
            }
            nextId = 0;
            firstChild = new int[n];
            nextSibling = new int[n];
            vs[0].dfs(null);

            answers = new int[n + 1];
            max = new int[n];
            Arrays.fill(answers, -1);


            int up = Math.max((int) Math.sqrt(n) * (31 - Integer.numberOfLeadingZeros(n)) / 10, 10);
            up = Math.min(up, n);
            int[] res = new int[n + 1];
            res[1] = n;
            for (int i = 2; i <= up; i++) {
                res[i] = solveOne(i);
            }
            res[n] = solveOne(n);
            int curFilled = up;
            int nextQ = n;
            while (res[curFilled] != res[n]) {
                int tr = res[curFilled];
                int lo = curFilled;
                int hi;
                if (nextQ == -1) {
                    hi = Math.min(n, lo + 500);
                } else {
                    hi = nextQ;
                    nextQ = -1;
                }
                while (lo < hi) {
                    int mid = (lo + hi) / 2;
                    int resMid = solveOne(mid);
                    if (resMid < tr - 1) {
                        nextQ = mid;
                    }
                    if (resMid == tr) {
                        lo = mid + 1;
                    } else {
                        hi = mid;
                    }
                }
                for (int i = curFilled + 1; i < lo; i++) {
                    res[i] = tr;
                }
                curFilled = lo;
                res[curFilled] = solveOne(curFilled);
            }
            for (int i = curFilled; i <= n; i++) {
                res[i] = res[n];
            }
            for (int i = 1; i <= n; i++) {
                pw.println(res[i]);
            }
        }
    }

    static class Scanner {
        StringTokenizer st;
        BufferedReader br;

        public Scanner(InputStream s) {
            br = new BufferedReader(new InputStreamReader(s));
        }

        public Scanner(FileReader s) throws FileNotFoundException {
            br = new BufferedReader(s);
        }

        public String next() throws IOException {
            while (st == null || !st.hasMoreTokens())
                st = new StringTokenizer(br.readLine());
            return st.nextToken();
        }

        public int nextInt() throws IOException {
            return Integer.parseInt(next());
        }

        public long nextLong() throws IOException {
            return Long.parseLong(next());
        }

        public String nextLine() throws IOException {
            return br.readLine();
        }

        public double nextDouble() throws IOException {
            return Double.parseDouble(next());
        }

        public boolean ready() throws IOException {
            return br.ready();
        }
    }
}