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

Маленький Петя очень любит перестановки. Недавно мама подарила ему перестановку 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 ходов, перестановка Маши ни разу не встречалась на доске.

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

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

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