← 返回题目列表

AtCoder · abc210_f

F. 共质纸牌

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

分数: 600 点

问题陈述

我们有 N 卡片在桌子上排成一排。 对于每个 i = 1, 2, \ldots, N, i第一张卡有一个整数 前面写着 A_i 和一个整数 背面写有 B_i 。 最初,每张牌都面朝上放置。

高桥会选择他喜欢的任意数量的牌(可能是零)并翻转它们。 那么,如果满足以下条件,他就会很高兴:

  • 对于每对整数 (i, j) 这样 1 \leq i \lt j \leq N,在 i-th 和 j第一张牌是互质的。

判断高桥是否有可能幸福。

约束

  • 1 \leq N \leq 3 \times 10^4
  • 1 \leq A_i, B_i \leq 2 \times 10^6
  • 输入中的所有值都是整数。

输入

输入由标准输入按以下格式给出:

N
A_1 B_1
A_2 B_2
\vdots
A_N B_N

输出

如果高桥有可能幸福,请打印 Yes;否则,打印 No.


示例输入 1

3
2 5
10 9
4 8

示例输出 1

Yes

最初,我们看到整数 2, 10,和 4。 如果我们翻转第一张和第二张牌,我们会看到 5, 9,和 4,这会让高桥高兴。因此,我们应该打印 Yes.


示例输入 2

2
10 100
1000 10000

示例输出 2

No

没有办法翻牌让高桥高兴,所以我们应该打印 No.