Здравствуйте!

Не так давно столкнулся с двумя задачками, связанными с перестановками. Решить их у меня не получилось, но мне бы хотелось разобраться, как решать задачи такого типа за полиномиальное время. Прошу помощи.

1) Условие: Дано число n и массив b — некая перестановка чисел от 1 до n. Нужно найти какую-нибудь перестановку a (также из n элементов), чтобы для каждого i (1  ≤  i  ≤  n) выполнялось равенство b[a[a[i]]] = i. К примеру, если нам дана перестановка b = (3, 4, 1, 2), то в качестве ответа можно вывести перестановку a = (2, 3, 4, 1). Если искомой перестановки a не существует, вывести "0".

2) Условие: Из заданной перестановки нужно извлечь квадратный корень. Здесь можно прочесть полное условие этой задачи (задача P).

Заранее всем спасибо!