In the rush of modern life, people often forget how beautiful the world is. The time to enjoy those around them is so little that some even stand in queues to several rooms at the same time in the clinic, running from one queue to another.

(Cultural note: standing in huge and disorganized queues for hours is a native tradition in Russia, dating back to the Soviet period. Queues can resemble crowds rather than lines. Not to get lost in such a queue, a person should follow a strict survival technique: you approach the queue and ask who the last person is, somebody answers and you join the crowd. Now you're the last person in the queue till somebody else shows up. You keep an eye on the one who was last before you as he is your only chance to get to your destination) I'm sure many people have had the problem when a stranger asks who the last person in the queue is and even dares to hint that he will be the last in the queue and then bolts away to some unknown destination. These are the representatives of the modern world, in which the ratio of lack of time is so great that they do not even watch foreign top-rated TV series. Such people often create problems in queues, because the newcomer does not see the last person in the queue and takes a place after the "virtual" link in this chain, wondering where this legendary figure has left.

The Smart Beaver has been ill and he's made an appointment with a therapist. The doctor told the Beaver the sad news in a nutshell: it is necessary to do an electrocardiogram. The next day the Smart Beaver got up early, put on the famous TV series on download (three hours till the download's complete), clenched his teeth and bravely went to join a queue to the electrocardiogram room, which is notorious for the biggest queues at the clinic.

Having stood for about three hours in the queue, the Smart Beaver realized that many beavers had not seen who was supposed to stand in the queue before them and there was a huge mess. He came up to each beaver in the ECG room queue and asked who should be in front of him in the queue. If the beaver did not know his correct position in the queue, then it might be his turn to go get an ECG, or maybe he should wait for a long, long time...

As you've guessed, the Smart Beaver was in a hurry home, so he gave you all the necessary information for you to help him to determine what his number in the queue can be.


-----Input-----

The first line contains two integers n (1 ≤ n ≤ 10^3) and x (1 ≤ x ≤ n) — the number of beavers that stand in the queue and the Smart Beaver's number, correspondingly. All willing to get to the doctor are numbered from 1 to n.

The second line contains n integers a_1, a_2, ..., a_{n} (0 ≤ a_{i} ≤ n) — the number of the beaver followed by the i-th beaver. If a_{i} = 0, then the i-th beaver doesn't know who is should be in front of him. It is guaranteed that values a_{i} are correct. That is there is no cycles in the dependencies. And any beaver is followed by at most one beaver in the queue.

The input limits for scoring 30 points are (subproblem B1):   It is guaranteed that the number of zero elements a_{i} doesn't exceed 20. 

The input limits for scoring 100 points are (subproblems B1+B2):   The number of zero elements a_{i} is arbitrary. 


-----Output-----

Print all possible positions of the Smart Beaver in the line in the increasing order.


-----Examples-----
Input
6 1
2 0 4 0 6 0

Output
2
4
6

Input
6 2
2 3 0 5 6 0

Output
2
5

Input
4 1
0 0 0 0

Output
1
2
3
4

Input
6 2
0 0 1 0 4 5

Output
1
3
4
6



-----Note----- [Image]  Picture for the fourth test.

Difficulty: MEDIUM
Tags: Graph traversal

Complete search
Skill types: Complete search

Starter code:

Solutions:
(n, x) = map(int, input().split())
a = [-10000] + list(map(int, input().split()))
ceps = []
ones = 0
was = set()
for i in range(1, n + 1):
	if i not in was and i not in a:
		cep = [i]
		while a[i]:
			cep.append(a[i])
			i = a[i]
		for i in cep:
			was.add(i)
		if x in cep:
			r = cep.index(x)
			l = len(cep) - r - 1
		elif len(cep) == 1:
			ones += 1
		else:
			ceps.append(len(cep))
import itertools
sums = set(ceps)
for i in range(2, len(ceps) + 1):
	for comb in itertools.combinations(ceps, i):
		sums.add(sum(comb))
sums.add(0)
poss = set()
for s in sums:
	for i in range(ones + 1):
		poss.add(l + s + 1 + i)
for pos in sorted(poss):
	print(pos)


from collections import defaultdict

class UnionFind:

	def __init__(self, n):
		self.n = n
		self.parents = [-1] * n

	def find(self, x):
		if self.parents[x] < 0:
			return x
		else:
			self.parents[x] = self.find(self.parents[x])
			return self.parents[x]

	def union(self, x, y):
		x = self.find(x)
		y = self.find(y)
		if x == y:
			return
		if self.parents[x] > self.parents[y]:
			(x, y) = (y, x)
		self.parents[x] += self.parents[y]
		self.parents[y] = x

	def size(self, x):
		return -self.parents[self.find(x)]

	def same(self, x, y):
		return self.find(x) == self.find(y)

	def members(self, x):
		root = self.find(x)
		return [i for i in range(self.n) if self.find(i) == root]

	def roots(self):
		return [i for (i, x) in enumerate(self.parents) if x < 0]

	def group_count(self):
		return len(self.roots())

	def all_group_members(self):
		group_members = defaultdict(list)
		for member in range(self.n):
			group_members[self.find(member)].append(member)
		return group_members
