У Артема есть друг Сандерс из университета Чикаго. Сандерс предложил Артему следующую задачу.
Обозначим за [n] множество {1, ..., n}. Также мы будем использовать обозначение f: [x] → [y], чтобы показать, что функция f имеет значения в точках 1, ..., x, и все эти значения — целые числа от 1 до y.
Итак, вам дана функция f: [n] → [n]. Ваша задача в том, чтобы найти целое положительное число m и две функции g: [n] → [m], h: [m] → [n], такие что g(h(x)) = x для всех 
и h(g(x)) = f(x) для всех 
, либо определите, что найти их невозможно.
Выходные данные
Если найти требуемые функции невозможно, выведите -1.
Иначе, на первой строке выведите число m (1 ≤ m ≤ 106). На второй строке выведите n чисел g(1), ..., g(n). На третьей строке выведите m чисел h(1), ..., h(m).
Если существует несколько верных ответов, вы можете вывести любой из них. Гарантируется, что если ответ существует, то также существует ответ, подходящий под указанные ограничения.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
1 2 3
|
3
1 2 3
1 2 3
|
|
2
|
3
2 2 2
|
1
1 1 1
2
|
|
3
|
2
2 1
|
-1
|