The Resistance is trying to take control over as many planets of a particular solar system as possible. Princess Heidi is in charge of the fleet, and she must send ships to some planets in order to maximize the number of controlled planets.

The Galaxy contains N planets, connected by bidirectional hyperspace tunnels in such a way that there is a unique path between every pair of the planets.

A planet is controlled by the Resistance if there is a Resistance ship in its orbit, or if the planet lies on the shortest path between some two planets that have Resistance ships in their orbits.

Heidi has not yet made up her mind as to how many ships to use. Therefore, she is asking you to compute, for every K = 1, 2, 3, ..., N, the maximum number of planets that can be controlled with a fleet consisting of K ships.

Input

The first line of the input contains an integer N (1 ≤ N ≤ 105) – the number of planets in the galaxy.

The next N - 1 lines describe the hyperspace tunnels between the planets. Each of the N - 1 lines contains two space-separated integers u and v (1 ≤ u, v ≤ N) indicating that there is a bidirectional hyperspace tunnel between the planets u and v. It is guaranteed that every two planets are connected by a path of tunnels, and that each tunnel connects a different pair of planets.

Output

On a single line, print N space-separated integers. The K-th number should correspond to the maximum number of planets that can be controlled by the Resistance using a fleet of K ships.

Examples

Input

3
1 2
2 3


Output

1 3 3 

Input

4
1 2
3 2
4 2


Output

1 3 4 4 

Note

Consider the first example. If K = 1, then Heidi can only send one ship to some planet and control it. However, for K ≥ 2, sending ships to planets 1 and 3 will allow the Resistance to control all planets.
/*
If you want to aim high, aim high
Don't let that studying and grades consume you
Just live life young
******************************
What do you think? What do you think?
1st on Billboard, what do you think of it
Next is a Grammy, what do you think of it
However you think, I’m sorry, but shit, I have no fcking interest
*******************************
I'm standing on top of my Monopoly board
That means I'm on top of my game and it don't stop
til my hip don't hop anymore
https://www.a2oj.com/Ladder16.html
*******************************
Shining through the city with a little funk and soul
*******************************
300iq as writer = Sad!
*/
import java.util.*;
import java.io.*;
import java.math.*;

   public class x958B2
   {
      static int N;
      static ArrayDeque<Integer>[] edges;
      public static void main(String hi[]) throws Exception
      {
         BufferedReader infile = new BufferedReader(new InputStreamReader(System.in));
         StringTokenizer st = new StringTokenizer(infile.readLine());
         N = Integer.parseInt(st.nextToken());
         if(N < 3)
         {
            int[] lol = {1, 2};
            for(int i=0; i < N; i++)
               System.out.print(lol[i]+" ");
            return;
         }
         edges = new ArrayDeque[N+1];
         for(int i=1; i <= N; i++)
            edges[i] = new ArrayDeque<Integer>();
         for(int i=0; i < N-1; i++)
         {
            st = new StringTokenizer(infile.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            edges[a].add(b);  edges[b].add(a);
         }
         depth = new int[N+1];
         path = new int[N+1];
         Arrays.fill(depth, -1);
         int first = farthest(1);
         int second = farthest(first);
         int root = second;
         dfs(root, 0);
         ArrayList<Integer> ls = getPath(first, second);
         PriorityQueue<Integer> pq = new PriorityQueue<Integer>( (x,y) -> {
            return depth[y]-depth[x];
         });
         int[] res = new int[N+1];
         res[1] = 1;   res[2] = ls.size();
         for(int v=1; v <= N; v++)
            pq.add(v);
         boolean[] taken = new boolean[N+1];
         for(int v: ls)
            taken[v] = true;
         int cnt = ls.size();
         int dex = 3;
         while(pq.size() > 0)
         {
            int curr = pq.poll();
            if(taken[curr])
               continue;
            int head = curr;
            while(head != 0)
            {
               taken[head] = true;
               head = path[head];
               cnt++;
            }
            res[dex++] = cnt;
         }
         for(; dex <= N; dex++)
            res[dex] = cnt;
         StringBuilder sb = new StringBuilder();
         for(int i=1; i <= N; i++)
            sb.append(res[i]+" ");
         System.out.println(sb);
      }
      public static ArrayList<Integer> getPath(int a, int b)
      {
         int[] par = new int[N+1];
         Arrays.fill(par, -1);
         par[b] = 0;
         ArrayDeque<Integer> q = new ArrayDeque<Integer>();
         q.add(b);
         while(q.size() > 0)
         {
            int curr = q.poll();
            for(int next: edges[curr])
               if(par[next] == -1)
               {
                  par[next] = curr;
                  q.add(next);
               }
         }
         ArrayList<Integer> ls = new ArrayList<Integer>();
         int head = a;
         while(head != b)
         {
            ls.add(head);
            head = par[head];
         }
         ls.add(b);
         return ls;
      }
      public static int farthest(int root)
      {
         int[] dist = new int[N+1];
         Arrays.fill(dist, Integer.MAX_VALUE/2);
         dist[root] = 0;
         ArrayDeque<Integer> q = new ArrayDeque<Integer>();
         q.add(root);
         int farthest = root;
         while(q.size() > 0)
         {
            int curr = q.poll();
            for(int next: edges[curr])
               if(dist[next] == Integer.MAX_VALUE/2)
               {
                  dist[next] = dist[curr]+1;
                  farthest = next;
                  q.add(next);
               }
         }
         return farthest;
      }
      static int[] depth;
      static int[] path;
      public static void dfs(int curr, int par)
      {
         for(int next: edges[curr])
            if(next != par)
            {
               dfs(next, curr);
               if(depth[curr] == -1 || depth[curr] < depth[next]+1)
               {
                  depth[curr] = depth[next]+1;
                  path[curr] = next;
               }
            }
         if(depth[curr] == -1)
            depth[curr] = 0;
      }
   }