C - Ball Redistribution Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 1200 点

問題文

1 から N までの番号がついた N 個の箱と，1 から N までの番号がついた N 個のボールがあります．

あなたはすぬけくんに対し，宿題として以下の手順を行うことを課しました．

  • それぞれのボールを好きな箱に入れる．1 つの箱に複数のボールが入ってもよいし，ボールが入らない箱があってもよい．
  • i=1,2,\cdots,N に対してこの順に以下の操作を行う．
    • 箱 i にボールが入っていない場合，何もしない．
    • 箱 i にボールが入っている場合，それらをすべて取り出し，好きな順番で一列に並べる．取り出したボールの個数を k ，列の中のボールの番号を (x_1,x_2,\cdots,x_k) とする．各 1 \leq j \leq k に対して，ボール x_j を箱 x_{j+1} に入れる．ただしここで x_{k+1} は x_1 を意味する． ボールを箱に入れる操作はすべて同時に行うものとする．

すぬけくんは宿題を終えたと主張し，最終状態をあなたに報告してきました． 具体的には，手順の終了後，ボール i が箱 A_i に入っている状態になったと言っています．

あなたは，すぬけくんが手順を正しく行ったかどうかを疑っています． すぬけくんが報告した状態が手順の結果としてあり得るかどうかを判定してください．

1 つの入力につきテストケースは T 個あります．

制約

  • 1 \leq T \leq 250000
  • 1 \leq N \leq 250000
  • 1 \leq A_i \leq N
  • ひとつの入力の中のテストケースすべてにわたる N の総和は 250000 以下である
  • 入力される値はすべて整数

入力

入力は以下の形式で標準入力から与えられる．

T
case_1
case_2
\vdots
case_T

各テストケースは以下の形式で与えられる．

N
A_1 A_2 \cdots A_N

出力

各テストケースに対し，すぬけくんが報告した状態が手順の結果としてあり得るならば Yes，あり得ないならば No を出力せよ．

入力例 1

5
3
1 1 1
3
2 2 2
5
1 2 3 4 5
10
8 3 8 10 1 5 3 1 6 4
10
1 5 1 2 4 8 8 6 7 3

出力例 1

Yes
No
Yes
No
Yes

1 つめのテストケースについて考えます． 以下の手順を考えるとすぬけくんが報告した状態になるので，答えは Yes です．

  • ボール 1,2,3 をそれぞれ箱 1,1,2 に入れる．
  • 箱 1 のボールを取り出して，(2,1) と並べる．
    • ボール 2 を箱 1 に入れる．
    • ボール 1 を箱 2 に入れる．
  • 箱 2 のボールを取り出して，(1,3) と並べる．
    • ボール 1 を箱 3 に入れる．
    • ボール 3 を箱 1 に入れる．
  • 箱 3 のボールを取り出して，(1) と並べる．
    • ボール 1 を箱 1 に入れる．
  • ボール 1,2,3 がそれぞれ箱 1,1,1 に入っている状態になる．

Score : 1200 points

Problem Statement

There are N boxes numbered from 1 to N, and N balls numbered from 1 to N.

You have assigned Snuke the following procedure as homework.

  • Put each ball into any box he likes. Multiple balls can be placed in the same box, and there can be boxes without balls.
  • For i = 1, 2, \cdots, N in this order, perform the following operations.
    • If box i contains no balls, do nothing.
    • If box i contains balls, take all of them out and arrange them in a line in any order he likes. Let k be the number of balls taken out, and (x_1, x_2, \cdots, x_k) be the ball numbers in the line. For each 1 \leq j \leq k, put ball x_j into box x_{j+1}. Here, x_{k+1} means x_1. All these operations of putting balls into boxes happen simultaneously.

He claims that he has completed the homework and reports the final state to you. Specifically, he says that ball i is in box A_i after the procedure.

You doubt whether he has correctly performed the procedure. Determine whether the state he reported is a possible result of the procedure.

There are T test cases for each input.

Constraints

  • 1 \leq T \leq 250000
  • 1 \leq N \leq 250000
  • 1 \leq A_i \leq N
  • The sum of N over all test cases in each input is at most 250000.
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

T
case_1
case_2
\vdots
case_T

Each test case is given in the following format:

N
A_1 A_2 \cdots A_N

Output

For each test case, print Yes if the state Snuke reported is a possible result of the procedure, and No otherwise.

Sample Input 1

5
3
1 1 1
3
2 2 2
5
1 2 3 4 5
10
8 3 8 10 1 5 3 1 6 4
10
1 5 1 2 4 8 8 6 7 3

Sample Output 1

Yes
No
Yes
No
Yes

Consider the first test case. The following steps yield the state Snuke reported, so the answer is Yes.

  • Put balls 1, 2, 3 into boxes 1, 1, 2, respectively.
  • Take out the balls from box 1 and arrange them as (2, 1).
    • Put ball 2 into box 1.
    • Put ball 1 into box 2.
  • Take out the balls from box 2 and arrange them as (1, 3).
    • Put ball 1 into box 3.
    • Put ball 3 into box 1.
  • Take out the balls from box 3 and arrange them as (1).
    • Put ball 1 into box 1.
  • Now, balls 1, 2, 3 are all in box 1.