← 返回题目列表

AtCoder · abc327_d

G. 好元组问题

中文机器翻译题面 查看原题

分数: 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