Artsem and Saunders
Time Limit: 1 Sec Memory Limit: 128 MB
Artsem has a friend Saunders from University of Chicago. Saunders presented him with the following problem.

Let [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.

Now 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.

传送门:CF765D

Input

The first line contains an integer n (1≤n≤105). The second line contains n space-separated integers — values f(1),...,f(n) (1≤f(i)≤n).

Output

If there is no answer, print one integer -1. Otherwise, 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).

Sample Input

1
2
3
1 2 3

Sample Output

1
2
3
3
1 2 3
1 2 3

题解

构造 第一次见这种反证构造 长见识了
## AC code:(不包含输入类)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
import java.io.BufferedReader;  
import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.io.*;
import java.util.*;
public class Main {

public static void main(String[] args) {
FastScanner sc=new FastScanner();
PrintWriter pw=new PrintWriter(System.out);
while(sc.hasNext()){
int n=sc.nextInt();
int[]f=new int[n+1];
int[]g=new int[n+1];
int[]h=new int[n+1];
int[]index=new int[n+1];
HashMap<Integer,Integer>map=new HashMap<Integer,Integer>();
int count=0;
int m=0;
for(int i=1;i<=n;i++){
f[i]=sc.nextInt();
if(index[f[i]]==0){
index[f[i]]=++m;
h[m]=f[i];
}
g[i]=index[f[i]];
}
boolean flag=true;
//judge
for(int i=1;i<=m;i++){
if(g[h[i]]!=i) {
flag=false;
break;
}
}
if(flag){
pw.println(m);
for(int i=1;i<=n;i++) pw.print(g[i]+" ");
pw.println();
for(int i=1;i<=m;i++) pw.print(h[i]+" ");
}
else
pw.println(-1);
pw.flush();
}

}

}