(n, x) = map(int, input().split())
a = list(map(int, input().split()))
for i in range(n):
	a[i] -= 1
y = x - 1
cnt = 0
while y != -1:
	cnt += 1
	y = a[y]
p = x - 1
uf = UnionFind(n)
for i in range(n):
	if a[i] != -1:
		uf.union(i, a[i])
l = [0]
for t in uf.roots():
	if not uf.same(t, p):
		l.append(uf.size(t))
dp = [0] * (n + 1)
dp[0] = 1
for i in range(1, len(l)):
	for j in range(1, n + 1)[::-1]:
		if 0 <= j - l[i] <= n and dp[j - l[i]] >= 1:
			dp[j] = 1
ans = []
for i in range(n + 1):
	if dp[i] >= 1:
		ans.append(i + cnt)
print(*ans, sep='\n')


import sys
sys.setrecursionlimit(100000)

def solve():
	(n, x) = rv()
	x -= 1
	(a,) = rl(1)
	a = [val - 1 for val in a]
	nxt = [True] * n
	index = [-1] * n
	for i in range(len(a)):
		index[i] = get(i, a, nxt)
	curindex = index[x] - 1
	others = list()
	for i in range(n):
		if not bad(i, a, x) and nxt[i]:
			others.append(index[i])
	others.sort()
	possible = [False] * (n + 1)
	possible[0] = True
	for val in others:
		pcopy = list(possible)
		for i in range(n + 1):
			if possible[i]:
				both = i + val
				if both < n + 1:
					pcopy[both] = True
		possible = pcopy
	res = list()
	for i in range(n + 1):
		if possible[i]:
			comb = i + curindex
			if comb < n:
				res.append(comb)
	print('\n'.join(map(str, [val + 1 for val in res])))

def bad(index, a, x):
	if index == x:
		return True
	if a[index] == x:
		return True
	if a[index] == -1:
		return False
	return bad(a[index], a, x)

def get(index, a, nxt):
	if a[index] == -1:
		return 1
	else:
		nxt[a[index]] = False
		return get(a[index], a, nxt) + 1

def prt(l):
	return print(' '.join(l))

def rv():
	return map(int, input().split())

def rl(n):
	return [list(map(int, input().split())) for _ in range(n)]
if sys.hexversion == 50594544:
	sys.stdin = open('test.txt')
solve()


def f(x, p):
	q = []
	while x:
		q.append(x)
		x = p[x]
	return q
from collections import defaultdict
(n, k) = map(int, input().split())
t = list(map(int, input().split()))
p = [0] * (n + 1)
for (i, j) in enumerate(t, 1):
	p[j] = i
p = [f(i, p) for (i, j) in enumerate(t, 1) if j == 0]
s = defaultdict(int)
for i in p:
	if k in i:
		t = {i.index(k) + 1}
	else:
		s[len(i)] += 1
s = [list(range(i, k * i + 1, i)) for (i, k) in s.items()]
for q in s:
	t |= {x + y for x in q for y in t}
print('\n'.join(map(str, sorted(list(t)))))


(n, x) = map(int, input().split())
link1 = list(map(int, input().split()))
link2 = [0] * (n + 1)
for (i, v) in enumerate(link1, 1):
	if v != 0:
		link2[v] = i
table = [False] * n
table[0] = True
for (i, v) in enumerate(link1, 1):
	if v == 0:
		len = 0
		flag = False
		now = i
		while now:
			len += 1
			if now == x:
				flag = True
				pos = len
			now = link2[now]
		if not flag:
			for j in reversed(range(n - len)):
				if table[j]:
					table[j + len] = True
for i in range(n):
	if table[i]:
		print(i + pos)


import math
import sys
from bisect import bisect_right, bisect_left, insort_right
from collections import Counter, defaultdict
from heapq import heappop, heappush
from itertools import accumulate, permutations
from sys import stdout
R = lambda : map(int, input().split())
(n, s) = R()
seq = [0] + list(R())
incm = [0] * (n + 1)
for x in seq:
	if x:
		incm[x] = 1
sz = [0] * (n + 1)
st = []
bs = 1
x = s
while seq[x]:
	bs += 1
	x = seq[x]
for (i, x) in enumerate(incm):
	foundx = False
	if not x:
		l = i
		while i:
			foundx = foundx or i == s
			sz[l] += 1
			i = seq[i]
		if seq[l] and (not foundx):
			st.append(sz[l])
