Задача . B. Игра с перестановками

Маленький Петя очень любит перестановки. Недавно мама подарила ему перестановку q₁, q₂, ..., q_n длины n.

Перестановкой a длины n будем называть последовательность целых чисел a₁, a₂, ..., a_n (1 ≤ a_i ≤ n), все числа которой различны.

Больше чем перестановки Петя любит только играть с маленькой Машей. Оказалось, у Маши тоже есть перестановка длины n. Петя решил во что бы то ни стало, получить такую же перестановку. Для этого он придумал игру со следующими правилами:

• Перед началом игры Петя записывает на доске перестановку 1, 2, ..., n. После чего Петя делает ровно k ходов, описанных ниже.
• На очередном ходу бросается монета. Если выпал орел, то выполняется пункт 1, если решка — пункт 2.
  1. Пусть на доске в данный момент записана перестановка p₁, p₂, ..., p_n. Тогда записанная на доске перестановка p стирается, а вместо нее записывается следующая: p_q1, p_q2, ..., p_qn. Иными словами, к перестановке p применяется перестановка q, подаренная Пете.
  2. Все действия аналогичны пункту 1, за исключением того что на доску записывается перестановка t, такая что: t_qi = p_i для всех i от 1 до n. Иными словами, к перестановке p применяется перестановка, обратная к q.

Известно, что после k-го хода на доске оказалась перестановка Маши s₁, s₂, ..., s_n. Кроме того, известно, что в процессе игры до k-го хода перестановка Маши ни разу не встретилась на доске. Обратите внимание, что в игре ровно k ходов, то есть в процессе игры монетка подбрасывалась ровно k раз.

Ваша задача — определить, возможна ли описанная ситуация, либо сообщить, что Петя что-то перепутал. Смотрите примеры из условия и разъяснения к ним для лучшего понимания.