CF765D.Artsem and Saunders

Artsem has a friend Saunders from University of Chicago. Saunders presented him with the following problem.

Let [n] denote the set {1, ..., n}. We will also write f: [x] → [y] when a function f is defined in integer points 1, ..., x, and all its values are integers from 1 to y.

Now then, you are given a function f: [n] → [n]. Your task is to find a positive integer m, and two functions g: [n] → [m], h: [m] → [n], such that g(h(x)) = x for all , and h(g(x)) = f(x) for all , or determine that finding these is impossible.

阿尔特谢姆有一位来自芝加哥大学的朋友桑德斯。桑德斯向他提出了如下问题。

记 [n] 为集合 {1, ..., n}。当函数 f 在整数点 1, ..., x 上有定义，且其所有函数值均为 1 到 y 之间的整数时，我们也写作 f: [x] → [y]。

现在，给定一个函数 f: [n] → [n]。你的任务是：找出一个正整数 m，以及两个函数 g: [n] → [m] 和 h: [m] → [n]，使得对所有 均有 g(h(x)) = x，且对所有 均有 h(g(x)) = f(x)；若不存在这样的 m, g, h，则判定其不可能。

The first line contains an integer n (1 ≤ n ≤ 105).

The second line contains n space-separated integers — values f(1), ..., f(n) (1 ≤ f(i) ≤ n).

第一行包含一个整数 $n$（$1 \leq n \leq 10^5$）。

第二行包含 $n$ 个以空格分隔的整数——即函数值 $f(1),\ ..., \ f(n)$（$1 \leq f(i) \leq n$）。

If there is no answer, print one integer -1.

Otherwise, on the first line print the number m (1 ≤ m ≤ 106). On the second line print n numbers g(1), ..., g(n). On the third line print m numbers h(1), ..., h(m).

If there are several correct answers, you may output any of them. It is guaranteed that if a valid answer exists, then there is an answer satisfying the above restrictions.

如果不存在答案，输出一个整数 $-1$。

否则，第一行输出数字 $m$（$1 \le m \le 10^6$）；第二行输出 $n$ 个数 $g(1),\ ..., \ g(n)$；第三行输出 $m$ 个数 $h(1),\ ..., \ h(m)$。

若存在多个正确答案，可输出其中任意一个。题目保证：若存在合法答案，则必存在满足上述限制的解。