← 返回题目列表

Codeforces · 34/D

D. 路线图

中文机器翻译题面 查看原题

Berland 有 n 个城市。每个城市都有其索引——从 1 到 n 的整数。首都的指数为r1。贝尔兰的所有道路都是双向的。道路系统是这样的,从首都到每个城市只有一条路径,即道路图看起来像一棵树。在 Berland 的编年史中,路线图是这样保存的:对于每个不同于首都的城市 i,保存有编号 pi——从首都到 i 的路上最后一个城市的索引。

一旦贝尔兰国王贝尔三十四世决定将首都从城市r1迁至城市r2。当然,此后贝尔兰德编年史中对路线图的旧表述就变得不正确了。请帮助国王按照上述方式找到路线图的新表示。

输入

第一行包含三个空格分隔的整数 n, r1, r2 (2 ≤ n ≤ 5·104, 1 ≤ r1 ≠ r2 ≤ n) — Berland 的城市数量、旧首都索引和新首都索引。

以下行包含 n - 1 个空格分隔的整数 — 路线图的旧表示形式。对于每个城市,除了r1之外,还给出了整数pi——从首都到城市i的最后一个城市的索引。所有城市均按指数递增的顺序进行描述。

输出

输出 n - 1 个数字 — 以相同格式新表示路线图。

示例

输入 #1

3 2 3
2 2

输出 #1

2 3

输入 #2

6 2 4
6 1 2 4 2

输出 #2

6 4 1 4 2