C - Roller Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 500 点

問題文

長さ N の正整数列 A=(A_1,A_2,\dots,A_N),B=(B_1,B_2,\dots,B_N) が与えられます。

あなたは以下の操作を好きな回数（0 回でもよい）繰り返すことができます。

  • 1 \le i \le N を満たす整数 i を選び、A_i を A_{i+1} で置き換える。

ただし、A_{N+1} とは A_1 のこととします。

A を B に一致させることが出来るか判定してください。

T 個のテストケースが与えられるので、それぞれについて答えを求めてください。

制約

  • 1 \le T \le 5000
  • 1 \le N \le 5000
  • 1 \le A_i,B_i \le N
  • 1 個の入力に含まれるテストケースについて、それらの N の総和は 5000 を超えない。

入力

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

T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T

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

N
A_1 A_2 \dots A_N
B_1 B_2 \dots B_N

出力

T 行出力せよ。 i 行目には、i 個目のテストケースにおいて A を B と一致させることが出来るならば Yes、出来ないならば No を出力せよ。

入力例 1

3
2
1 2
2 2
4
2 3 1 1
2 1 1 2
2
1 1
2 2

出力例 1

Yes
Yes
No

1 個目のテストケースでは、以下のように操作することにより A を B と一致させることが出来ます。

  • i=1 を選ぶ。A_1 を A_2 で置き換える。A=(2,2) となる。

2 個目のテストケースでは、以下のように操作することにより A を B と一致させることが出来ます。

  • i=4 を選ぶ。A_4 を A_1 で置き換える。A=(2,3,1,2) となる。
  • i=2 を選ぶ。A_2 を A_3 で置き換える。A=(2,1,1,2) となる。

3 個目のテストケースでは、どのように操作しても A を B と一致させることは出来ません。

Score : 500 points

Problem Statement

You are given sequences of positive integers of length N: A=(A_1,A_2,\dots,A_N) and B=(B_1,B_2,\dots,B_N).

You can repeat the following operation any number of times (possibly zero).

  • Choose an integer i such that 1 \le i \le N and replace A_i with A_{i+1}.

Here, regard A_{N+1} as A_1.

Determine whether it is possible to make A equal B.

You have T test cases to solve.

Constraints

  • 1 \le T \le 5000
  • 1 \le N \le 5000
  • 1 \le A_i,B_i \le N
  • For each input file, the sum of N over all test cases does not exceed 5000.

Input

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

T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T

Each test case is in the following format:

N
A_1 A_2 \dots A_N
B_1 B_2 \dots B_N

Output

Print T lines. The i-th line should contain Yes if it is possible to make A equal B in the i-th test case, and No otherwise.

Sample Input 1

3
2
1 2
2 2
4
2 3 1 1
2 1 1 2
2
1 1
2 2

Sample Output 1

Yes
Yes
No

In the first test case, you can make A equal B as follows.

  • Choose i=1 to replace A_1 with A_2, making A=(2,2).

In the second test case, you can make A equal B as follows.

  • Choose i=4 to replace A_4 with A_1, making A=(2,3,1,2).
  • Choose i=2 to replace A_2 with A_3, making A=(2,1,1,2).

In the third test case, there is no way to make A equal B.