Permutation
Time limit2sMemory limit128 MB
Given a permutation B satisfying B[A[A[i]]] = i, reconstruct a permutation A that produces it, or report that none exists.
- Level
Medium7 of 10
- Topics
- Math, Number theory, Graph, Combinatorics
- Solved
- No attempts yet
Problem
There is an array A[1..N] containing each integer from 1 to N exactly once. An array B[1..N] is created from A by the following rule.
B[A[A[i]]] = i (1 <= i <= N)
Given B, find an array A that could have produced it. Such an array may not exist. If two or more arrays A are possible, output any one of them.
Input
The first line contains N, the number of elements in B. (1 <= N <= 20,000)
Each of the next N lines contains one value, B[1], ..., B[N], in order.
Output
If a solution exists, print N on the first line. Then print A[1], ..., A[N], one value per line, in order.
If no solution exists, print 0 on the first line.