找出有向环

题目描述

给定一个具有 $N$ 个顶点和 $N$ 条边的有向图。

第 $i$ 条边从顶点 $i$ 连向顶点 $A_i$。(约束保证 $i \neq A_i$。)

请找出一个不含重复顶点的有向环。

可以证明,在该题的约束下解一定存在。

输入格式

输入按以下格式从标准输入给出:

$N$
$A_1$ $A_2$ $\dots$ $A_N$

输出格式

按以下格式输出一个解:

$M$
$B_1$ $B_2$ $\dots$ $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}$
• 当 $i \neq j$ 时,$B_i \neq B_j$

如果有多个解,输出任意一个均可。

样例

7
6 7 2 1 3 4 5

4
7 5 3 2

$7 \rightarrow 5 \rightarrow 3 \rightarrow 2 \rightarrow 7$ 确实是一个有向环。

其他可接受的输出还有:

4
2 7 5 3

3
4 1 6

注意,图可能不连通。

2
2 1

2
1 2

该样例同时包含边 $1 \rightarrow 2$ 和 $2 \rightarrow 1$。

此时,$1 \rightarrow 2 \rightarrow 1$ 确实是一个有向环。

8
3 7 4 7 3 3 8 2

3
2 7 8

数据范围

• 输入中的所有值均为整数。
• $2 \le N \le 2 \times 10^5$
• $1 \le A_i \le N$
• $A_i \neq 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 \neq j$ 时,$B_i \neq B_j$。

答案不唯一,输出任意合法解即可。