{"raw_statement":[{"iden":"statement","content":"Artsem has a friend Saunders from University of Chicago. Saunders presented him with the following problem.\n\nLet \\[_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_.\n\nNow 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."},{"iden":"input","content":"The first line contains an integer _n_ (1 ≤ _n_ ≤ 105).\n\nThe second line contains _n_ space-separated integers — values _f_(1), ..., _f_(_n_) (1 ≤ _f_(_i_) ≤ _n_)."},{"iden":"output","content":"If there is no answer, print one integer _\\-1_.\n\nOtherwise, 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_).\n\nIf 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."},{"iden":"examples","content":"Input\n\n3\n1 2 3\n\nOutput\n\n3\n1 2 3\n1 2 3\n\nInput\n\n3\n2 2 2\n\nOutput\n\n1\n1 1 1\n2\n\nInput\n\n2\n2 1\n\nOutput\n\n\\-1"}],"translated_statement":[{"iden":"statement","content":"Artsem 有一个来自芝加哥大学的朋友 Saunders。Saunders 给了他以下问题。\n\n令 #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] 之间的整数。\n\n现在，给定一个函数 #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)]；或者判断这样的函数不存在。\n\n第一行包含一个整数 #cf_span[n] (#cf_span[1 ≤ n ≤ 10^5])。\n\n第二行包含 #cf_span[n] 个用空格分隔的整数 —— 值 #cf_span[f(1), ..., f(n)] (#cf_span[1 ≤ f(i) ≤ n])。\n\n如果无解，请输出一个整数 _-1_。\n\n否则，第一行输出数字 #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)]。\n\n如果有多个正确答案，你可以输出任意一个。题目保证，若存在合法答案，则一定存在满足上述限制的答案。"},{"iden":"input","content":"第一行包含一个整数 #cf_span[n] (#cf_span[1 ≤ n ≤ 10^5])。第二行包含 #cf_span[n] 个用空格分隔的整数 —— 值 #cf_span[f(1), ..., f(n)] (#cf_span[1 ≤ f(i) ≤ n])。"},{"iden":"output","content":"如果无解，请输出一个整数 _-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)]。如果有多个正确答案，你可以输出任意一个。题目保证，若存在合法答案，则一定存在满足上述限制的答案。"},{"iden":"examples","content":"输入\n3\n1 2 3\n输出\n3\n1 2 3\n1 2 3\n\n输入\n3\n2 2 2\n输出\n1\n1 1 1\n2\n\n输入\n2\n2 1\n输出\n-1"}],"sample_group":[],"show_order":[],"formal_statement":"Let $ f: [n] \\to [n] $ be given.\n\nWe seek a positive integer $ m $, and functions $ g: [n] \\to [m] $, $ h: [m] \\to [n] $, such that:\n\n1. $ g \\circ h = \\text{id}_{[m]} $, i.e., $ g(h(x)) = x $ for all $ x \\in [m] $,\n2. $ h \\circ g = f $, i.e., $ h(g(x)) = f(x) $ for all $ x \\in [n] $.\n\nEquivalently:\n\n- $ h $ is injective (since $ g \\circ h = \\text{id} $),\n- $ g $ is surjective (since $ g \\circ h = \\text{id} $),\n- $ f = h \\circ g $, so $ f $ factors through $ g $ and $ h $.\n\nThis 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]) $.\n\nThat is: Let $ S = f([n]) \\subseteq [n] $. Then $ f|_S: S \\to S $ must be a bijection.\n\n**Necessary and sufficient condition:** $ f(f(x)) = f(x) $ for all $ x \\in [n] $.  \n*(Equivalently: $ f $ is a retraction — its restriction to its image is the identity.)*\n\n---\n\n**If condition fails:** Output $-1$.\n\n**If condition holds:**\n\nLet $ m = |S| = |\\text{image}(f)| $.\n\nLet $ S = \\{ s_1, s_2, \\dots, s_m \\} $, sorted in increasing order.\n\nDefine $ h: [m] \\to [n] $ by $ h(i) = s_i $.\n\nDefine $ g: [n] \\to [m] $ by $ g(x) = i $ where $ s_i = f(x) $.\n\nThen:\n\n- $ h(g(x)) = h(i) = s_i = f(x) $ → $ h \\circ g = f $,\n- $ 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]} $.\n\nThus, the construction works.\n\n---\n\n**Formal Output:**\n\nIf $ f(f(x)) \\ne f(x) $ for some $ x \\in [n] $, output $-1$.\n\nElse:\n\n- Let $ S = \\{ f(x) \\mid x \\in [n] \\} $, and $ m = |S| $.\n- Let $ h: [m] \\to [n] $ be the strictly increasing enumeration of $ S $: $ h(1) < h(2) < \\dots < h(m) $, with $ h(i) \\in S $.\n- Let $ g: [n] \\to [m] $ be defined by $ g(x) = \\text{the index } i \\text{ such that } f(x) = h(i) $.\n\nOutput $ m $, then $ g(1), \\dots, g(n) $, then $ h(1), \\dots, h(m) $.","simple_statement":null,"has_page_source":false}