CF34D Road Map

伯兰德有 $n$ 座城市。每座城市都有一个编号，编号为 $1$ 到 $n$ 的整数。首都的编号为 $r_{1}$。伯兰德所有的道路均为双向道路。道路系统保证从首都到每座城市恰好有一条路径，即整个道路系统构成一棵树。在伯兰德的史书记载中，路网是这样保存的：对于每个城市 $i$（首都除外），都会记录一个数字 $p_{i}$，表示从首都到 $i$ 的路径上倒数第二个城市的编号。 有一天，伯兰德国王 Berl XXXIV 决定将首都从 $r_{1}$ 号城市迁到 $r_{2}$ 号城市。显然，原来的路网表示方法已经不再适用。请你帮助国王，根据上述的方法，找出以新首都为根节点后的路网表示。

第一行包含三个用空格分隔的整数 $n$、$r_{1}$ 和 $r_{2}$（$2 \leq n \leq 5 \cdot 10^{4}$，$1 \leq r_{1} \neq r_{2} \leq n$），分别表示伯兰德的城市数、原首都编号和新首都编号。 第二行包含 $n-1$ 个用空格分隔的整数，表示原路网的记录。对于每个编号不等于 $r_{1}$ 的城市，给出一个整数 $p_{i}$，表示从首都到城市 $i$ 路径上的倒数第二个城市的编号。所有城市按编号递增顺序给出。

输出 $n-1$ 个整数，按同样格式输出以新首都为根节点后的路网记录。

由 ChatGPT 5 翻译