Пожалуйста, подпишитесь на официальный канал Codeforces в Telegram по ссылке https://t.me/codeforces_official. ×

B. Игра с перестановками
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
stdin
вывод
stdout

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

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

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

  • Перед началом игры Петя записывает на доске перестановку 1, 2, ..., n. После чего Петя делает ровно k ходов, описанных ниже.
  • На очередном ходу бросается монета. Если выпал орел, то выполняется пункт 1, если решка — пункт 2.
    1. Пусть на доске в данный момент записана перестановка p1, p2, ..., pn. Тогда записанная на доске перестановка p стирается, а вместо нее записывается следующая: pq1, pq2, ..., pqn. Иными словами, к перестановке p применяется перестановка q, подаренная Пете.
    2. Все действия аналогичны пункту 1, за исключением того что на доску записывается перестановка t, такая что: tqi = pi для всех i от 1 до n. Иными словами, к перестановке p применяется перестановка, обратная к q.

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

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

Входные данные

В первой строке записаны два целых числа n и k (1 ≤ n, k ≤ 100). Во второй строке записаны n целых чисел через пробел q1, q2, ..., qn (1 ≤ qi ≤ n) — перестановка, подаренная Пете. В третьей строке записана Машина перестановка s, в аналогичном формате.

Гарантируется, что заданные последовательности q и s — корректные перестановки.

Выходные данные

Если описанная в условии ситуация возможна, выведите «YES» (без кавычек), иначе — выведите «NO» (без кавычек).

Примеры
Входные данные
4 1
2 3 4 1
1 2 3 4
Выходные данные
NO
Входные данные
4 1
4 3 1 2
3 4 2 1
Выходные данные
YES
Входные данные
4 3
4 3 1 2
3 4 2 1
Выходные данные
YES
Входные данные
4 2
4 3 1 2
2 1 4 3
Выходные данные
YES
Входные данные
4 1
4 3 1 2
2 1 4 3
Выходные данные
NO
Примечание

В первом примере перестановка Маши совпадает с перестановкой, которая была записана на доске перед началом игры. Следовательно, нарушается условие, что перед выполнением k ходов, перестановка Маши ни разу не встречалась на доске.

Во втором примере описанная ситуация возможна, в случае если после подбрасывания монетки выпала решка.

В третьем примере возможная последовательность выпадений монетки такая: орел-решка-решка.

В четвертом примере возможна следующая последовательность выпадений монетки: орел-орел.