Story

⏲

「今日も、ありがとございましたー！」

matcharate君、greenrate君とwhiteさんは店に礼をしました。今日もすごく繁盛したので、すごく疲れました。

早速3人はお店の居間で今年の振り返りをしました。今年あったことを振り返ると、やるべきタスクの順番を間違えていたことが判明しました。 (まあ個人の勝手なのですが)

このままでは店の経営者としてまずいと思ったので、来年はしっかりタスクの順番を考えようと思いました。

ひとまず、今年もおつかれさまでした。

end.✨🗻

問題

長さ $N$ の順列 $P=(1,2,\dots,N)$ があります。$P$ を並べ替えたか、$P$ に等しい順列 $Q=(Q_1,Q_2\dots,Q_N)$ が与えられます。

$Q$ に対して次の操作を $0$ 回以上 $K$ 回以下まで行うことができます。

• $1$ 以上 $N$ 以下の異なる整数 $i,j$ を選び，$Q_i,Q_j$ を入れ替える

操作後、$P=Q$ を満たすような操作方法が存在するかどうか判定してください。

$T$ 個のケースに答えてください。

入力

入力は以下の形式で与えられる。

$\text{case}_t$ は次の形式で与えられる。

制約

• $1\le T\le 10^3$
• $1\le N\le 10^3$
• $0\le K\le N$
• 各ケースに対して $Q$ は $P$ を並べ替えたもの、または $P$ に等しいものである
• 入力はすべて整数

出力

ケース毎に次のように答えを改行区切りで出力せよ。

• $P=Q$ を満たす操作方法が存在するなら Yes を、存在しないなら No を出力せよ

入出力例

6
3 1
1 2 3
3 1
1 3 2
3 1
2 1 3
3 1
2 3 1
3 1
3 1 2
3 1
3 2 1

Yes
Yes
Yes
No
No
Yes

例えば $2$ 個目のケースでは $Q=(1,3,2)$ です。$(i,j)=(2,3)$ を選んで入れ替えることで $Q=(1,2,3)=P$ を満たすことができます。
この時操作回数は $K=1$ 以下なので、条件を満たします。よって Yes を出力します。

また $4$ 回目のケースでは $K=1$ 回以下の操作で $P=Q$ とするような操作方法は存在しません。よって No を出力します。