Road Map

2000ms

262144K

Description:

There are n cities in Berland. Each city has its index — an integer number from 1 to n. The capital has index r₁. 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 p_i — 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 r₁ to city r₂. 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, r₁, r₂ (2 ≤ n ≤ 5·10⁴, 1 ≤ r₁ ≠ r₂ ≤ 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 r₁, there is given integer p_i — 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.

Sample Input:

3 2 3
2 2

Sample Output:

2 3

Sample Input:

6 2 4
6 1 2 4 2

Sample Output:

6 4 1 4 2

Informação

Provedor Codeforces

Código CF34D