RANJAN05 - Road Map

no tags 

There are x villages in Andhere Nagar. Each village has its index — an integer number from 1 to x. The capital has index a. All the roads in Andhere Nagar 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 Andhere Nagar's chronicles the road map is kept in the following way: for each village i, different from the capital, there is kept number pi — index of the last village on the way from the capital to i.

Once the king of Andhere Nagar, Choupat Raja, decided to move the capital from village a to village b. Naturally, after this the old representation of the road map in Andhere Nagar '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 x, a, b (2 ≤ x ≤ 5·104, 1 ≤ a ≠ b ≤ n) — amount of villages in Andhere Nagar, index of the old capital and index of the new one, correspondingly.

The following line contains x - 1 space-separated integers — the old representation of the road map. For each city, apart from a, 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 x - 1 numbers — new representation of the road map in the same format.

Example 1

Input:
3 2 3
2 2

Output:
2 3

Example 2

Input:
6 2 4
6 1 2 4 2

Output:
6 4 1 4 2

hide comments
smso: 2022-08-09 09:31:43

Graph for example 2:
3 <-> 1 <-> 6<-> 2 <-> 4 <-> 5
Biggest hurdle is the vague problem statements.

Sushovan Sen: 2020-10-15 11:47:01

Problem is easier than the number of successful solvers suggest

Aditya Kumar Akash: 2013-07-31 09:30:19

I am getting wrong answer for this question while i submit in spoj, but for all the test cases i manually checked i get correct answer on my system. Any tricky test case for this ? please help.


Added by:abhiranjan
Date:2010-10-23
Time limit:1s-1.580s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:C CSHARP C++ 4.3.2 CPP JAVA
Resource:IIITM Local Contest