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: MEDIUM_HARD
Tags: Graph algorithms

Graph traversal

Constructive algorithms

Sorting

Greedy algorithms

Tree algorithms

Dynamic programming
Skill types: Dynamic programming

Sorting

Greedy algorithms
Expected Time Complexity: O(N)

Starter code:

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


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
colors = colors[1:]
colors.sort()
print(' '.join(map(str, colors)))


from collections import deque

class Graph(object):

	def __init__(self, n, d):
		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):
		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):
		stack = [root]
		vis = [0] * self.n
		stack2 = []
		while len(stack) != 0:
			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:
			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):
		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()
				continue
			vis[e] = 1
			for i in graph[e]:
				if not vis[e]:
					stack.append(i)
			if self.parent[e] == -1:
				continue
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)


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


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)


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 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=' ')


from operator import itemgetter
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=' ')


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


import collections
n = int(input())
a = [0, 0] + list(map(int, input().split()))
G = collections.defaultdict(list)
for i in range(2, len(a)):
	G[a[i]].append(i)
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)))


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=' ')


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()


il_rozgalezien = int(input())
d = [0, 0] + [int(x) for x in input().split()]
slownik = {}
for i in range(2, il_rozgalezien + 1):
	if d[i] in slownik:
		slownik[d[i]].append(i)
	else:
		slownik[d[i]] = [i]
il_lisci = [0] * (il_rozgalezien + 1)
for i in range(il_rozgalezien, 1, -1):
	if i not in slownik:
		il_lisci[i] = 1
		il_lisci[d[i]] += 1
	else:
		il_lisci[d[i]] += il_lisci[i]
il_lisci.sort()
if il_rozgalezien == 1:
	print(1)
else:
	print(*il_lisci[1:])


import sys
input = sys.stdin.readline
from collections import deque
n = int(input())
p = list(map(int, input().split()))
if n == 1:
	print(1)
	exit()
g = [[] for i in range(n)]
for i in range(n - 1):
	g[p[i] - 1].append(i + 1)
	g[i + 1].append(p[i] - 1)
order = []
p = [-1] * n
dq = deque([[-1, 0]])
while dq:
	(par, ver) = dq.popleft()
	order.append(ver)
	for to in g[ver]:
		if to == par:
			continue
		dq.append([ver, to])
		p[to] = ver
order.reverse()
c = [0] * n
for i in range(1, n):
	if len(g[i]) == 1:
		c[i] = 1
for x in order[:-1]:
	c[p[x]] += c[x]
c.sort()
print(*c)


import sys
import random
import copy
from itertools import permutations, combinations
from math import sqrt, fabs, ceil
from collections import namedtuple
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)
	f = read_num_list(fin)
	new_f = [0] + f
	for i in range(0, n):
		new_f[i] -= 1
	f = new_f
	chs = get_array([n], [])
	for (i, p) in enumerate(f):
		if p >= 0:
			chs[p].append(i)
	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
			if vis[f[x]] == len(chs[f[x]]):
				q.append(f[x])
			count[f[x]] += count[x]
	count = sorted(count)
	print(' '.join([str(x) for x in count]))
if SUBMIT:
	solve(sys.stdin)
else:
	solve(open(in_file_path, 'r'))


n = int(input())
a = input().split()
A = [int(x) for x in a]
B = [[x, []] for x in range(1, n + 1)]
i = 0
for i in range(len(A)):
	B[A[i] - 1][1].append(i + 2)

def merge(arr, l, m, r):
	n1 = m - l + 1
	n2 = r - m
	L = [0] * n1
	R = [0] * n2
	for i in range(0, n1):
		L[i] = arr[l + i]
	for j in range(0, n2):
		R[j] = arr[m + 1 + j]
	i = 0
	j = 0
	k = l
	while i < n1 and j < n2:
		if L[i] <= R[j]:
			arr[k] = L[i]
			i += 1
		else:
			arr[k] = R[j]
			j += 1
		k += 1
	while i < n1:
		arr[k] = L[i]
		i += 1
		k += 1
	while j < n2:
		arr[k] = R[j]
		j += 1
		k += 1

def mergeSort(arr, l, r):
	if l < r:
		m = (l + (r - 1)) // 2
		mergeSort(arr, l, m)
		mergeSort(arr, m + 1, r)
		merge(arr, l, m, r)
