← 返回题目列表

Codeforces · 698/B

B. 修一棵树

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

树是没有环的无向连通图。

让我们考虑一棵有 n 个顶点的有根无向树,编号为 1 到 n。有很多方法可以表示这样的树。一种方法是创建一个包含 n 个整数 p1、p2、...、pn 的数组,其中 pi 表示顶点 i 的父节点(这里,为方便起见,根被视为其自己的父节点)。

对于这个有根树,数组 p 是 [2, 3, 3, 2]。

给定一个序列 p1, p2, ..., pn,我们能够恢复一棵树:

1. 必须有一个索引 r 使得 pr = r。顶点r是树的根。
2. 对于所有其他 n - 1 个顶点 i,顶点 i 和顶点 pi 之间存在一条边。

如果所描述的过程生成一些(任何)有根树,则序列 p1, p2, ..., pn 被称为有效。例如,对于 n = 3 的序列 (1,2,2)、(2,3,1) 和 (2,1,3) 无效。

给定一个序列 a1, a2, ..., an,不一定有效。您的任务是更改元素的最小数量,以获得有效的序列。打印最小更改次数以及该更改次数之后的有效序列示例。如果在最少的更改次数内可以实现许多有效的序列,则打印其中的任何一个。

输入

输入的第一行包含一个整数 n (2 ≤ n ≤ 200 000) - 树中的顶点数。

第二行包含 n 个整数 a1, a2, ..., an (1 ≤ ai ≤ n)。

输出

在第一行中打印要更改的最小元素数,以获得有效的序列。

在第二行中,打印从 (a1, a2, ..., an) 中以最少的更改次数可能获得的任何有效序列。如果有很多这样的序列,则任何一个都会被接受。

示例

输入 #1

4
2 3 3 4

输出 #1

1
2 3 4 4

输入 #2

5
3 2 2 5 3

输出 #2

0
3 2 2 5 3

输入 #3

8
2 3 5 4 1 6 6 7

输出 #3

2
2 3 7 8 1 6 6 7

注意

在第一个示例中,更改一个元素就足够了。在提供的输出中,序列表示以顶点 4 为根的树(因为 p4 = 4),您可以在下面的左图中看到。其他正确的解决方案之一是序列 2 3 3 2,表示以顶点 3 为根的树(下右图)​​。在这两幅图中,根部都被涂成红色。

在第二个示例中,给定序列已经有效。