Autosynthesis
Contest: Codeforces Round 902 (Div. 1, based on COMPFEST 15 - Final Round)
Difficulty rating: 2100
Tags: constructive algorithms, dfs and similar, graphs, greedy, sortings

Chaneka writes down an array $$$a$$$ of $$$n$$$ positive integer elements. Initially, all elements are not circled. In one operation, Chaneka can circle an element. It is possible to circle the same element more than once.

After doing all operations, Chaneka makes a sequence $$$r$$$ consisting of all uncircled elements of $$$a$$$ following the order of their indices.

Chaneka also makes another sequence $$$p$$$ such that its length is equal to the number of operations performed and $$$p_i$$$ is the index of the element that is circled in the $$$i$$$-th operation.

Chaneka wants to do several operations such that sequence $$$r$$$ is equal to sequence $$$p$$$. Help her achieve this, or report if it is impossible! Note that if there are multiple solutions, you can print any of them.

Input format:
The first line contains a single integer $$$n$$$ ($$$1 \leq n \leq 2\cdot10^5$$$) — the size of array $$$a$$$.

The second line contains $$$n$$$ integers $$$a_1,a_2,a_3,\ldots,a_n$$$ ($$$1\leq a_i\leq n$$$).

Output format:
A single line containing $$$-1$$$ if it is impossible.

Otherwise, the output consists of two lines. The first line contains an integer $$$z$$$ representing the number of operations performed. The second line contains $$$z$$$ integers, the $$$i$$$-th integer represents the index of the element circled in the $$$i$$$-th operation. If there are multiple solutions, you can print any of them.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
In the first example, doing the operations like the example output gives the following results:

- Element $$$a_2$$$ gets circled $$$1$$$ time.
- Element $$$a_3$$$ gets circled $$$2$$$ times.
- The uncircled elements (ordered by their indices) are $$$a_1$$$, $$$a_4$$$, and $$$a_5$$$. So $$$r=[3,2,3]$$$.
- $$$p=[3,2,3]$$$

Therefore, $$$r=p$$$.

In the second example, it is impossible.

Example input:
5
3 4 2 2 3

Example output:
3
3 2 3

Example input:
3
1 2 3

Example output:
-1

Editorial:
Let's say we have coloured each element of $$$a$$$ into black or white and we want to find a sequence of operations that results in all black elements being circles and all white elements being uncircled. Notice that such a sequence exists if and only if the following holds:
• For each black element, there must exist at least one white element with a value equal to the index of that black element. (There must be a value in $$$p$$$ that circles that black element)
• For each white element, there cannot be any white element with a value equal to the index of that black element. (There cannot be a value in $$$p$$$ that circles that white element)
Construct a directed graph of $$$n$$$ vertices and $$$n$$$ directed edges. Each edge $$$i$$$ is from vertex $$$i$$$ to vertex $$$a_i$$$. For an edge from $$$x$$$ to $$$y$$$, define $$$x$$$ as a child of $$$y$$$ and define $$$y$$$ as a parent of $$$x$$$. Notice that each vertex only has exactly one parent. This means that each connected component in the graph looks like a directed rooted tree with a cycle of arbitrary size at the root.
Let each vertex $$$i$$$ represent whether element $$$a_i$$$ is white or black. From the knowledge above, we can get the following for determining the colour of a certain vertex:
• If it has at least one white child, then it must be black.
• If it has no white children, then it must be white.
This means we can determine the colour of a vertex once we have determined the colours of its children. Additionally, once there is at least one white child, we can guarantee the vertex to be black.
We can solve this by maintaining a queue. First, fill the queue with each vertex with no children ($$$0$$$ indegree). When we process a vertex in the queue, determine the colour using the rules above, and then decrease the indegree of its parent (as if the current processed vertex is deleted from the graph). If the indegree of the parent reaches $$$0$$$, add the parent to the queue. In particular, if the current vertex is white, we can immediately determine the colour of the parent to be black and add it to the queue as well.
The process stops once there are no vertices left with $$$0$$$ indegrees and none of the remaining vertices has a white child. Because of the special structure of the graph, once this happens, the remaining graph only contains zero or more disjoint cycles.
Let's solve each cycle independently. Notice that if a cycle is of even length, we can colour its vertices black and white alternatingly. However, if a cycle is of odd length, it is impossible to colour it.
Time complexity: $$$O(n)$$$