102965: [Atcoder]ABC296 F - Simultaneous Swap
Description
Score : $500$ points
Problem Statement
You are given two sequences of $N$ numbers: $A=(A_1,A_2,\ldots,A_N)$ and $B=(B_1,B_2,\ldots,B_N)$.
Takahashi can repeat the following operation any number of times (possibly zero).
Choose three pairwise distinct integers $i$, $j$, and $k$ between $1$ and $N$.
Swap the $i$-th and $j$-th elements of $A$, and swap the $i$-th and $k$-th elements of $B$.
If there is a way for Takahashi to repeat the operation to make $A$ and $B$ equal, print Yes; otherwise, print No.
Here, $A$ and $B$ are said to be equal when, for every $1\leq i\leq N$, the $i$-th element of $A$ and that of $B$ are equal.
Constraints
- $3 \leq N \leq 2\times 10^5$
- $1\leq A_i,B_i\leq N$
- All values in the input are integers.
Input
The input is given from Standard Input in the following format:
$N$ $A_1$ $A_2$ $\ldots$ $A_N$ $B_1$ $B_2$ $\ldots$ $B_N$
Output
Print Yes if there is a way for Takahashi to repeat the operation to make $A$ and $B$ equal, and print No otherwise.
Sample Input 1
3 1 2 1 1 1 2
Sample Output 1
Yes
Performing the operation once with $(i,j,k)=(1,2,3)$ swaps $A_1$ and $A_2$, and swaps $B_1$ and $B_3$,
making both $A$ and $B$ equal to $(2,1,1)$. Thus, you should print Yes.
Sample Input 2
3 1 2 2 1 1 2
Sample Output 2
No
There is no way to perform the operation to make $A$ and $B$ equal, so you should print No.
Sample Input 3
5 1 2 3 2 1 3 2 2 1 1
Sample Output 3
Yes
Sample Input 4
8 1 2 3 4 5 6 7 8 7 8 5 6 4 3 1 2
Sample Output 4
No
Input
题意翻译
zjh 有两个长度为 $n$ 的序列 $a,b$。 他每次可以选择一组互不相同的 $(i,j,k)$，满足 $1\leqslant i,j,k\leqslant n$，然后交换 $a_i,a_j$，再交换 $b_i,b_k$。 输出是否有可能使得 $a=b$。 Translated by @[Zealous_YH](https://www.luogu.com.cn/user/399150)Output
问题描述
给你两个长度为 N 的数列：$A=(A_1,A_2,\ldots,A_N)$ 和 $B=(B_1,B_2,\ldots,B_N)$。
高桥可以重复执行以下操作任意次（包括0次）：
选择 1 到 N 之间的三个不同的整数 i，j 和 k。
交换数列 A 的第 i 个和第 j 个元素，同时交换数列 B 的第 i 个和第 k 个元素。
如果高桥可以通过重复执行操作使 A 和 B 相等，输出 Yes；否则，输出 No。
在这里，当对于每一个 $1\leq i\leq N$，数列 A 的第 i 个元素和数列 B 的第 i 个元素相等时，称 A 和 B 相等。
约束
- $3 \leq N \leq 2\times 10^5$
- $1\leq A_i,B_i\leq N$
- 输入中的所有值都是整数。
输入
输入通过标准输入给出以下格式：
$N$ $A_1$ $A_2$ $\ldots$ $A_N$ $B_1$ $B_2$ $\ldots$ $B_N$
输出
如果高桥可以通过重复执行操作使 A 和 B 相等，输出 Yes；否则，输出 No。
样例输入 1
3 1 2 1 1 1 2
样例输出 1
Yes
执行一次操作，选择 $(i,j,k)=(1,2,3)$，交换数列 A 的第 1 个和第 2 个元素，同时交换数列 B 的第 1 个和第 3 个元素，
使 A 和 B 都等于 $(2,1,1)$。因此，你应该输出 Yes。
样例输入 2
3 1 2 2 1 1 2
样例输出 2
No
没有方法通过执行操作使 A 和 B 相等，所以你应该输出 No。
样例输入 3
5 1 2 3 2 1 3 2 2 1 1
样例输出 3
Yes
样例输入 4
8 1 2 3 4 5 6 7 8 7 8 5 6 4 3 1 2
样例输出 4
No