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:
// practice with rainboy
import java.io.*;
import java.util.*;

public class CF1266F extends PrintWriter {
	CF1266F() { super(System.out, true); }
	Scanner sc = new Scanner(System.in);
	public static void main(String[] $) {
		CF1266F o = new CF1266F(); o.main(); o.flush();
	}

	int[] oo, oj; int __ = 1;
	int link(int o, int j) {
		oo[__] = o; oj[__] = j;
		return __++;
	}
	int[] ae, dd;
	int[] tt; int[][] dd_, kk_; int[] mm_;
	int[] ans;
	void init(int n, int m) {
		oo = new int[1 + m * 2]; oj = new int[1 + m * 2];
		ae = new int[n]; dd = new int[n];
		tt = new int[n]; dd_ = new int[n][]; kk_ = new int[n][]; mm_ = new int[n];
		ans = new int[n * 2 + 4];
	}
	void dfs1(int p, int i) {
		int d = 0;
		for (int o = ae[i]; o != 0; o = oo[o]) {
			int j = oj[o];
			if (j != p) {
				dfs1(i, j);
				d = Math.max(d, dd[j]);
			}
		}
		dd[i] = d + 1;
	}
	void dfs2(int p, int i, int d_) {
		int j1 = -1, j2 = -1;
		for (int o = ae[i]; o != 0; o = oo[o]) {
			int j = oj[o];
			if (j != p) {
				if (j1 == -1 || dd[j1] < dd[j]) {
					j2 = j1; j1 = j;
				} else if (j2 == -1 || dd[j2] < dd[j])
					j2 = j;
			}
		}
		int d1 = Math.max(d_, j1 == -1 ? 0 : dd[j1]) + 1;
		int d2 = Math.max(d_, j2 == -1 ? 0 : dd[j2]) + 1;
		for (int o = ae[i]; o != 0; o = oo[o]) {
			int j = oj[o];
			if (j != p)
				dfs2(i, j, j == j1 ? d2 : d1);
		}
		int m = 0;
		for (int o = ae[i]; o != 0; o = oo[o]) {
			int j = oj[o];
			if (j != p) {
				tt[m++] = dd[j];
			}
		}
		if (p != -1)
			tt[m++] = d_;
		Arrays.sort(tt, 0, m);
		int m_ = 1;
		for (int h = 1; h < m; h++)
			if (tt[h] != tt[h - 1])
				m_++;
		dd_[i] = new int[m_];
		kk_[i] = new int[m_];
		mm_[i] = m_; m_ = 0;
		for (int h = 0, h_; h < m; h = h_) {
			h_ = h + 1;
			while (h_ < m && tt[h_] == tt[h])
				h_++;
			dd_[i][m_] = tt[h];
			kk_[i][m_] = h_ - h;
			m_++;
		}
		for (int h = m_ - 2; h >= 0; h--)
			kk_[i][h] += kk_[i][h + 1];
		for (int h = 0; h < m_; h++) {
			int l = dd_[i][h] * 2;
			ans[l] = Math.max(ans[l], kk_[i][h]);
			ans[l - 1] = Math.max(ans[l - 1], kk_[i][h]);
			if (h + 1 < m_)
				ans[l + 1] = Math.max(ans[l + 1], kk_[i][h + 1] + 1);
		}
	}
	void solve(int[] d1, int[] k1, int m1, int[] d2, int[] k2, int m2) {
		for (int i = 0, j = 0; i < m1 && j < m2; ) {
			int l = Math.min(d1[i], d2[j]) * 2;
			int k = k1[i] + k2[j] - 2;
			ans[l] = Math.max(ans[l], k);
			if (d1[i] < d2[j])
				i++;
			else if (d1[i] > d2[j])
				j++;
			else {
				i++; j++;
			}
		}
	}
	void dfs(int p, int i) {
		if (p != -1)
			solve(dd_[p], kk_[p], mm_[p], dd_[i], kk_[i], mm_[i]);
		for (int o = ae[i]; o != 0; o = oo[o]) {
			int j = oj[o];
			if (j != p)
				dfs(i, j);
		}
	}
	void main() {
		int n = sc.nextInt();
		init(n, n - 1);
		for (int h = 0; h < n - 1; h++) {
			int i = sc.nextInt() - 1;
			int j = sc.nextInt() - 1;
			ae[i] = link(ae[i], j); dd[i]++;
			ae[j] = link(ae[j], i); dd[j]++;
		}
		ans[n * 2 + 2] = ans[n * 2 + 3] = 1;
		for (int i = 0; i < n; i++)
			ans[1] = Math.max(ans[1], dd[i] + 1);
		Arrays.fill(dd, 0);
		Random rand = new Random();
		int s = rand.nextInt(n);
		dfs1(-1, s);
		dfs2(-1, s, -1);
		dfs(-1, s);
		for (int l = n * 2 + 1; l >= 1; l--)
			ans[l] = Math.max(ans[l], ans[l + 2]);
		for (int l = 1; l <= n; l++)
			print(ans[l] + " ");
		println();
	}
}