There are n cities in Berland. Each city has its index — an integer number from 1 to n. The capital has index r1. All the roads in Berland are two-way. The road system is such that there is exactly one path from the capital to each city, i.e. the road map looks like a tree. In Berland's chronicles the road map is kept in the following way: for each city i, different from the capital, there is kept number pi — index of the last city on the way from the capital to i.

Once the king of Berland Berl XXXIV decided to move the capital from city r1 to city r2. Naturally, after this the old representation of the road map in Berland's chronicles became incorrect. Please, help the king find out a new representation of the road map in the way described above.

Input

The first line contains three space-separated integers n, r1, r2 (2 ≤ n ≤ 5·104, 1 ≤ r1 ≠ r2 ≤ n) — amount of cities in Berland, index of the old capital and index of the new one, correspondingly.

The following line contains n - 1 space-separated integers — the old representation of the road map. For each city, apart from r1, there is given integer pi — index of the last city on the way from the capital to city i. All the cities are described in order of increasing indexes.

Output

Output n - 1 numbers — new representation of the road map in the same format.

Examples

Input

3 2 3
2 2


Output

2 3 

Input

6 2 4
6 1 2 4 2


Output

6 4 1 4 2

Difficulty: MEDIUM_HARD
Tags: Graph algorithms

Graph traversal

Starter code:

Solutions:
import sys
sys.setrecursionlimit(100000)
(n, r1, r2) = map(int, input().split())
a = list(map(int, input().split()))
g = {}
num = 0
for (k, v) in enumerate(a):
	num += 1
	if num == r1:
		num += 1
	if num not in g:
		g[num] = []
	g[num].append(v)
	if v not in g:
		g[v] = []
	g[v].append(num)
b = [0] * (n + 1)
visited = set()

def visit(cur, parent):
	visited.add(cur)
	b[cur] = parent
	for child in g[cur]:
		if child not in visited:
			visit(child, cur)
from collections import deque
q = deque()
q.append((r2, 0))
while q:
	(cur, parent) = q.popleft()
	if cur not in visited:
		visited.add(cur)
		b[cur] = parent
		for child in g[cur]:
			q.append((child, cur))
b2 = [b[k] for k in range(n + 1) if k > 0 and k != r2]
print(*b2)


from sys import setrecursionlimit
import threading
setrecursionlimit(10 ** 9)
threading.stack_size(67108864)

def dfs(u, fr):
	global al, parent
	for i in al[u]:
		if i != fr:
			parent[i] = u
			dfs(i, u)

def main():
	global al, parent
	(n, r1, r2) = [int(i) for i in input().split()]
	r1 -= 1
	r2 -= 1
	p = [int(i) for i in input().split()]
	al = [[] for i in range(n)]
	for i in range(n - 1):
		if i >= r1:
			al[i + 1].append(p[i] - 1)
			al[p[i] - 1].append(i + 1)
		else:
			al[i].append(p[i] - 1)
			al[p[i] - 1].append(i)
	parent = [-1] * n
	dfs(r2, -1)
	print(' '.join([str(i + 1) for i in parent if i != -1]))
thread = threading.Thread(target=main)
thread.start()


(n, r1, r2) = list(map(int, input().split()))
p = list(map(int, input().split()))
a = [0] * n
for i in range(n - 1):
	a[i + int(i >= r1 - 1)] = p[i]
s = [r2]
v = r2
while v != r1:
	s.append(a[v - 1])
	v = a[v - 1]
for i in range(1, len(s)):
	a[s[i] - 1] = s[i - 1]
print(*a[:r2 - 1] + a[r2:])


import sys
input = sys.stdin.readline
(n, r1, r2) = map(int, input().split())
r1 -= 1
r2 -= 1
p = list(map(int, input().split()))
g = [[] for i in range(n)]
c = 0
for i in range(n - 1):
	if i == r1:
		c += 1
	g[i + c].append(p[i] - 1)
	g[p[i] - 1].append(i + c)
pre = [-1] * n
q = [[-1, r2]]
pre[r2] = r2
while q:
	(par, ver) = q.pop()
	for to in g[ver]:
		if par != to:
			pre[to] = ver
			q.append([ver, to])
ans = []
for i in range(n):
	if pre[i] != i:
		ans.append(pre[i] + 1)
print(*ans)


import sys
from math import gcd, sqrt
from collections import defaultdict, Counter, deque
import math
import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def get_sum(bit, i):
	s = 0
	i += 1
	while i > 0:
		s += bit[i]
		i -= i & -i
	return s

def update(bit, n, i, v):
	i += 1
	while i <= n:
		bit[i] += v
		i += i & -i

