Phân tích hàm

Ký hiệu $[n]=\{1,2,\dots ,n\}$. Ta viết $f:[x]\to [y]$ khi hàm $f$ được xác định tại mọi điểm nguyên $1,2,\dots ,x$ và mọi giá trị của nó đều là số nguyên thuộc $[1,y]$.

Cho hàm $f:[n]\to [n]$. Hãy tìm một số nguyên dương $m$ cùng hai hàm $g:[n]\to [m]$ và $h:[m]\to [n]$ thoả mãn đồng thời:

• $g(h(x))=x$ với mọi $x\in [m]$;
• $h(g(x))=f(x)$ với mọi $x\in [n]$;

hoặc xác định rằng không tồn tại bộ $(m,g,h)$ nào như vậy.

Nếu có nhiều đáp án hợp lệ, bạn được in ra bất kỳ đáp án nào. Dữ liệu đảm bảo rằng nếu bài toán có lời giải thì cũng có lời giải với $m\le {10}^6$.

Dữ liệu vào

• Dòng đầu chứa số nguyên $n$.
• Dòng thứ hai chứa $n$ số nguyên $f(1),f(2),\dots ,f(n)$.

Dữ liệu ra

Nếu không tồn tại đáp án, in ra một số $-1$.

Ngược lại:

• Dòng đầu in số $m$.
• Dòng thứ hai in $n$ số $g(1),g(2),\dots ,g(n)$.
• Dòng thứ ba in $m$ số $h(1),h(2),\dots ,h(m)$.

Ràng buộc

• $1\le n\le {10}^5$
• $1\le f(i)\le n$
• $1\le m\le {10}^6$

Ví dụ