D. Artsem and Saunders

Artsem 有一个来自芝加哥大学的朋友 Saunders。Saunders 给了他以下问题。 令 #cf_span[[n]] 表示集合 #cf_span[{1, ..., n}]。我们也将写 #cf_span[f: [x] → [y]]，表示函数 #cf_span[f] 定义在整数点 #cf_span[1], ..., #cf_span[x] 上，且其所有取值均为 1 到 #cf_span[y] 之间的整数。 现在，给定一个函数 #cf_span[f: [n] → [n]]。你的任务是找到一个正整数 #cf_span[m]，以及两个函数 #cf_span[g: [n] → [m]] 和 #cf_span[h: [m] → [n]]，使得对所有 #cf_span[x] 满足 #cf_span[g(h(x)) = x]，且对所有 #cf_span[x] 满足 #cf_span[h(g(x)) = f(x)]；或者判断这样的函数不存在。 第一行包含一个整数 #cf_span[n] (#cf_span[1 ≤ n ≤ 10^5])。 第二行包含 #cf_span[n] 个用空格分隔的整数 —— 值 #cf_span[f(1), ..., f(n)] (#cf_span[1 ≤ f(i) ≤ n])。 如果无解，请输出一个整数 _-1_。 否则，第一行输出数字 #cf_span[m] (#cf_span[1 ≤ m ≤ 10^6])。第二行输出 #cf_span[n] 个数 #cf_span[g(1), ..., g(n)]。第三行输出 #cf_span[m] 个数 #cf_span[h(1), ..., h(m)]。 如果有多个正确答案，你可以输出任意一个。题目保证，若存在合法答案，则一定存在满足上述限制的答案。 ## Input 第一行包含一个整数 #cf_span[n] (#cf_span[1 ≤ n ≤ 10^5])。第二行包含 #cf_span[n] 个用空格分隔的整数 —— 值 #cf_span[f(1), ..., f(n)] (#cf_span[1 ≤ f(i) ≤ n])。 ## Output 如果无解，请输出一个整数 _-1_。否则，第一行输出数字 #cf_span[m] (#cf_span[1 ≤ m ≤ 10^6])。第二行输出 #cf_span[n] 个数 #cf_span[g(1), ..., g(n)]。第三行输出 #cf_span[m] 个数 #cf_span[h(1), ..., h(m)]。如果有多个正确答案，你可以输出任意一个。题目保证，若存在合法答案，则一定存在满足上述限制的答案。 [samples]

Let $ f: [n] \to [n] $ be given. We seek a positive integer $ m $, and functions $ g: [n] \to [m] $, $ h: [m] \to [n] $, such that: 1. $ g \circ h = \text{id}_{[m]} $, i.e., $ g(h(x)) = x $ for all $ x \in [m] $, 2. $ h \circ g = f $, i.e., $ h(g(x)) = f(x) $ for all $ x \in [n] $. Equivalently: - $ h $ is injective (since $ g \circ h = \text{id} $), - $ g $ is surjective (since $ g \circ h = \text{id} $), - $ f = h \circ g $, so $ f $ factors through $ g $ and $ h $. This is possible if and only if $ f $ is idempotent up to bijection on its image — more precisely, if the restriction of $ f $ to its image $ f([n]) $ is a permutation of $ f([n]) $. That is: Let $ S = f([n]) \subseteq [n] $. Then $ f|_S: S \to S $ must be a bijection. **Necessary and sufficient condition:** $ f(f(x)) = f(x) $ for all $ x \in [n] $. *(Equivalently: $ f $ is a retraction — its restriction to its image is the identity.)* --- **If condition fails:** Output $-1$. **If condition holds:** Let $ m = |S| = |\text{image}(f)| $. Let $ S = \{ s_1, s_2, \dots, s_m \} $, sorted in increasing order. Define $ h: [m] \to [n] $ by $ h(i) = s_i $. Define $ g: [n] \to [m] $ by $ g(x) = i $ where $ s_i = f(x) $. Then: - $ h(g(x)) = h(i) = s_i = f(x) $ → $ h \circ g = f $, - $ g(h(i)) = g(s_i) = j $ where $ f(s_i) = s_j $. But since $ f(s_i) = s_i $ (as $ f|_S = \text{id} $), then $ j = i $, so $ g(h(i)) = i $ → $ g \circ h = \text{id}_{[m]} $. Thus, the construction works. --- **Formal Output:** If $ f(f(x)) \ne f(x) $ for some $ x \in [n] $, output $-1$. Else: - Let $ S = \{ f(x) \mid x \in [n] \} $, and $ m = |S| $. - Let $ h: [m] \to [n] $ be the strictly increasing enumeration of $ S $: $ h(1) < h(2) < \dots < h(m) $, with $ h(i) \in S $. - Let $ g: [n] \to [m] $ be defined by $ g(x) = \text{the index } i \text{ such that } f(x) = h(i) $. Output $ m $, then $ g(1), \dots, g(n) $, then $ h(1), \dots, h(m) $.