根据那两个式子
g(h(x))=x
h(g(x))=f(x)
可以推出来两个新的式子
g(f(x))=g(x)
h(x)=f(h(x))
于是，我们先找到f(x)的所有不动点，有几个不动点，m就是多少，将它们依次赋值给h(1),h(2),...,h(m)，对应的g(h(i))赋值成1,2,..,m
然后如果对于某个i，g(f(i))不存在的话，则无解，否则有解，将g和h依次输出即可。
#include<cstdio>
using namespace std;
int n,f[100010],g[100010],h[1000010],m;
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;++i)
scanf("%d",&f[i]);
for(int i=1;i<=n;++i)
if(f[i]==i)
{
h[++m]=i;
g[i]=m;
}
if(!m)
{
puts("-1");
return 0;
}
for(int i=1;i<=n;++i)
if(!g[f[i]])
{
puts("-1");
return 0;
}
printf("%d\n",m);
for(int i=1;i<n;++i)
printf("%d ",g[f[i]]);
printf("%d\n",g[f[n]]);
for(int i=1;i<m;++i)
printf("%d ",h[i]);
printf("%d\n",h[m]);
return 0;
}