問題一覧 > 通常問題

No.1779 Magical Swap

レベル : / AI推定難易度 : 1400 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 80
作問者 : 👑 箱星 / テスター : ramdos
お気に入りにしたユーザー ProblemId : 7121 / 自分の提出
問題文最終更新日: 2022-04-26 00:15:08
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
Advent Calendar Contest 2021 (順位表) の他の問題:

Problem Statement

There are $2$ sequences $A_1,\ldots,A_N$ and $B_1,\ldots, B_N$ of length $N$. A wizard can use the following magic.

  • Choose positive integers $k,i,j$ satisfying $k\ge 2, ki \le N, kj\le N$, and swap the values of $A_{ki}$ and $A_{kj}$.

Determine whether the sequence $A$ can be made equal to the sequence $B$ by using the magic $0$ or more times.

Solve $T$ test cases.

Constraints

  • $1\le T\le 10^5$
  • $1\le N\le 10^5$
  • $1\le A_i\le 10^9$
  • $1\le B_i\le 10^9$
  • The sum of $N$ over all test cases is at most $10^5$.
  • All input values are integers.

Input

First, the number of test cases $T$ is given on the $1$st line of the input.

$T$

Then, $T$ test cases follow, each given in the following format.

$N$
$A_1$ $A_2$ $\ldots$ $A_N$
$B_1$ $B_2$ $\ldots$ $B_N$

Output

For each test case, print Yes on $1$ line if the sequence $A$ can be made equal to the sequence $B$, and No otherwise.

Sample

Sample 1
Input
3
3
7 5 3
7 5 3
6
1 2 3 3 2 1
1 1 2 3 2 3
8
1 2 3 4 5 6 7 8
8 7 6 5 4 3 2 1
Output
Yes
Yes
No

For the $1$st test case, the sequences are equal from the beginning, so there is no need to use the magic.

For the $2$nd test case, choosing $k=2, i=1, j=3$ swaps the values of $A_2$ and $A_6$, and the sequence $A$ changes from $(1,2,3,3,2,1)$ to $(1,1,3,3,2,2)$. Then, choosing $k=3,i=1,j=2$ swaps the values of $A_3$ and $A_6$, and the sequence $A$ becomes $(1,1,2,3,2,3)$. This is equal to the sequence $B$.

For the $3$rd test case, no matter how the magic is used, the sequence $A$ cannot be made equal to the sequence $B$.

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