Coprime Solitaire

题目描述

我们有 $N$ 张纸牌按一排放在桌子上。 对于每个 $i = 1, 2, \ldots, N$，第 $i$ 张纸牌的正面写着整数 $A_i$，背面写着整数 $B_i$。 最开始，每张纸牌都是正面朝上。 Takahashi 将选择任意数量的纸牌（也可以为零）并把它们翻面。 然后，如果满足以下条件，他会感到高兴：

对于每一对整数 $(i, j)$ 满足 $1 \leq i \lt j \leq N$，第 $i$ 张和第 $j$ 张纸牌上可见的整数互素。

判定是否存在一种翻牌方式使得 Takahashi 感到高兴。

输入格式

从标准输入读取输入，格式如下： $N$ $A_1$ $B_1$ $A_2$ $B_2$ $\vdots$ $A_N$ $B_N$

输出格式

如果存在使 Takahashi 感到高兴的翻牌方式，输出 $Yes$；否则，输出 $No$。

3
2 5
10 9
4 8

Yes

2
10 100
1000 10000

No

提示

$1 \leq N \leq 3 \times 10^4$ $1 \leq A_i, B_i \leq 2 \times 10^6$ 输入中的所有数值都是整数。最开始，我们看到的整数是 $2$, $10$, 和 $4$。 如果我们把第一张和第二张牌翻面，我们将看到 $5$, $9$, 和 $4$，这会使 Takahashi 感到高兴。因此，我们应该输出 $Yes$。
没有办法通过翻牌使 Takahashi 感到高兴，所以我们应该输出 $No$。

标签: AtCoder|abc210F

来源

AtCoder|abc210F