No.482 あなたの名は

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 129
作問者 : ei1333ei1333 / テスター : tatuyan_edsontatuyan_edson

6 ProblemId : 1330 / 出題時の順位表

問題文

$N$ 人がいて, それぞれ $1$ から $N$ までの番号が振られています。 最初, 人 $i$ には自分の魂 $i$ が宿っていました。

ハクビシンくんはプロなので, 任意の異なる $2$ 人を選んで $2$ 人に宿っている魂を入れ替える操作ができます。 この操作に夢中だったハクビシンくんは, 何度かこの操作を行いました。 その結果, 現在人 $i$ には魂 $D_i$ が宿っています。

ここでハクビシンくんは, 魂を入れ替える操作をあと $K$ 回行ったら操作能力が消えることに気づきました。

自分と違う魂が宿った状態のまま放っておくのは可哀想なので, すべての人について自分の魂が宿っているという最初の状態に戻したいです。

また操作能力を残していると衝動に駆られて使ってしまいそうなので, ちょうど $K$ 回の操作を使い切りたいです。

ちょうど $K$ 回の操作で, すべての人に自分の魂が宿っている状態に戻せるか判定してください。

入力

$N\ K$
$D_1\ D_2\ \dots\ D_N$
  • $1$ 行目に, 人数 $N(2 \le N \le 200\ 000)$, 残り操作回数 $K(1 \le K \le 10^{12}) $ が与えられます。
  • $2$ 行目に, 現在の魂の状態が与えられます。 $i(1 \le i \le N)$ 番目の値 $D_i(1 \le D_i \le N)$ は, 現在人 $i$ に魂 $D_i$ が宿っていることを意味します。 $1$ から $N$ までの値はちょうど $1$ 回ずつ現れることが保証されます。

$K$ が 32 bit整数型に収まらないことがあるので注意してください。

出力

$1$ 行に, ちょうど $K$ 回の操作ですべての人に自分の魂が宿っている状態にできるとき YES, できないとき NO を出力してください。

最後に改行してください。

サンプル

サンプル1
入力
2 1
2 1
出力
YES

ちょうど $1$ 回の操作を行います。

人 $1$ と人 $2$ を選んで魂を交換すると $\{1, 2\}$ となり, すべての人に自分の魂が宿っている状態になるので YES を出力します。

サンプル2
入力
3 2
3 2 1
出力
NO

ちょうど $2$ 回の操作では, すべての人に自分の魂が宿っている状態にできません。 NO を出力します。

例えば, 人 $1$ と人 $3$ を選んで魂を交換すると $\{1, 2, 3\}$ となりますが操作は $2$ 回行う必要があります。

サンプル3
入力
4 2
1 2 3 4
出力
YES

例えば, $1$ 回目に人 $1$ と人 $2$ を選んで魂を交換すると $\{2, 1, 3, 4\}$ となります。 $2$ 回目にも人 $1$ と人 $2$ を選んで魂を交換すると $\{1, 2, 3, 4\}$ となるので YES を出力します。

提出ページヘ