def modInverse(b, m):
	g = math.gcd(b, m)
	if g != 1:
		return -1
	else:
		return pow(b, m - 2, m)
(n, r1, r2) = map(int, input().split())
l = [0] + list(map(int, input().split()))
hash = defaultdict(list)
cur = 1
i = 1
ans = [0] * n

def bfs(n, tot):
	boo = defaultdict(bool)
	queue = [n]
	par = [0] * (tot + 1)
	boo[n] = True
	while queue:
		z = queue.pop(0)
		for i in hash[z]:
			if not boo[i]:
				queue.append(i)
				par[i] = z
				boo[i] = True
	return par[:n] + par[n + 1:]
while i < len(l):
	if cur == r1:
		cur += 1
	else:
		hash[cur].append(l[i])
		hash[l[i]].append(cur)
		i += 1
		cur += 1
ans = bfs(r2, n)
print(*ans[1:])


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

def dfs(r1, r2):
	p = -1
	curr = r2
	while p != r1:
		tmp = parent[curr]
		parent[curr] = p
		p = curr
		curr = tmp
(n, r1, r2) = put()
parent = [0]
parent.extend(list(put()))
parent.insert(r1, -1)
dfs(r1, r2)
parent.remove(0)
parent.remove(-1)
print(*parent)


(n, r1, r2) = map(int, input().split())
gr = [[] for i in range(n)]
a = list(map(int, input().split()))
i = 0
while i < r1 - 1:
	gr[i].append(a[i] - 1)
	gr[a[i] - 1].append(i)
	i += 1
while i < n - 1:
	gr[i + 1].append(a[i] - 1)
	gr[a[i] - 1].append(i + 1)
	i += 1
v = [False for i in range(n)]
s = [r2 - 1]
tr = {}
while s:
	x = s.pop()
	v[x] = True
	for j in gr[x]:
		if v[j]:
			continue
		s.append(j)
		tr[j] = x + 1
for i in range(n):
	if i != r2 - 1:
		print(tr[i], end=' ')


import sys
from math import sqrt, gcd, ceil, log
from collections import defaultdict, Counter, deque
input = sys.stdin.readline
read = lambda : list(map(int, input().strip().split()))

def main():
	(n, r1, r2) = read()
	rep = [0] + read()
	par = [0] * (n + 1)
	j = 0
	adj = [[] for i in range(n + 1)]
	for i in range(1, n):
		if i == r1:
			j += 1
		adj[i + j].append(rep[i])
		adj[rep[i]].append(i + j)
	stk = [r2]
	visited = [0] * (n + 1)
	visited[r2] = 1
	while stk:
		elem = stk.pop()
		for i in adj[elem]:
			if not visited[i]:
				par[i] = elem
				visited[i] = 1
				stk.append(i)
	print(' '.join(map(str, [i for i in par if i != 0])))
main()


(n, r, r1) = map(int, input().split())
(capt, ind) = ([0] * (n + 1), 1)
ig = r1
capt[0] = r
for (u, v) in enumerate(map(int, input().split())):
	ind += u + 1 == r
	capt[ind] = v
	ind += 1
r0 = capt[r1]
while 1:
	temp = capt[r0]
	if temp == r1:
		break
	capt[r0] = r1
	r1 = r0
	r0 = temp
for x in range(1, n + 1):
	if x != ig:
		print(capt[x], end=' ')


from sys import stdin, stdout
from collections import defaultdict, deque
nmbr = lambda : int(stdin.readline())
lst = lambda : list(map(int, stdin.readline().split()))

def bfs(src):
	q = deque()
	q.append(src)
	vis[src] = 1
	while q:
		cur = q.popleft()
		for neigh in g[cur]:
			if not vis[neigh]:
				q.append(neigh)
				parent[neigh] = cur
				vis[neigh] = 1
for _ in range(1):
	(n, r1, r2) = lst()
	g = defaultdict(list)
	a = lst()
	c = 1
	for node in a:
		if c == r1:
			c += 1
		g[c] += [node]
		g[node] += [c]
		c += 1
	parent = [-1] * (n + 1)
	vis = [0] * (1 + n)
	bfs(r2)
	for i in range(1, n + 1):
		if i == r2:
			continue
		stdout.write(str(parent[i]) + ' ')


import sys
from array import array

def input():
	return sys.stdin.buffer.readline().decode('utf-8')
(n, r1, r2) = map(int, input().split())
adj = [[] for _ in range(n + 1)]
v = 1
for u in map(int, input().split()):
	if v == r1:
		v += 1
	adj[v].append(u)
	adj[u].append(v)
	v += 1
ans = [0] * (n + 1)
ans[r2] = -1
stack = [r2]
while stack:
	v = stack.pop()
	for dest in adj[v]:
		if ans[dest] != 0:
			continue
		ans[dest] = v
		stack.append(dest)
