There is one apple tree in Arkady's garden. It can be represented as a set of junctions connected with branches so that there is only one way to reach any junctions from any other one using branches. The junctions are enumerated from $1$ to $n$, the junction $1$ is called the root.

A subtree of a junction $v$ is a set of junctions $u$ such that the path from $u$ to the root must pass through $v$. Note that $v$ itself is included in a subtree of $v$.

A leaf is such a junction that its subtree contains exactly one junction.

The New Year is coming, so Arkady wants to decorate the tree. He will put a light bulb of some color on each leaf junction and then count the number happy junctions. A happy junction is such a junction $t$ that all light bulbs in the subtree of $t$ have different colors.

Arkady is interested in the following question: for each $k$ from $1$ to $n$, what is the minimum number of different colors needed to make the number of happy junctions be greater than or equal to $k$?


-----Input-----

The first line contains a single integer $n$ ($1 \le n \le 10^5$) — the number of junctions in the tree.

The second line contains $n - 1$ integers $p_2$, $p_3$, ..., $p_n$ ($1 \le p_i < i$), where $p_i$ means there is a branch between junctions $i$ and $p_i$. It is guaranteed that this set of branches forms a tree.


-----Output-----

Output $n$ integers. The $i$-th of them should be the minimum number of colors needed to make the number of happy junctions be at least $i$.


-----Examples-----
Input
3
1 1

Output
1 1 2 

Input
5
1 1 3 3

Output
1 1 1 2 3 



-----Note-----

In the first example for $k = 1$ and $k = 2$ we can use only one color: the junctions $2$ and $3$ will be happy. For $k = 3$ you have to put the bulbs of different colors to make all the junctions happy.

In the second example for $k = 4$ you can, for example, put the bulbs of color $1$ in junctions $2$ and $4$, and a bulb of color $2$ into junction $5$. The happy junctions are the ones with indices $2$, $3$, $4$ and $5$ then.

Difficulty: interview

Starter code:

Solutions:

# encoding:UTF-8
# Filename:Base.py

import sys
import random
import copy
from itertools import permutations, combinations
from math import sqrt, fabs, ceil
from collections import namedtuple

# ------Util Const--------

in_file_path = "input.txt"
output_file_path = "output.txt"

SUBMIT = True


def get_array(x, initial=None):
    dimension = len(x)
    if dimension == 1:
        return [copy.deepcopy(initial) for _ in range(x[0])]
    else:
        return [get_array(x[1:], initial) for _ in range(x[0])]


def read_num(fin, num_type=int):
    tmp_list = [num_type(x) for x in fin.readline().strip().split()]
    if len(tmp_list) == 1:
        return tmp_list[0]
    else:
        return tuple(tmp_list)

def read_num_list(fin, num_type=int):
    return [num_type(x) for x in fin.readline().strip().split()]


# def solve(fin):
#     n = read_num(fin)
#     ans_set = None
#     for i in range(n):
#         tmp_list = read_num_list(fin)
#         if ans_set == None:
#             ans_set = set(tmp_list[1:])
#         else:
#             ans_set &= set(tmp_list[1:])
#
#     print(' '.join([str(x) for x in ans_set]))

# def solve(fin):
#     n, m = read_num(fin)
#     a = [0] * m
#     b = [0] * int(sqrt(n))
#     for i in range(1, n + 1):
#         a[i * i % m] += 1
#
#     ans = 0
#     for x in range(m):
#         y = (m - x) % m
#         ans += a[x] * a[y]
#     print(ans)

# def BFS_count(x, chs, count):
#     q = []
#     q.append(x)
#     while (q)
#     return count[x]

