Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 500 点
問題文
長さ N の数列 A=(A_1,A_2,\ldots,A_N), B=(B_1,B_2,\ldots,B_N) が与えられます。
高橋君は次の操作を好きなだけ (0 回でも良い) 繰り返す事ができます。
1 以上 N 以下の、どの 2 つも互いに相異なる 3 つの整数 i,j,k を選ぶ。
A の i 番目の要素と j 番目の要素を交換し、B の i 番目の要素と k 番目の要素を交換する。
高橋君がうまく操作を繰り返すことによって、
A と B を一致させる事が可能ならば Yes
を、不可能ならば No
を出力してください。
ただし、A と B が一致しているとは、任意の 1\leq i\leq N について A の i 番目の要素と B の i 番目の要素が等しいことを言います。
制約
- 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) として 1 回操作を行うことで、A_1 と A_2、B_1 と B_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
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