実行時間制限: 2 sec / メモリ制限: 1024 MB
配点 : 200 点
問題文
人 1 、人 2 、\ldots 、人 N と番号をつけられた N 人の人がいます。
N 人は、人 1 、人 2 、\ldots 、人 N の順番に下記の行動をちょうど 1 回ずつ行います。
- 人 i 自身がまだ一度も番号を呼ばれていないなら、人 A_i の番号を呼ぶ。
最後まで番号を一度も呼ばれない人全員の番号を昇順に列挙してください。
制約
- 2 \leq N \leq 2 \times 10^5
- 1 \leq A_i \leq N
- A_i \neq i
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N A_1 A_2 \ldots A_N
出力
下記の形式にしたがって、最後まで番号を一度も呼ばれない人全員の番号を昇順に列挙せよ。
K X_1 X_2 \ldots X_K
すなわち、まず 1 行目に、最後まで番号を一度も呼ばれない人の人数 K を出力し、 2 行目に、最後まで番号を一度も呼ばれない人全員の番号を昇順に並べた列 (X_1, X_2, \ldots, X_K) を空白区切りで出力せよ。
入力例 1
5 3 1 4 5 4
出力例 1
2 2 4
5 人の行動は下記の通りです。
- 人 1 はまだ番号を一度も呼ばれていないので、人 1 は人 3 の番号を呼びます。
- 人 2 はまだ番号を一度も呼ばれていないので、人 2 は人 1 の番号を呼びます。
- 人 3 はすでに人 1 によって番号を呼ばれているので、何もしません。
- 人 4 はまだ番号を一度も呼ばれていないので、人 4 は人 5 の番号を呼びます。
- 人 5 はすでに人 4 によって番号を呼ばれているので、何もしません。
よって、最後まで番号を一度も呼ばれないのは人 2 と人 4 です。
入力例 2
20 9 7 19 7 10 4 13 9 4 8 10 15 16 3 18 19 12 13 2 12
出力例 2
10 1 2 5 6 8 11 14 17 18 20
Score : 200 points
Problem Statement
There are N people whose IDs are 1, 2, \ldots, and N.
Each of person 1, person 2, \ldots, and person N performs the following action once in this order:
- If person i's ID has not been called out yet, call out person A_i's ID.
Enumerate the IDs of all the people whose IDs are never called out until the end in ascending order.
Constraints
- 2 \leq N \leq 2 \times 10^5
- 1 \leq A_i \leq N
- A_i \neq i
- All values in the input are integers.
Input
The input is given from Standard Input in the following format:
N A_1 A_2 \ldots A_N
Output
Enumerate the IDs of all the people whose IDs are not called out until the end in ascending order in the following format:
K X_1 X_2 \ldots X_K
In other words, the first line should contain the number of people, K, whose IDs are never called out until the end; the second line should contain the sequence (X_1, X_2, \ldots, X_K) of IDs of such people in ascending order, with spaces in between.
Sample Input 1
5 3 1 4 5 4
Sample Output 1
2 2 4
The five people's actions are as follows.
- Person 1's ID has not been called out yet, so person 1 calls out person 3's ID.
- Person 2's ID has not been called out yet, so person 2 calls out person 1's ID.
- Person 3's ID has already been called out by person 1, so nothing happens.
- Person 4's ID has not been called out yet, so person 4 calls out person 5's ID.
- Person 5's ID has already been called out by person 4, so nothing happens.
Therefore, person 2 and 4's IDs are not called out until the end.
Sample Input 2
20 9 7 19 7 10 4 13 9 4 8 10 15 16 3 18 19 12 13 2 12
Sample Output 2
10 1 2 5 6 8 11 14 17 18 20