103112: [Atcoder]ABC311 C - Find it!

Problem Statement

There is a directed graph with $N$ vertices and $N$ edges.
The $i$-th edge goes from vertex $i$ to vertex $A_i$. (The constraints guarantee that $i \neq A_i$.)
Find a directed cycle without the same vertex appearing multiple times.
It can be shown that a solution exists under the constraints of this problem.

Notes

The sequence of vertices $B = (B_1, B_2, \dots, B_M)$ is called a directed cycle when all of the following conditions are satisfied:

• $M \geq 2$
• The edge from vertex $B_i$ to vertex $B_{i+1}$ exists. $(1 \leq i \leq M-1)$
• The edge from vertex $B_M$ to vertex $B_1$ exists.
• If $i \neq j$, then $B_i \neq B_j$.

Constraints

• All input values are integers.
• $2 \le N \le 2 \times 10^5$
• $1 \le A_i \le N$
• $A_i \neq i$

Input

The input is given from Standard Input in the following format:

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

Output

Print a solution in the following format:

$M$
$B_1$ $B_2$ $\dots$ $B_M$

$M$ is the number of vertices, and $B_i$ is the $i$-th vertex in the directed cycle.
The following conditions must be satisfied:

• $2 \le M$
• $B_{i+1} = A_{B_i}$ ( $1 \le i \le M-1$ )
• $B_{1} = A_{B_M}$
• $B_i \neq B_j$ ( $i \neq j$ )

If multiple solutions exist, any of them will be accepted.

Sample Input 1

7
6 7 2 1 3 4 5

Sample Output 1

4
7 5 3 2

$7 \rightarrow 5 \rightarrow 3 \rightarrow 2 \rightarrow 7$ is indeed a directed cycle.

Here is the graph corresponding to this input:

Here are other acceptable outputs:

4
2 7 5 3

3
4 1 6

Note that the graph may not be connected.

Sample Input 2

2
2 1

Sample Output 2

2
1 2

This case contains both of the edges $1 \rightarrow 2$ and $2 \rightarrow 1$.
In this case, $1 \rightarrow 2 \rightarrow 1$ is indeed a directed cycle.

Here is the graph corresponding to this input, where $1 \leftrightarrow 2$ represents the existence of both $1 \rightarrow 2$ and $2 \rightarrow 1$:

Sample Input 3

8
3 7 4 7 3 3 8 2

Sample Output 3

3
2 7 8

Here is the graph corresponding to this input:

问题描述

有一个有向图，有N个顶点和N条边。
第i条边从顶点i指向顶点$A_i$。（条件保证了$i \neq A_i$）
找到一个没有重复顶点的有向环。
可以证明在本问题的约束条件下，解是存在的。

注释

顶点序列$B = (B_1, B_2, \dots, B_M)$称为有向环，当满足以下所有条件时：

• $M \geq 2$
• 从顶点$B_i$到顶点$B_{i+1}$的边存在。$(1 \leq i \leq M-1)$
• 从顶点$B_M$到顶点$B_1$的边存在。
• 如果$i \neq j$，则$B_i \neq B_j$。

约束条件

• 所有输入值都是整数。
• $2 \le N \le 2 \times 10^5$
• $1 \le A_i \le N$
• $A_i \neq 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}$
• $B_i \neq B_j$ ( $i \neq j$ )

如果有多个解存在，任何解都将被接受。

样例输入1

7
6 7 2 1 3 4 5

样例输出1

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
2 1

样例输出2

2
1 2

此例包含边$1 \rightarrow 2$和$2 \rightarrow 1$。
在这种情况下，$1 \rightarrow 2 \rightarrow 1$确实是一个有向环。

下面是对应于此输入的图，其中$1 \leftrightarrow 2$表示边$1 \rightarrow 2$和$2 \rightarrow 1$都存在：

样例输入3

8
3 7 4 7 3 3 8 2

样例输出3

3
2 7 8

下面是对应于此输入的图：