分数: 6 点
问题陈述
你被给予 M 对 (A_i,B_i) 之间的不同整数 1 和 N (含)。
判断是否存在排列 P=(P_1, P_2,\ldots , P_N) 的整数 1 to N 这样 P_{A_i}+P_{B_i} 是的倍数 3 对于所有人 1\leq i\leq M.
约束
- 2 \leq N \leq 1000
- 0 \leq M \leq \min\left( \frac{N(N-1)}{2},2\times 10^5 \right)
- 1 \leq A_i<B_i \leq N
- 对 (A_i, B_i) 都是不同的。
- 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出:
N M A_1 B_1 : A_M B_M
输出
如果存在满足问题陈述中的条件的排列,则打印 Yes;
否则,打印 No.
示例输入 1
5 2 1 2 2 3
示例输出 1
Yes
如果我们选择 P=(1,2,4,3,5),例如,我们有 P_1+P_2=1+2=3 和 P_2+P_3=2+4=6,满足条件。
示例输入 2
3 2 1 2 2 3
示例输出 2
No
有 3!=6 可能的排列,但没有一个满足所有条件。