找到环

问题描述

给定一个有 \(N\) 个顶点、\(N\) 条边的有向图。 第 \(i\) 条边从顶点 \(i\) 指向顶点 \(A_i\)。（由约束可保证 \(i \ne A_i\)。）

请你找出一个不包含重复顶点的有向环。在本题给定的约束下，可以证明答案一定存在。

注释

在本题中，"有向环"定义为满足以下全部条件的顶点序列 \(B=(B_1, B_2, \dots, B_M)\)：

• \(M \ge 2\)
• 存在边从 \(B_i\) 指向 \(B_{i+1}\)（\(1 \le i \le M-1\)）
• 存在边从 \(B_M\) 指向 \(B_1\)
• 若 \(i \ne j\)，则 \(B_i \ne B_j\)

约束

• 输入均为整数
• \(2 \le N \le 2 \times 10^5\)
• \(1 \le A_i \le N\)
• \(A_i \ne i\)

输入

以下列格式从标准输入给出：

N
A_1 A_2 … A_N

输出

按以下格式输出：

M
B_1 B_2 … B_M

其中 \(M\) 是输出的有向环的顶点数，\(B_i\) 是该有向环的第 \(i\) 个顶点。输出必须满足：

• \(2 \le M\)
• \(B_{i+1} = A_{B_i}\)（\(1 \le i \le M-1\)）
• \(B_1 = A_{B_M}\)
• \(B_i \ne B_j\)（当 \(i \ne j\)）

若满足条件的答案不止一个，输出任意一个均可判定为正确。

输入样例 1

7
6 7 2 1 3 4 5

输出样例 1

4
7 5 3 2

解释：\(7 \to 5 \to 3 \to 2 \to 7\) 确实构成一个有向环。

其他同样正确的输出示例：

4
2 7 5 3

3
4 1 6

注意：图不一定连通。

输入样例 2

2
2 1

输出样例 2

2
1 2

解释：这是 \(1 \to 2\) 与 \(2 \to 1\) 两条边都存在的情况，因此 \(1 \to 2 \to 1\) 是一个合法的有向环。 （对应的图中以 \(1 \leftrightarrow 2\) 表示两方向边同时存在。）

输入样例 3

8
3 7 4 7 3 3 8 2

输出样例 3

3
2 7 8