def solve(fin):
    n = read_num(fin)
    f = read_num_list(fin)
    new_f = [0] + f
    for i in range(0, n):
        new_f[i] -= 1
    f = new_f
    # print(f)
    chs = get_array([n], [])
    for i, p in enumerate(f):
        if p >= 0:
            chs[p].append(i)
    # print(chs)
    q = [x for x in range(0, n) if not chs[x]]
    vis = [0] * n
    count = [0] * n
    while q:
        x = q.pop(0)
        if not chs[x]:
            count[x] = 1
        if f[x] >= 0:
            vis[f[x]] += 1
            # print(vis[f[x]], len(chs[f[x]]))
            if vis[f[x]] == len(chs[f[x]]):
                q.append(f[x])
            count[f[x]] += count[x]


    # print(chs)
    count = sorted(count)
    print(' '.join([str(x) for x in count]))

def __starting_point():
    if SUBMIT:
        solve(sys.stdin)
    else:
        solve(open(in_file_path, 'r'))

__starting_point()

s=input().split()
n=int(s[0])
arr=list(map(int,input().split()))

children=[[] for i in range(n+1)]
for i,j in enumerate(arr):
    if 1<i+2<=n:
        children[j].append(i+2)
leaves=[0]*(n+1)

for i in range(n,0,-1):
    if not children[i]:
        leaves[i]=1
    else:
        leaves[i]=sum(leaves[j] for j in children[i])
    
    
print(' '.join(map(str,sorted(leaves[1:]))))

n = int(input())
if n == 1:
    print(1)
else:
    adj = [[] for i in range(n+10)]
    s = input().split()
    for i in range(2,n+1):
        pi = int(s[i-2])
        adj[i].append(pi)
        adj[pi].append(i)
        
    num = 1
    curr = [1]
    nextcurr = []
    disco = [1]
    visited = {1:True}
    while num < n:
        for v in curr:
            for w in adj[v]:
                if w not in visited:
                    nextcurr.append(w)
                    visited[w] = True
                    disco.append(w)
                    num += 1
        curr = nextcurr
        nextcurr = []

    nl = {}
    nlvals = {}
    for v in disco[::-1]:
        nl[v] = max(sum(nl.get(w,0) for w in adj[v]),1)
        nlvals[nl[v]] = nlvals.get(nl[v],0)+1
    colors = {}
    leaves = nlvals[1]
    colors[1] = leaves
    for c in range(2, leaves+1):
        colors[c] = colors[c-1] + nlvals.get(c,0)

    ans = ""
    j = 1
    for i in range(1, n+1):
        while colors[j] < i:
            j += 1
        ans += str(j) + ' '
    print(ans.strip())


n = int(input())
p = [0,0] + [int(w) for w in input().split()]

d = [0] * (n+1)

for i in range(n, 1, -1):
    if d[i] == 0:
        d[i] = 1
    d[p[i]] += d[i]

if n == 1:
    d[1] = 1

d = d[1:]
d.sort()

print(*d)


from operator import itemgetter
#int(input())
#map(int,input().split())
#[list(map(int,input().split())) for i in range(q)]
#print("YES" * ans + "NO" * (1-ans))
n = int(input())
if n == 1:
    print(1)
else:
    pi = list(map(int,input().split()))
    ai = [1] * (n+1)
    ai[0] = 10**9
    for i in pi:
        ai[i] = 0
    for i in range(n-2,-1,-1):
        ai[pi[i]] += ai[i+2]
    ai.sort()
    for i in range(n):
        print(ai[i],end=" ")


n = int(input())
tr = {}
p = [int(s) for s in input().split()]
for i in range(n-1):
    if not tr.get(p[i]-1):
        tr[p[i]-1] = []
    tr[p[i]-1].append(i+1)
# print(tr)
lc = [-1 for i in range(n)]
def get_lc(i):
    if lc[i] == -1:
        if tr.get(i):
            lc[i] = 0
            for j in tr[i]:
                lc[i] += get_lc(j)
        else:
            lc[i] = 1
    return lc[i]
for i in range(n-1, -1, -1):
    get_lc(i)
print(*sorted(lc))

import sys
from collections import Counter

