Artsem 有一位来自芝加哥大学的朋友 Saunders。桑德斯向他提出了以下问题。
设 [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 对于所有 $$x \in [m]$$,并且 h(g(x)) = f(x) 对于所有 $$x \in [n]$$,或者确定找到这些是不可能的。
输入
第一行包含一个整数 n (1 ≤ n ≤ 105)。
第二行包含 n 个空格分隔的整数 — 值 f(1), ..., f(n) (1 ≤ f(i) ≤ n)。
输出
如果没有答案,则打印一个整数-1。
否则,在第一行打印数字 m (1 ≤ m ≤ 106)。在第二行打印 n 个数字 g(1), ..., g(n)。在第三行打印 m 个数字 h(1), ..., h(m)。
如果有多个正确答案,则可以输出其中任何一个。保证如果存在有效答案,则存在满足上述限制的答案。
示例
输入 #1
3 1 2 3
输出 #1
3 1 2 3 1 2 3
输入 #2
3 2 2 2
输出 #2
1 1 1 1 2
输入 #3
2 2 1
输出 #3
-1