No.1779 Magical Swap
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もしくは右上の雲マークをクリックしてアカウントを作成してください。