input = sys.stdin.readline

n=int(input())
P=list(map(int,input().split()))

LIST=[0]*(n+1)

LEAF=[1]*(n+1)
for p in P:
    LEAF[p]=0


for i in range(1,n+1):
    if LEAF[i]==1:
        LIST[i]=1

for i in range(n,1,-1):
    LIST[P[i-2]]+=LIST[i]

counter=Counter(LIST[1:])

SUM=[0]
SC=sorted(counter.keys())

for j in SC:
    SUM.append(SUM[-1]+counter[j])

i=1
j=0
while j<len(SUM):
    if i<=SUM[j]:
        print(SC[j-1],end=" ")
    else:
        j+=1
        continue
    
    i+=1


from bisect import bisect_right as br
from bisect import bisect_left as bl
from collections import defaultdict
from itertools import combinations
import sys
import math
MAX = sys.maxsize
MAXN = 10**5+10
MOD = 10**9+7
def isprime(n):
    n = abs(int(n))
    if n < 2:
        return False
    if n == 2: 
        return True    
    if not n & 1: 
        return False
    for x in range(3, int(n**0.5) + 1, 2):
        if n % x == 0:
            return False
    return True

def mhd(a,b,x,y):
    return abs(a-x)+abs(b-y)

def numIN():
    return(map(int,sys.stdin.readline().strip().split()))

def charIN():
    return(sys.stdin.readline().strip().split())

def bfs(g,d):
	nonlocal n

	for i in range(n,0,-1):
		while g[i]:
			x = g[i].pop()
			d[i]+=d[x]
	return d



n = int(input())
l = list(numIN())
if n==1:
	print(1)
	return
if n==2:
	print(1,1)
	return
d = [0]*(n+1)
l = [0,0]+l
g = defaultdict(list)
for i in range(2,n+1):
	g[l[i]].append(i)
	d[i]+=1
	d[l[i]]+=1
for i in range(1,n+1):
	if g[i]:
		d[i] = 0
x = bfs(g,d)
x.sort()
for i in range(1,n+1):
	print(x[i],end= ' ')





n = int(input())
p = [0,0] + [int(w) for w in input().split()]
d = [0] * (n+1)

for i in range(n, 1, -1):
    if d[i] == 0:
        d[i] = 1
    d[p[i]] += d[i]
if n == 1:
    d[1] = 1
d = d[1:]
d.sort()
print(*d)

from collections import defaultdict
import sys
sys.setrecursionlimit(500000)
test = 0


def countleaf(tree, n, leafs):
    leafs[n] = 1 if len(tree[n]) == 0 else 0

    for i in tree[n]:
        leafs[n] += countleaf(tree, i, leafs)
    
    return leafs[n]
    
n = int(input())
edges = list(map(int, input().split()))
tree = [[] for i in range(n)]

leafs = [0] * n

for i, e in enumerate(edges):
    tree[e - 1] += [i + 1]

if test: print(tree)

for i in range(n - 1, -1, -1):
    if not tree[i]:
        leafs[i] = 1
    else:
        leafs[i] = sum(leafs[j] for j in tree[i])

print(*sorted(leafs))


# -*- coding:utf-8 -*-

"""

created by shuangquan.huang at 12/14/18

"""
import collections

import sys

N = int(input())
p = [int(x) for x in input().split()]


G = collections.defaultdict(list)

for i, v in enumerate(p):
    u = i + 2
    G[u].append(v)
    G[v].append(u)

root = 1

colors = [0] * (N + 1)
counts = [0] * (N + 1)

q = [root]
parents = [0] * (N+1)
vis = [0] * (N+1)
while q:
    u = q.pop()
    if vis[u]:
        colors[parents[u]] += colors[u]
        continue
    children = [v for v in G[u] if v != parents[u]]
    for v in children:
        parents[v] = u
    
    if children:
        vis[u] = True
        q.append(u)
        q.extend(children)
    else:
        vis[u] = True
        colors[u] = 1
        colors[parents[u]] += 1
        
    





