P24554 [AtCoder] 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$.

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.

Constraints

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

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:

输入格式

见题面 Input 部分

输出格式

见题面 Output 部分

样例输入
7 6 7 2 1 3 4 5
样例输出
4 7 5 3 2