nz = seq.count(0) - 1 - len(st) - 1
pos = [0] * (n + 1)
for p in st:
	for i in range(n, -1, -1):
		if bs + i + p < n + 1 and pos[bs + i]:
			pos[bs + i + p] = 1
	pos[bs + p] = 1
rp = [0] * (n + 1)
rp[bs] = 1
if bs + nz + 1 < n + 1:
	rp[bs + nz + 1] = -1
for i in range(n + 1):
	if pos[i]:
		rp[i] += 1
		if i + nz + 1 < n + 1:
			rp[i + nz + 1] -= 1
for i in range(1, n + 1):
	rp[i] += rp[i - 1]
for i in range(1, n + 1):
	if rp[i]:
		print(i)


import collections

def find(parents, i):
	if parents[i] == i:
		return i
	result = find(parents, parents[i])
	parents[i] = result
	return result

def union(parents, i, j):
	(i, j) = (find(parents, i), find(parents, j))
	parents[i] = j
(n, x) = map(int, input().split())
a = {i + 1: int(ai) for (i, ai) in enumerate(input().split())}
parents = {i: i for i in a}
x_order = 1
x_current = x
while a[x_current] != 0:
	x_order += 1
	x_current = a[x_current]
for (source, target) in a.items():
	if target != 0:
		union(parents, source, target)
del a
x_representative = find(parents, x)
sizes = collections.Counter()
for i in parents:
	i_representative = find(parents, i)
	if i_representative != x_representative:
		sizes[i_representative] += 1
del parents
adds = collections.Counter()
for size in sizes.values():
	adds[size] += 1
del sizes
sieve = {0: 1}
for (add, count) in adds.items():
	sieve_update = {}
	for (i, j) in sieve.items():
		if j != 0:
			for k in range(1, count + 1):
				if i + add * k <= n:
					sieve_update[i + add * k] = 1
	sieve.update(sieve_update)
del adds
for (position, value) in sorted(sieve.items()):
	if value:
		print(position + x_order)


def put():
	return map(int, input().split())
(n, x) = put()
a = list(put())
parent = list(range(n + 1))
for i in range(n):
	if a[i] != 0:
		parent[a[i]] = i + 1
cnt = []
z = 0
for i in range(n):
	if a[i] == 0:
		j = i + 1
		c = 1
		found = False
		if j == x:
			z = c
			found = True
		while j != parent[j]:
			j = parent[j]
			c += 1
			if j == x:
				z = c
				found = True
		if not found:
			cnt.append(c)
(n, m) = (len(cnt) + 1, sum(cnt) + 1)
dp = [[0] * (m + 1) for i in range(n + 1)]
dp[0][0] = 1
s = set()
s.add(0)
for i in range(1, n):
	for j in range(m):
		if j == 0 or dp[i - 1][j] == 1 or (j - cnt[i - 1] >= 0 and dp[i - 1][j - cnt[i - 1]] == 1):
			dp[i][j] = 1
			s.add(j)
l = []
for i in s:
	l.append(i + z)
l.sort()
print(*l)


import sys
input = sys.stdin.readline
from collections import defaultdict

class UnionFind:

	def __init__(self, n):
		self.n = n
		self.parents = [-1] * n

	def find(self, x):
		if self.parents[x] < 0:
			return x
		else:
			self.parents[x] = self.find(self.parents[x])
			return self.parents[x]

	def union(self, x, y):
		x = self.find(x)
		y = self.find(y)
		if x == y:
			return
		if self.parents[x] > self.parents[y]:
			(x, y) = (y, x)
		self.parents[x] += self.parents[y]
		self.parents[y] = x

	def size(self, x):
		return -self.parents[self.find(x)]

	def same(self, x, y):
		return self.find(x) == self.find(y)

	def members(self, x):
		root = self.find(x)
		return [i for i in range(self.n) if self.find(i) == root]

	def roots(self):
		return [i for (i, x) in enumerate(self.parents) if x < 0]

	def group_count(self):
		return len(self.roots())

	def all_group_members(self):
		group_members = defaultdict(list)
		for member in range(self.n):
			group_members[self.find(member)].append(member)
		return group_members
(n, x) = map(int, input().split())
x -= 1
a = list(map(int, input().split()))
uf = UnionFind(n)
for i in range(n):
	if a[i] != 0:
		uf.union(a[i] - 1, i)
c = []
for r in uf.roots():
	if x not in uf.members(r):
		c.append(uf.size(r))
size0 = 0
xx = x
while a[xx] != 0:
	size0 += 1
	xx = a[xx] - 1
dp = [[0] * (n + 1) for i in range(len(c) + 1)]
dp[0][0] = 1
for i in range(1, len(c) + 1):
	for j in range(n + 1):
		dp[i][j] |= dp[i - 1][j] | dp[i - 1][j - c[i - 1]]
ans = []
for i in range(n + 1):
	if dp[len(c)][i]:
		ans.append(i + size0 + 1)
print(*ans, sep='\n')