#
#
# def dfs(u, parent):
#     cc, hc = 0, 0
#     for v in G[u]:
#         if v != parent:
#             a, b = dfs(v, u)
#             cc += a
#             hc += b
#     counts[u] = hc + 1
#     cc = cc if cc > 0 else 1
#     colors[u] = cc
#     return cc, hc + 1
#
#
# dfs(1, -1)
#
colors = colors[1:]
colors.sort()
print(' '.join(map(str, colors)))


n=int(input())
fa=[0,0]+list(map(int,input().split()))
delta=[0]*(n+1)
suml=[0]*(n+1)
for i in range(n,0,-1):
	if suml[i]==0:
		suml[i]=1
	delta[suml[i]]+=1
	suml[fa[i]]+=suml[i]

for i in range(1,n+1):
	delta[i]+=delta[i-1]
ans=0
for i in range(1,n+1):
	while delta[ans]<i:
		ans+=1
	print("%d "%ans,end="")
print("\n")

n=int(input())
if n==1:
    print(1)
else:
    p=list(map(int,input().split()))
    children=[]
    for i in range(n):
        children.append([])
    for i in range(n-1):
        children[p[i]-1].append(i+1)
    layers=[1]+[0]*(n-1)
    layer=[0]
    num=2
    bylayer=[]
    while len(layer)>0:
        bylayer.append(layer)
        newlayer=[]
        for vert in layer:
            for child in children[vert]:
                layers[child]=num
                newlayer.append(child)
        layer=newlayer
        num+=1
    bylayer=bylayer[::-1]
    count=[0]*n
    for layer in bylayer:
        for vert in layer:
            if children[vert]==[]:
                count[vert]=1
            else:
                count[vert]=sum(count[v] for v in children[vert])
    count.sort()
    out=""
    for guy in count:
        out+=str(guy)+" "
    print(out)

n=int(input())
a=[0,0]+[int(x) for x in input().split()]
ans=[0]*(n+1)
for i in range(n,1,-1):
    if ans[i]==0:
        ans[i]=1
    ans[a[i]]+=ans[i]
if n==1:
    ans[1]=1
ans=ans[1:]
ans.sort()
print(*ans)

n = int(input())
p = list(map(int, input().split()))
gr = [[] for i in range(n)]
for i in range(n - 1):
    gr[p[i] - 1].append(i + 1)

q = [0]
after = []
i = 0
s = [0 for i in range(n)]
used = set()
used.add(0)
while q:
    cur = q.pop()
    after.append(cur)
    for el in gr[cur]:
        if el not in used:
            used.add(el)
            q.append(el)
            i += 1

q = after
for j in range(i, -1, -1):
    if len(gr[q[j]]) == 0:
        s[q[j]] = 1
    else:
        ans = 0
        for c in gr[q[j]]:
            ans += s[c]
        s[q[j]] = ans
s.sort()
print(' '.join(list(map(str, s))))


import collections


n = int(input())
a = [0, 0] + list(map(int, input().split()))

# contruct tree
G = collections.defaultdict(list)
for i in range(2, len(a)):
    G[a[i]].append(i)

# dp[i] represents the number of color needed to make node i be happy
# recursion will get stackover flow, use bottom to top
nodes = []
q = collections.deque([1])
while q:
    node = q.popleft()
    nodes.append(node)
    for v in G[node]:
        q.append(v)

nodes.reverse()

dp = {}
for u in nodes:
    count = 0
    if len(G[u]) == 0: count += 1
    for v in G[u]:
        count += dp[v]
    dp[u] = count


res = sorted(dp.values())
print(' '.join(map(str, res)))


n=int(input())
p=[0,0]+list(map(int,input().split()))
d=[0]*(n+1)
for i in range(n,1,-1):
    if d[i]==0:
        d[i]=1
    d[p[i]]+=d[i]
