問題一覧 > 通常問題

No.482 Your Name Is

レベル : / AI推定難易度 : 850 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 285
作問者 : ei1333333 / テスター : tatuyan_edson
お気に入りにしたユーザー ProblemId : 1330 / 自分の提出
問題文最終更新日: 2026-06-25 02:24:50
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 156 (順位表) の他の問題:

Problem Statement

There are $N$ people, numbered from $1$ to $N$. Initially, person $i$ was inhabited by their own soul $i$.

Hakubishin-kun is a pro, so he can perform an operation of choosing any $2$ distinct people and swapping the souls inhabiting those $2$ people. Absorbed in this operation, Hakubishin-kun performed it several times. As a result, person $i$ is currently inhabited by soul $D_i$.

Now Hakubishin-kun has realized that after $K$ more soul-swapping operations, he will lose his ability to perform the operation.

Since it would be cruel to leave people inhabited by souls other than their own, he wants to return to the initial state, in which every person is inhabited by their own soul.

Also, if any of his ability remains, he might give in to the urge to use it, so he wants to use up exactly $K$ operations.

Determine whether it is possible to return to the state in which every person is inhabited by their own soul using exactly $K$ operations.

Input

$N\ K$
$D_1\ D_2\ \dots\ D_N$
  • The $1$st line contains the number of people $N(2 \le N \le 200\ 000)$ and the number of remaining operations $K(1 \le K \le 10^{12}) $.
  • The $2$nd line gives the current state of the souls. The $i(1 \le i \le N)$-th value $D_i(1 \le D_i \le N)$ means that person $i$ is currently inhabited by soul $D_i$. It is guaranteed that each value from $1$ to $N$ appears exactly $1$ time.

Note that $K$ may not fit in a 32 bit integer type.

Output

Print YES on $1$ line if it is possible to make every person inhabited by their own soul using exactly $K$ operations, and NO if it is not possible.

Print a newline at the end.

Sample

Sample 1
Input
2 1
2 1
Output
YES

Exactly $1$ operation is performed.

Choosing person $1$ and person $2$ and swapping their souls gives $\{1, 2\}$, and every person is inhabited by their own soul, so print YES.

Sample 2
Input
3 2
3 2 1
Output
NO

With exactly $2$ operations, it is not possible to make every person inhabited by their own soul. Print NO.

For example, choosing person $1$ and person $3$ and swapping their souls gives $\{1, 2, 3\}$, but $2$ operations must be performed.

Sample 3
Input
4 2
1 2 3 4
Output
YES

For example, choosing person $1$ and person $2$ in the $1$st operation and swapping their souls gives $\{2, 1, 3, 4\}$. Choosing person $1$ and person $2$ again in the $2$nd operation and swapping their souls gives $\{1, 2, 3, 4\}$, so print YES.

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。