ans = [x for x in ans if x > 0]
print(*ans)


def findPath(fr, to, parent):
	path = [to]
	current = to
	while current != fr:
		path.append(parent[current])
		current = parent[current]
	return path
(n, r1, r2) = map(int, input().split())
idx = lambda i: i if i < r1 else i + 1
oldParents = dict(((idx(i + 1), int(city)) for (i, city) in enumerate(input().split())))
oldParents[r1] = r1
path = findPath(r1, r2, oldParents)
newParents = oldParents
for i in range(1, len(path)):
	newParents[path[i]] = path[i - 1]
for i in range(1, n + 1):
	if i != r2:
		print(newParents[i], end=' ')


from collections import defaultdict, Counter, deque
import os
import sys
from io import BytesIO, IOBase
ii = lambda : int(input())
lmii = lambda : list(map(int, input().split()))
slmii = lambda : sorted(map(int, input().split()))
li = lambda : list(input())
mii = lambda : map(int, input().split())
msi = lambda : map(str, input().split())

def gcd(a, b):
	if b == 0:
		return a
	return gcd(b, a % b)

def lcm(a, b):
	return a * b // gcd(a, b)

def main():
	(n, r1, r2) = mii()
	a = lmii()
	i = 1
	adj = defaultdict(list)
	while i <= n:
		if i == r1:
			i += 1
		if i - 2 >= n - 1:
			break
		if i > r1:
			adj[i].append(a[i - 2])
			adj[a[i - 2]].append(i)
		else:
			adj[i].append(a[i - 1])
			adj[a[i - 1]].append(i)
		i += 1
	visited = defaultdict(int)
	stk = [r2]
	par = defaultdict(int)
	visited[r2] = 1
	while stk:
		elem = stk.pop()
		for i in adj[elem]:
			if not visited[i]:
				par[i] = elem
				visited[i] = 1
				stk.append(i)
	for i in sorted(par):
		if par[i]:
			print(par[i], end=' ')
	print()
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


(n, r1, r2) = map(int, input().split())

def dfs(u):
	x = None
	while x != r1:
		tmp = prev[u]
		prev[u] = x
		x = u
		u = tmp
prev = [0] + list(map(int, input().split()))
prev.insert(r1, None)
dfs(r2)
prev.remove(0)
prev.remove(None)
print(*prev)


import os
import sys

def list2d(a, b, c):
	return [[c] * b for i in range(a)]

def list3d(a, b, c, d):
	return [[[d] * c for j in range(b)] for i in range(a)]

def list4d(a, b, c, d, e):
	return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]

def ceil(x, y=1):
	return int(-(-x // y))

def Yes():
	print('Yes')

def No():
	print('No')

def YES():
	print('YES')

def NO():
	print('NO')
INF = 10 ** 18
MOD = 10 ** 9 + 7
import threading
threading.stack_size(10 ** 8)
from types import GeneratorType

def bootstrap(func, stack=[]):

	def wrapped_function(*args, **kwargs):
		if stack:
			return func(*args, **kwargs)
		else:
			call = func(*args, **kwargs)
			while True:
				if type(call) is GeneratorType:
					stack.append(call)
					call = next(call)
				else:
					stack.pop()
					if not stack:
						break
					call = stack[-1].send(call)
			return call
	return wrapped_function
Ri = lambda : [int(x) for x in sys.stdin.readline().split()]
ri = lambda : sys.stdin.readline().strip()

def solve():
	(n, r1, r2) = Ri()
	r1 -= 1
	r2 -= 1
	g = [[] for i in range(n)]
	temp = Ri()
	temp = [i - 1 for i in temp]
	ans = 0
	for i in range(n):
		if i == r1:
			ans += 1
			continue
		g[i].append(temp[i - ans])
		g[temp[i - ans]].append(i)
	ans = [0] * n

	@bootstrap
	def dfs(cur, par):
		for child in g[cur]:
			if child == par:
				continue
			ans[child] = cur + 1
			yield dfs(child, cur)
		yield
	dfs(r2, -1)
	for i in range(len(ans)):
		if ans[i] == 0:
			ans = ans[:i] + ans[i + 1:]
			break
	for i in ans:
		print(i, end=' ')
	print()
solve()


(n, ro, rk) = map(int, input().split())
t = [0] + list(map(int, input().split()))
t.insert(ro, 0)
(r, p) = ([], rk)
while p:
	r.append(p)
	p = t[p]
for i in range(1, len(r)):
	t[r[i]] = r[i - 1]
t.pop(rk)
print(' '.join(map(str, t[1:])))