if n==1:
    d[1]=1
d=d[1:]
d.sort()
print(*d)

from bisect import bisect_left as bl, bisect_right as br, insort
import sys
import heapq
#from math import *
from collections import defaultdict as dd, deque
def data(): return sys.stdin.readline().strip()
def mdata(): return map(int, data().split())
#sys.setrecursionlimit(1000000)
mod=int(1e9+7)

def bfs(x):
    cnt=0
    for i in tree[x]:
        bfs(i)
        cnt+=a[i]
    if len(tree[x])==0:
        cnt=1
    a[x]=cnt

n=int(data())
tree=[{} for i in range(n)]
if n>1:
    P=list(mdata())
    for i in range(n-1):
        tree[P[i]-1][i+1]=0
    a=[0]*n
    for i in range(n-1,-1,-1):
        if len(tree[i])==0:
            a[i]=1
        else:
            for j in tree[i]:
                a[i]+=a[j]
    a.sort()
else:
    a=[1]
print(*a)

class DFS:
    def __init__(self):
        self.G= []
        self.leave_tree= []

    def take_input(self):
        k = int(input())
        if(k>1):
            graph =[int(node)-1 for (node) in input().split(' ')]
            self.G = [[] for _ in range(len(graph)+1)]   
            for i in range(len(graph)):
                self.G[graph[i]].append(i+1)
            self.visited = [0]*k
            self.leave_tree = [0]*k
            for i in range(k-1,-1,-1):
                if len(self.G[i])==0:
                    self.leave_tree[i]=1
                else:
                    for j in self.G[i]:
                        self.leave_tree[i]+=self.leave_tree[j]
            self.leave_tree.sort()
            print(*self.leave_tree)
        else:
            print(k)





x = DFS()
x.take_input()


import sys
input=sys.stdin.readline
from collections import defaultdict
graph=defaultdict(list)
n=int(input())
par=[ int(i) for i in input().split() if i!='\n']
bulb=[1]*(n+1)
for i in range(n-1):
    bulb[par[i]]=0
    graph[par[i]].append(i+2)
#print(graph,bulb)
zero=bulb.count(0)
for  i in range(n,0,-1):
    if bulb[i]==0:
        count=0
        for j in graph[i]:
            count+=bulb[j]
        bulb[i]=count
bulb=bulb[1:]
bulb.sort()
sys.stdout.write(' '.join(map(str,bulb)))


import sys
input=sys.stdin.readline
from collections import defaultdict
graph=defaultdict(list)
n=int(input())
par=[ int(i) for i in input().split() if i!='\n']
bulb=[1]*(n+1)
for i in range(n-1):
    bulb[par[i]]=0
    graph[par[i]].append(i+2)
#print(graph,bulb,par)
zero=bulb.count(0)
for  i in range(n,0,-1):
    if bulb[i]==0:
        count=0
        for j in graph[i]:
            count+=bulb[j]
        bulb[i]=count
bulb=bulb[1:]
bulb.sort()
sys.stdout.write(' '.join(map(str,bulb)))


from collections import deque

