Good Tuple Problem

题目描述

长度为 $M$ 的由不超过 $N$ 的正整数组成的序列对 $(S, T) = ((S_1, S_2, \dots, S_M), (T_1, T_2, \dots, T_M))$ 被称为良好序列对，当且仅当 $(S, T)$ 满足下列条件。

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

给定一个长度为 $M$ 的由不超过 $N$ 的正整数组成的序列对 $(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$。

3 2
1 2
2 3

Yes

3 3
1 2 3
2 3 1

No

10 1
1
1

No

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

Yes

提示

$1 \leq N, M \leq 2 \times 10^5$ $1 \leq A_i, B_i \leq N$ 所有输入值均为整数。如果我们取 $X=(0,1,0)$，那么 $X$ 是一个长度为 $N$ 的由 $0$ 和 $1$ 组成的序列，满足 $X_{A_1} \neq X_{B_1}$ 和 $X_{A_2} \neq X_{B_2}$。
因此，$(A, B)$ 满足成为良好序列对的条件。
没有序列 $X$ 满足该条件，所以 $(A, B)$ 不是良好序列对。

标签: AtCoder|abc327D

来源

AtCoder|abc327D