← 返回题目列表

Codeforces · 765/D

D. 阿瑟姆和桑德斯

中文机器翻译题面 查看原题

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