AT_abc327_d [ABC327D] Good Tuple Problem

题目描述

对于由不超过 $N$ 的正整数组成的长度为 $M$ 的数列对 $(S, T) = ((S_1, S_2, \dots, S_M), (T_1, T_2, \dots, T_M))$，如果满足以下条件，则称其为良好数列对：

• 存在一个由 $0, 1$ 组成的长度为 $N$ 的数列 $X = (X_1, X_2, \dots, X_N)$，使得对于每个 $i = 1, 2, \dots, M$，都有 $X_{S_i} \neq X_{T_i}$。

现给定一个由不超过 $N$ 的正整数组成的长度为 $M$ 的数列对 $(A, B) = ((A_1, A_2, \dots, A_M), (B_1, B_2, \dots, B_M))$。请判断 $(A, B)$ 是否为良好数列对。如果是，输出 Yes，否则输出 No。

输入格式

输入以如下格式从标准输入读入：

$N$ $M$ $A_1$ $A_2$ $\dots$ $A_M$ $B_1$ $B_2$ $\dots$ $B_M$

输出格式

如果 $(A, B)$ 是良好数列对，输出 Yes；否则输出 No。

输入输出样例 #1

输入 #1

3 2
1 2
2 3

输出 #1

Yes

输入输出样例 #2

输入 #2

3 3
1 2 3
2 3 1

输出 #2

No

输入输出样例 #3

输入 #3

10 1
1
1

输出 #3

No

输入输出样例 #4

输入 #4

7 8
1 6 2 7 5 4 2 2
3 2 7 2 1 2 3 3

输出 #4

Yes

说明/提示

限制条件

• $1 \leq N, M \leq 2 \times 10^5$
• $1 \leq A_i, B_i \leq N$
• 输入的所有值均为整数

样例解释 1

取 $X = (0, 1, 0)$，这是一个由 $0, 1$ 组成的长度为 $N$ 的数列，且满足 $X_{A_1} \neq X_{B_1}$ 且 $X_{A_2} \neq X_{B_2}$。因此，$(A, B)$ 满足良好数列对的条件。

样例解释 2

不存在满足条件的数列 $X$，因此 $(A, B)$ 不是良好数列对。

由 ChatGPT 4.1 翻译