class Graph(object):
	"""docstring for Graph"""
	def __init__(self,n,d): # Number of nodes and d is True if directed
		self.n = n
		self.graph = [[] for i in range(n)]
		self.parent = [-1 for i in range(n)]
		self.directed = d
		
	def addEdge(self,x,y):
		self.graph[x].append(y)
		if not self.directed:
			self.graph[y].append(x)

	def bfs(self, root): # NORMAL BFS
		self.parent = [-1 for i in range(self.n)]
		queue = [root]
		queue = deque(queue)
		vis = [0]*self.n
		while len(queue)!=0:
			element = queue.popleft()
			vis[element] = 1
			for i in self.graph[element]:
				if vis[i]==0:
					queue.append(i)
					self.parent[i] = element

	def dfs(self, root, ans): # Iterative DFS
		stack=[root]
		vis=[0]*self.n
		stack2=[]
		while len(stack)!=0: # INITIAL TRAVERSAL
			element = stack.pop()
			if vis[element]:
				continue
			vis[element] = 1
			stack2.append(element)
			for i in self.graph[element]:
				if vis[i]==0:
					self.parent[i] = element
					stack.append(i)

		while len(stack2)!=0: # BACKTRACING. Modify the loop according to the question
			element = stack2.pop()
			m = 0
			flag=0
			for i in self.graph[element]:
				if i!=self.parent[element]:
					flag=1
					m += ans[i]
			if not flag:	
				ans[element] = 1
			else:
				ans[element] = m
		return ans

	def shortestpath(self, source, dest): # Calculate Shortest Path between two nodes
		self.bfs(source)
		path = [dest]
		while self.parent[path[-1]]!=-1:
			path.append(parent[path[-1]])
		return path[::-1]

	def ifcycle(self):
		self.bfs(0)
		queue = [0]
		vis = [0]*n
		queue = deque(queue)
		while len(queue)!=0:
			element = queue.popleft()
			vis[element] = 1
			for i in graph[element]:
				if vis[i]==1 and i!=parent[element]:
					return True
				if vis[i]==0:
					queue.append(i)
					vis[i] = 1
		return False

	def reroot(self, root, ans):
		stack = [root]
		vis = [0]*n
		while len(stack)!=0:
			e = stack[-1]
			if vis[e]:
				stack.pop()
				# Reverse_The_Change()
				continue
			vis[e] = 1
			for i in graph[e]:
				if not vis[e]:
					stack.append(i)
			if self.parent[e]==-1:
				continue
			# Change_The_Answers()



n = int(input())
g = Graph(n,False)
p = list(map(int,input().split()))
for i in range(n-1):
	g.addEdge(i+1,p[i]-1)
depth = [-1]*n
g.dfs(0,depth)
depth.sort()
print(*depth)


from sys import stdin
from collections import Counter

class Node:
    def __init__(self,val):
        self.val=val
        self.forw=set()
        self.cou=0

    def __str__(self):
        return f'{self.val} {self.forw} {self.cou}'

n=int(stdin.readline())
arr=[Node(i) for i in range(1,n+1)]
c=2
for x in map(int,stdin.readline().split()):
    arr[x-1].forw.add(c)
    c+=1


dct=Counter()
lst = [1]
while len(lst):
    fl = 0
    for i in arr[lst[-1]-1].forw:
        lst.append(i)
        fl = 1
        break
    if fl:
        arr[lst[-2]-1].forw.remove(i)
    if not fl:
        if arr[lst[-1]-1].cou ==0:
            arr[lst[-1]-1].cou=1
        dct[arr[lst[-1]-1].cou]+=1
        k=arr[lst.pop()-1].cou
        if len(lst):arr[lst[-1]-1].cou+=k

y=1
for _ in range(n):
    while not dct[y]:
        y+=1
    dct[y]-=1
    print(y,end=' ')

import sys
import threading

def dfs(g, i, p):
    nonlocal ans
    count = 0
    for j in g[i]:
        if j == p:
            continue
        count += dfs(g, j, i)
    if count == 0:
        count = 1
    ans.append(count)
    return count

def solve():
    
    n = int(input())
    l = list(map(int, input().split()))
    g = [[] for i in range(n+1)]

    for i in range(1, n):
        g[i+1].append(l[i-1])
        g[l[i-1]].append(i+1)

    dfs(g, 1, 0)
    ans.sort()
    st = ' '.join(map(str, ans))
    print(st)

ans = []
max_recur_size = 10**5*2 + 1000
max_stack_size = max_recur_size*500
 
sys.setrecursionlimit(max_recur_size)
threading.stack_size(max_stack_size)
thread = threading.Thread(target=solve)
thread.start()