C - Find it! Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 350 点

問題文

N 頂点 N 辺の有向グラフがあります。
i 番目の辺は頂点 i から 頂点 A_i に伸びます。 ( i \neq 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 \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

この入力に対応するグラフは以下の通りです。

Score : 350 points

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: