У Егора был массив \(a\) длины \(n\), изначально состоящий из нулей. Однако он захотел сделать из него другой массив \(b\) длины \(n\).
Поскольку Егор не ищет легких путей, разрешено использовать только такую операцию (возможно ноль или несколько раз):
- выбрать массив \(l\) длины \(k\) (\(1 \leq l_i \leq n\), все \(l_i\) различны) и поменять каждый элемент \(a_{l_i}\) на \(l_{(i\%k)+1}\) (\(1 \leq i \leq k\)).
Ему стало интересно, а можно ли вообще получить массив \(b\) с помощью таких операций. Поскольку Егор еще только начинающий программист, он попросил Вас помочь ему решить эту задачу.
Операция \(\%\) означает взятие по модулю, то есть \(a\%b\) равно остатку от деления числа \(a\) на число \(b\).
Выходные данные
Для каждого набора входных данных выведите «YES» (без кавычек), если существует способ получить массив \(b\), используя только заданную операцию. Иначе выведите «NO» (без кавычек). Вы можете выводить каждую букву в любом регистре (строчную или заглавную). Например, строки «yEs», «yes», «Yes» и «YES» будут приняты как положительный ответ.
Примечание
Рассмотрим первый пример:
- Применим операцию с \(l\) = \([1,2,3]\). Теперь \(a\) = \([2,3,1,0,0]\).
- Применим операцию с \(l\) = \([3,5,4]\). Теперь \(a\) = \([2,3,5,3,4]\) = \(b\).
Мы видим, что получить массив
\(b\) можно. Следовательно ответ
YES.
Во втором примере можно доказать, что массив \(b\) получить нельзя, следовательно ответ NO.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
6
5 3
2 3 5 3 4
4 2
2 4 3 1
1 1
1
3 1
1 2 3
5 3
5 4 3 2 1
6 1
1 2 3 1 5 6
|
YES
NO
YES
YES
NO
NO
|