分数: 400 点
问题陈述
一对长度序列 M 最多由正整数组成 N, (S, T) = ((S_1, S_2, \dots, S_M), (T_1, T_2, \dots, T_M)),据说 是一对很好的序列 当 (S, T) 满足以下条件。
- 存在一个序列 X = (X_1, X_2, \dots, X_N) 长度 N 组成 0 和 1 满足以下条件:
- X_{S_i} \neq X_{T_i} 对于每个 i=1, 2, \dots, M.
给你一对长度为 M 最多由正整数组成 N: (A, B) = ((A_1, A_2, \dots, A_M), (B_1, B_2, \dots, B_M))。如果 (A, B) 是一对很好的序列,打印 Yes;否则,打印 No.
约束
- 1 \leq N, M \leq 2 \times 10^5
- 1 \leq A_i, B_i \leq N
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N M A_1 A_2 \dots A_M B_1 B_2 \dots B_M
输出
If (A, B) 是一对很好的序列,打印 Yes;否则,打印 No.
示例输入 1
3 2 1 2 2 3
示例输出 1
Yes
如果我们设置 X=(0,1,0),那么 X 是一个长度序列 N 组成 0 和 1 满足 X_{A_1} \neq X_{B_1} 和 X_{A_2} \neq X_{B_2}.
因此, (A, B) 满足成为良好序列对的条件。
示例输入 2
3 3 1 2 3 2 3 1
示例输出 2
No
无序列 X 满足条件,因此 (A, B) 不是一对好的序列。
示例输入 3
10 1 1 1
示例输出 3
No
示例输入 4
7 8 1 6 2 7 5 4 2 2 3 2 7 2 1 2 3 3
示例输出 4
Yes