for j in B:
	mergeSort(j[1], 0, len(j[1]) - 1)
for i in range(len(B)):
	if B[n - i - 1][1] == []:
		B[n - i - 1][1] = 1
	else:
		ans = 0
		for j in B[n - i - 1][1]:
			ans += B[j - 1][1]
		B[n - i - 1][1] = ans
C = [0 for x in range(0, n + 1)]
for i in B:
	C[i[1]] += 1
for i in range(len(C)):
	for j in range(C[i]):
		print(i, end=' ')
print('')


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 = [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()
for i in range(n):
	print(d[i], end=' ')


from bisect import bisect_left as bl, bisect_right as br, insort
import sys
import heapq
from collections import defaultdict as dd, deque

def data():
	return sys.stdin.readline().strip()

def mdata():
	return map(int, data().split())
mod = int(1000000000.0 + 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)


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())
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())
from types import GeneratorType

def bootstrap(f, stack=[]):

	def wrappedfunc(*args, **kwargs):
		if stack:
			return f(*args, **kwargs)
		else:
			to = f(*args, **kwargs)
			while True:
				if type(to) is GeneratorType:
					stack.append(to)
					to = next(to)
				else:
					stack.pop()
					if not stack:
						break
					to = stack[-1].send(to)
			return to
	return wrappedfunc

class Graph:

	def __init__(self, V):
		self.V = V
		self.adj = [[] for i in range(V)]

	@bootstrap
	def DFSUtil(self, temp, v, visited, happy):
		visited[v] = True
		for i in self.adj[v]:
			if visited[i] == False:
				temp = (yield self.DFSUtil(temp, i, visited, happy))
				happy[v] += happy[i]
		if happy[v] == 0:
			happy[v] += 1
		yield temp

	def addEdge(self, v, w):
		self.adj[v].append(w)
		self.adj[w].append(v)
G = Graph(n)
a = list(map(int, input().split()))
happy = [0 for _ in range(0, n)]
visited = [False for _ in range(n)]
for i in range(len(a)):
	G.addEdge(i + 1, a[i] - 1)
G.DFSUtil([], 0, visited, happy)
happy.sort()
print(*happy)


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())


from types import GeneratorType

def bootstrap(f, stack=[]):

	def wrappedfunc(*args, **kwargs):
		if stack:
			return f(*args, **kwargs)
		else:
			to = f(*args, **kwargs)
			while True:
				if type(to) is GeneratorType:
					stack.append(to)
					to = next(to)
				else:
					stack.pop()
					if not stack:
						break
					to = stack[-1].send(to)
			return to
	return wrappedfunc
from collections import defaultdict
import sys
n = int(input())
children = defaultdict(list)
coloursneeded = defaultdict(int)
for (node, parent) in enumerate([int(x) for x in input().split()], start=2):
	children[parent].append(node)

@bootstrap
def needed(node):
	if node not in children.keys():
		coloursneeded[node] = 1
		yield 1
	val = 0
	for a in children[node]:
		val += (yield needed(a))
	coloursneeded[node] = val
	yield val
needed(1)
print(*sorted(coloursneeded.values()), sep=' ')


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


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 sys
import threading

def dfs(g, i, p):
	global 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()


n = int(input())
p = [-1] + list(map(int, input().split()))
g = [[] for i in range(n)]
for i in range(n - 1):
	g[i + 1].append(p[i + 1] - 1)
	g[p[i + 1] - 1].append(i + 1)
cnt = [0] * n
stack = [(-1, 0)]
stack2 = [(-1, 0)]
while stack:
	(par, ver) = stack.pop()
	for to in g[ver]:
		if par != to:
			stack.append((ver, to))
			stack2.append((ver, to))
while stack2:
	(par, ver) = stack2.pop()
	if len(g[ver]) == 1 and ver != 0:
		cnt[ver] = 1
		continue
	s = 0
	for to in g[ver]:
		if par == to:
			continue
		s += cnt[to]
	cnt[ver] = s
if n == 1:
	print(1)
else:
	print(*sorted(cnt))


N = int(input())
if N == 1:
	print(1)
	exit()
temp = [int(x) for x in input().split()]
temp.insert(0, 0)
temp.insert(0, 0)
visited = [0] * (N + 1)
for i in range(N, 1, -1):
	if not visited[i]:
		visited[i] = 1
	visited[temp[i]] += visited[i]
print(*sorted(visited[1:]))